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 / output : F = saving arc, save_length = minimum length
def Dijkstra(w, save_length) :
    # n = size of w
    n = len(w)
    #initialize save_length
    for i in range(0, n) :
        save_length.append(0)

    #touch[i] = v1에서 vi로 가기 위한 최단 경로상의 마지막 정점, 즉 v(i-1)
    touch = list()
    touch.append(0)
    #length[i] = v1에서 vi로 가는 현재 최단 경로의 길이
    length = list()
    length.append(0)

    for i in range(1, n) :
        touch.append(0)
        length.append(w[0][i])

    #F = output
    F = set()

    #repeat (n - 1) times
    index = 0
    while index < n - 1 :
        min = 1000 #min = infinite
        #initialize vnear : 0
        vnear = 0
        for i in range(1, n) :
            if (length[i] >= 0 and length[i] < min) :
                min = length[i]
                vnear = i

        #F에 이음선 e = (touch[vnear], vnear)를 추가한다.
        F.add((touch[vnear], vnear))

        for i in range(1, n) :
            if(length[vnear] + w[vnear][i] < length[i]) :
                length[i] = length[vnear] + w[vnear][i]
                touch[i] = vnear
            #이미 vnear를 거쳐간 이후에는 save_length를 더이상 업데이트 할 필요가 없다.
            if(length[i] >= 0) :
                save_length[i] = length[i]


        length[vnear] = -1
        index += 1

    return F





#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'),
            ])
        }

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

print('\n')


#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]]

#save_length : saving minimum length
save_length = list()

dijkstra = Dijkstra(w, save_length)
print('Dijkstra Algorithm : \n', dijkstra)
print('Dijkstra Length : \n', save_length)