import numpy as np

#Kruskal Algorithm
parent = dict()
rank = dict()

#초기화 함수이다.
def make_singleton_set(v) :
    parent[v] = v
    rank[v] = 0

#해당 노드를 가지고 있는 집합을 리턴한다.
def find(v) :
    if(parent[v] != v) :
        parent[v] = find(parent[v])
    return parent[v]

#r1, r2 집합을 합집합 연산한다.
def union(r1, r2) :
    if(r1 != r2) :
        if(rank[r1] > rank[r2]) :
            parent[r2] = r1
        else :
            parent[r1] = r2
            if(rank[r1] == rank[r2]) :
                rank[r2] += 1

#define Kruskal Algorithm : input = graph
def Kruskal(graph) :
    #n =  정점의 수 / m = 엣지의 수
    n = len(graph['vertices'])

    #엣지를 전부 찾은 후 비내림차순으로 정렬한다.
    edge_list = list(graph['edges'])
    edge_list.sort()

    #초기화한다
    for v in graph['vertices'] :
        make_singleton_set(v)

    #리턴할 edges 집합
    F = set()

    index = 0
    while len(F) < n - 1 :
        #e = edges 이음선
        e = edge_list[index]

        #p , q는 각각의 집합들을 가리키는 포인터이다.
        p = find(e[1])
        q = find(e[2])

        #만약 p와 q가 다른 집합이면 서로를 합집합한다.
        if(p != q) :
            union(p, q)
            F.add(e)

        index += 1

    return F

#Dijkstra Algorithm : input = graph
def dijkstra(w) :
    n = len(w)




#practice about Kruskal Algorithm
graph = {
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': set([
            (1, 'A', 'B'),
            (3, 'A', 'C'),
            (3, 'B', 'C'),
            (6, 'B', 'D'),
            (4, 'C', 'D'),
            (2, 'C', 'E'),
            (5, 'D', 'E'),
            ])
        }

#mst = result of applying Kruskal Algorithm
mst = Kruskal(graph)
print('Kruskal Algorithm : ', "\n", mst)

#Dijkstra Algorithm
inf = 1000
w = [[0,7,4,6,1],[inf,0,inf,inf,inf],
   [inf,2,0,5,inf], [inf,3,inf,0,inf], [inf,inf,inf,1,0]]