import graph as _g
import notintersectset as _s
import math as _math
from copy import deepcopy as _deepcopy

class _MST:
    def __init__(self, *args, **kwwords):
        pass

    def generic_mst(self, g: _g.Graph):
        '''
        通用最小生成树算法

        Args
        ===
        `g` : 图G=(V,E)

        `w` : 图的权重

        Doc
        ===
        # A = []

        # while A does not form a spanning tree

        #    do find an edge (u,v) that is safe for A (保证不形成回路)

        #       A <- A ∪ {(u, v)}

        # return A

        '''
        A = ['generic mst']
        g.edges.sort()
        return A

    def mst_kruskal(self, g : _g.Graph):
        '''
        最小生成树的Kruska算法 时间复杂度`O(ElgV)`
        Args
        ===
        `g` : 图`G=(V,E)`

        Return
        ===
        `(mst_list, weight)` : 最小生成树列表和最小权重组成的`tuple`

        Example
        ===
        ```python
        g = Graph()
        g.clear()
        g.addvertex(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'])
        g.addedgewithweight('a', 'b', 4)
        g.addedgewithweight('b', 'c', 8)
        g.addedgewithweight('c', 'd', 7)
        g.addedgewithweight('d', 'e', 9)
        g.addedgewithweight('a', 'h', 8)
        g.addedgewithweight('b', 'h', 11)
        g.addedgewithweight('c', 'i', 2)
        g.addedgewithweight('i', 'h', 7)
        g.addedgewithweight('h', 'g', 1)
        g.addedgewithweight('g', 'f', 2)
        g.addedgewithweight('f', 'e', 10)
        g.addedgewithweight('d', 'f', 14)
        g.addedgewithweight('c', 'f', 4)
        g.addedgewithweight('i', 'g', 4)
        mst_kruskal(g)
        >>> ([('h', 'g', 1), ('c', 'i', 2), ('g', 'f', 2), ('a', 'b', 4), ('c', 'f', 4), ('c', 'd', 7), ('b', 'c', 8), ('d', 'e', 9)], 37)
        ```
        '''
        s = _s.Set()
        A = []
        weight = 0
        for v in g.veterxs:
            s.make_set(v)
        g.edges.sort()
        for e in g.edges:
            (u, v) = g.getvertexfromedge(e)
            uset = s.find(u)
            vset = s.find(v)
            if uset != vset:
                A += [(u.key, v.key, e.weight)]
                s.union(uset, vset)
                weight += e.weight
        return A, weight

    def __change_weightkey_in_queue(self, Q, v, u):
        for q in Q:
            if q.key == v.key:
                q.weightkey = v.weightkey
                q.pi = u
                break

    def mst_prism(self, g : _g.Graph, r : _g.Vertex):
        '''
        最小生成树的Prism算法 时间复杂度`O(ElgV)`
        Args
        ===
        `g` : 图`G=(V,E)`

        Return
        ===
        `weight` : 最小权重
        '''
        for u in g.veterxs:
            u.isvisit = False
            u.weightkey = _math.inf
            u.pi = None
        if type(r) is not _g.Vertex:
            r = g.veterxs_atkey(r)
        else:
            r = g.veterxs_atkey(r.key)
        r.weightkey = 0   
        total_adj = g.getadj_from_matrix()
        weight = 0
        n = g.vertex_num
        weight_min = 0
        k = 0
        tree = []
        for j in range(n):
            weight_min = _math.inf
            u = None
            # 优先队列Q extract-min
            for v in g.veterxs:
                if v.isvisit == False and v.weightkey < weight_min:
                    weight_min = v.weightkey
                    u = v
            u.isvisit = True
            # 获取u的邻接表
            adj = g.getvertexadj(u)
            # 计算最小权重
            weight += weight_min        
            for v in adj:
                # 获取边
                edge = g.getedge(u, v)
                # 构造最小生成树
                if weight_min != 0 and edge.weight == weight_min:
                    tree.append((v.key, u.key, weight_min))
                # if v ∈ Q and w(u, v) < key[v]
                if v.isvisit == False and edge.weight < v.weightkey:
                    v.pi = u
                    v.weightkey = edge.weight
                    # 更新Vertex域 如果是引用则不需要，此处adj不是引用
                    for q in g.veterxs:
                        if q.key == v.key:
                            q.weightkey = v.weightkey
                            q.pi = v.pi
                            break
        return tree, weight

    def mst_dijkstra(self, g: _g.Graph, r: _g.Vertex):
        '''
        最小生成树的Prism算法 时间复杂度`O(ElgV)`
        Args
        ===
        `g` : 图`G=(V,E)`

        Return
        ===
        `weight` : 最小权重
        '''
        for u in g.veterxs:
            u.isvisit = False
            u.weightkey = _math.inf
            u.pi = None
        if type(r) is not _g.Vertex:
            r = g.veterxs_atkey(r)
        else:
            r = g.veterxs_atkey(r.key)
        r.weightkey = 0
        total_adj = g.getadj_from_matrix()
        weight = 0
        n = g.vertex_num
        weight_min = 0
        k = 0
        tree = []
        for j in range(n):
            weight_min = _math.inf
            u = None
            # 优先队列Q extract-min
            for v in g.veterxs:
                if v.isvisit == False and v.weightkey < weight_min:
                    weight_min = v.weightkey
                    u = v
            u.isvisit = True
            # 获取u的邻接表
            adj = g.getvertexadj(u)
            # 计算最小权重
            weight += weight_min
            for v in adj:
                # 获取边
                edge = g.getedge(u, v)
                # 构造最小生成树
                if weight_min != 0 and edge.weight == weight_min:
                    tree.append((v.key, u.key, weight_min))
                # if v ∈ Q and w(u, v) < key[v]
                if v.isvisit == False and edge.weight < v.weightkey:
                    v.pi = u
                    v.weightkey = edge.weight
                    # 更新Vertex域 如果是引用则不需要，此处adj不是引用
                    for q in g.veterxs:
                        if q.key == v.key:
                            q.weightkey = v.weightkey
                            q.pi = v.pi
                            break
        return tree, weight

__mst_instance = _MST()
generic_mst = __mst_instance.generic_mst
mst_kruskal = __mst_instance.mst_kruskal
mst_prism = __mst_instance.mst_prism
mst_dijkstra = __mst_instance.mst_dijkstra

def buildgraph():
    '''
    构造图
    '''
    g =  _g.Graph()
    g.clear()
    g.addvertex(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'])
    g.addedgewithweight('a', 'h', 8)
    g.addedgewithweight('a', 'b', 4)
    g.addedgewithweight('b', 'c', 8)
    g.addedgewithweight('c', 'd', 7)
    g.addedgewithweight('d', 'e', 9)
    g.addedgewithweight('b', 'h', 11)
    g.addedgewithweight('c', 'i', 2)
    g.addedgewithweight('i', 'h', 7)
    g.addedgewithweight('h', 'g', 1)
    g.addedgewithweight('g', 'f', 2)
    g.addedgewithweight('f', 'e', 10)
    g.addedgewithweight('d', 'f', 14)
    g.addedgewithweight('c', 'f', 4)
    g.addedgewithweight('i', 'g', 6)
    return g

def test_mst_generic():
    g = _g.Graph()
    g.clear()
    g.addvertex(['a', 'b', 'c', 'd'])
    g.addedgewithweight('a', 'b', 2)
    g.addedgewithweight('a', 'd', 3)
    g.addedgewithweight('b', 'c', 1)
    print('邻接表为')
    _g._print_inner_conllection(g.adj)
    print('邻接矩阵为')
    print(g.matrix)
    print('图G=(V,E)的集合为')
    _g._print_inner_conllection(g.edges)
    print(generic_mst(g))
    print('边按权重排序后图G=(V,E)的集合为')
    _g._print_inner_conllection(g.edges)
    del g

def test_mst_kruskal():
    g = buildgraph()
    print('边和顶点的数量分别为:', g.edge_num, g.vertex_num)
    print('邻接表为')
    g.printadj()
    print('邻接矩阵为')
    print(g.matrix)
    print('最小生成树为：')
    mst_list = mst_kruskal(g)
    print(mst_list)
    del g

def test_mst_prism():
    g = buildgraph()
    print('边和顶点的数量分别为:', g.edge_num, g.vertex_num)
    print('邻接表为')
    g.printadj()
    print('邻接矩阵为')
    print(g.matrix)
    print('最小生成树为：')
    mst_list = mst_prism(g, 'a')
    print(mst_list)
    del g

def test_mst_dijkstra():
    g = buildgraph()
    print('邻接表为')
    g.printadj()
    print('最小生成树为：')
    print(g.matrix)
    del g

def test():
    '''
    测试函数
    '''
    test_mst_generic()
    test_mst_kruskal()
    test_mst_prism()
    test_mst_dijkstra()

if __name__ == '__main__':
    print('test as follows')
    test()
else:
    pass