from problem import Problem
import random

solutie = ''
sol = ''

# A utility function to find set of an element i
# (uses path compression technique)
def find( parinte, i):
    if parinte[i] == i:
        return i
    return find(parinte, parinte[i])

# A function that does union of two sets of x and y
# (uses union by rank)
def union( parinte, rank, x, y):
    xroot = find(parinte, x)
    yroot = find(parinte, y)

    # Attach smaller rank tree under root of
    # high rank tree (Union by Rank)
    if rank[xroot] < rank[yroot]:
        parinte[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parinte[yroot] = xroot

    # If ranks are same, then make one as root
    # and increment its rank by one
    else:
        parinte[yroot] = xroot
        rank[xroot] += 1


# The main function to construct MST using Kruskal's
# algorithm
def KruskalMST(graph,V):
    global solutie

    result =[] #This will store the resultant MST

    i = 0  # An index variable, used for sorted edges
    e = 0  # An index variable, used for result[]

    # Step 1:  Sort all the edges in non-decreasing
    # order of their
    # weight.  If we are not allowed to change the
    # given graph, we can create a copy of graph
    graph = sorted(graph, key=lambda item: item[2])

    parent = []
    rank = []

    # Create V subsets with single elements
    for node in range(V):
        parent.append(node)
        rank.append(0)

    # Number of edges to be taken is equal to V-1
    while e < V - 1:

        # Step 2: Pick the smallest edge and increment
        # the index for next iteration
        u, v, w = graph[i]
        i = i + 1
        x = find(parent, u)
        y = find(parent, v)

        # If including this edge does't cause cycle,
        # include it in result and increment the index
        # of result for next edge
        if x != y:
            e = e + 1
            result.append([u, v, w])
            union(parent, rank, x, y)
        # Else discard the edge

    # print the contents of result[] to display the built MST
    solutie += "Muchiile arborelui de cost minim obtinut sunt urmatoarele:\n"

    for u, v, weight in result:
        solutie += str(u) + " -- " + str(v) + " == " + str(weight) + '\n'


class Problem42(Problem):

    def __init__(self):
        statement = "Primind urmatorul graf, construiti arborele partial de cost minim (Kruskal):\n\n"
        data = []

        V = random.randint(6, 9)  # Generez un numar de varfuri intre 6 si 9

        graph = []   # Dictionarul in care stocam graful

        matrice = [[0 for x in range(V)] for y in range(V)]  # Declar matricea de adiacenta si o initializez cu 0
        for i in range(0, V):
            for j in range(i + 1, V):   # Pentru fiecare element de deasupra diagonalei principale
                matrice[i][j] = random.randint(0, 1)    # generez 0 sau 1:  1 - exista muchie intre i si j;  0 - nu exista muchie
                matrice[j][i] = matrice[i][j]           # si fac matricea simetrica

        for i in range(0, V):
            ok = 0
            for j in range(0, V):
                if matrice[i][j] == 1:
                    ok = ok + 1       # Numar cati de 1 sunt pe o linie;
            if ok <= 1:               # daca e cel mult un 1
                for j in range(0, V):
                    matrice[i][j] = 1       # populez toata linia cu 0
                    matrice[j][i] = 1

        for i in range(0, V):
            matrice[i][i] = 0       # Fac elementele de pe diagonala principala 0
        statement += "Lista de muchii:\n"
        for i in range(0, V):
            for j in range(i + 1, V):       # Parcurg matricea deasupra diagonalei principale
                if matrice[i][j] == 1:      # daca elementul de pe pozitia [i][j] este 1
                    c = random.randint(1, 30)       # generez un cost intre 1 si 20

                    statement += str(i) + '  ' + str(j) + ' -> ' + str(c) + '\n'
                    graph.append([i, j, c])     # si adaug muchia si costul ei in graf

        KruskalMST(graph, V)

        super().__init__(statement, data)


    def solve(self):

        solution = "Idee de rezolvare: \n"
        solution += "Pas 1: Sortam muchiile crescator in functie de cost;\n"
        solution += "pas 2: Alegem cea mai mica muchie. Verificam daca inchide un ciclu cu arborele\n"
        solution += "format pana acum. Daca nu inchide un ciclu, includem muchia in arborele de cost minim;\n"
        solution += "Pas 3: Repetam pasul 2 pana cand numarul muchiilor din arbore este cu unu mai putin decat numarul de noduri.\n\n"

        solution += solutie
        return solution

p = Problem42()
print(p.statement)
print(p.solve())