#!/usr/bin/env python
#encoding: utf-8
import random
import argparse
import pstats
import cProfile
import sys
sys.path.append("C:\\Users\\Utente\\Downloads")
from sorting.sorting.Sorting import mergeSort
from graph.Graph_IncidenceList import GraphIncidenceList as Graph
from mst.GraphHelper import GraphHelper
from mst.mst import MST


def  _parseargs( ):
    parser = argparse.ArgumentParser(description = 'Questo strumento serve per'
         'prendere il numero di nodi ed archi con cui si vuole creare il grafo')
    parser.add_argument("nodi",type=int,help="inserire il numero di nodi")
    parser.add_argument("archi",type=int,help="inserire il numero di archi:non "
                                      "puo essere maggiore del doppio dei nodi")
    parser.add_argument("pesoMassimo",type=int,help="inserire il peso massimo "
                                                     "assegnabile ad ogni arco")
    parser.add_argument("nomeFunzione",type=str , help="permette di scegliere "
        "se avere un grafo che presenti archi con pesi casuali che non vengano "
          "perturbati(anche pesi uguali tra loro),pesi pertubati attraverso un "
      "contatore o perturbati casualmente, inserendo rispettivamente : casuale,"
                                      "contatorePerturbato o casualePerturbato")
    args = parser.parse_args()
    return args


def randomEdge(nodes,maxWeight,funcName):
    """crea un arco avente testa,coda e peso casuali"""
    head = random.randint(0,nodes-1)
    tail = random.randint(0,nodes-1)
    while head == tail:
     tail = random.randint(0,nodes-1)
    if funcName=='casuale':              #assegna all'arco un peso rappresentato
     weight = random.randint(0,maxWeight)                 # da un intero casuale
    if funcName=='casualePerturbato': #assegna all'arco un peso intero che viene
     weight = random.randint(0,maxWeight)+random.random()     #perturbato con un
    return(head,tail,weight)               #decimale di 16 cifre dopo la virgola

def randomEdge_1(nodes,maxWeight,count): #variante della fuznione precedente che
    head = random.randint(0,nodes-1)#perturba il peso dell'arco con un contatore
    tail = random.randint(0,nodes-1)                       #di 13 cifre decimali
    while head == tail:
     tail = random.randint(0,nodes-1)
    weight = random.randint(0,maxWeight)+count
    return (head,tail,weight)


def BGR(nodes,edges,maxWeight,funcName):
    """genera un grafo casuale rappresentato tramite liste di incidenza"""
    if edges > (2*nodes):
      edges = int(input("inserire un numero di archi uguale massimo al doppio"
                                                                    "dei nodi"))
    if nodes <= 0:
      print("il grafo è vuoto")
      return
    if nodes == 1 and edges > 0:
      print("impossibile creare archi aventi stesso vertice come testa e coda")
      return
    g = Graph()
    n =[]
    ginfo = ()
    for i in range(nodes):
      n.append(g.insertNode(i))
    if funcName == "contatorePerturbato":
     count = 0.0000000000000    #contatore per il perturbamento manuale del peso
     for e in range(edges):                                           #dell'arco
      ginfo = ginfo + (randomEdge_1(nodes,maxWeight,count),)
      count = count + 0.0000000000001
    else:
     for e in range(edges):
      ginfo = ginfo + (randomEdge(nodes,maxWeight,funcName),)
    for e in ginfo:
     g.insertEdge(e[0], e[1], e[2])
     g.insertEdge(e[1], e[0], e[2])
    #g.printGraph()        # printa il grafo prima che cleanGraph venga chiamato
    c = GraphHelper()                      # nel caso lo si volesse visualizzare
    c.cleanGraph(g)
    g.printGraph()
    return g

def graphEdges(graph):
    """crea una lista di tuple rappresentanti gli archi all'interno
    delle liste di incidenza (o del grafo)"""
    nodes = len(graph.nodes)
    edgesList = []
    for i in range(nodes):
        curr = graph.inc[i].getFirstRecord()
        while curr != None:
            edge = curr.elem
            head = edge.head
            tail = edge.tail
            weight = edge.weight
            edgesList.append((head,tail,weight))
            curr = curr.next
    print ("\n")
    return edgesList

def find(parent,i):
    """strumento per il controllo dei vertici(se parti dello stesso mst)"""
    if parent[i] == i:
        return i
    return find(parent,parent[i])

def union(parent,rank,x,y):
    """strumento per la formazione dei supervertci: unisce piu vertici in uno"""
    xroot = find(parent,x)
    yroot = find(parent,y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[yroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

def boruvka(graph):
    """Genera il Minimo Albero Ricoprente di un grafo secondo l'algoritmo di
    Boruvka implementato con il concetto di union by rank"""
    mstlist = []
    trees = len(graph.nodes)    #inizializza ogni vertice come singolo albero
    mstweight = 0
    father = []
    rank = []
    cheapest = []
    edgesList = graphEdges(graph)  #lista con gli archi del grafo
    for i in range(len(graph.nodes)):
      father.append(i)              #lista contenente tutti i vertici
      rank.append(0)                #Gli alberi con rank inizializzato a 0
      cheapest = [-1] * len(graph.nodes)  #inizializzo la lista degli archi meno
    while trees > 1:                                               #costosi a -1
      for i in range(len(edgesList)):
        head,tail,weight = edgesList[i]          #assegno una variabile per ogni
        value1 = find(father, head)     #elemento dell'arco in posizione i-esima
        value2 = find(father , tail)                     #contenuto in edgesList
        if value1 != value2:
          if cheapest[value1] == -1 or cheapest[value1][2] > weight :
            cheapest[value1] = [head , tail ,weight]
          if cheapest[value2] == -1 or cheapest[value2][2] > weight :
            cheapest[value2] = [head , tail ,weight]
      for node in range(len(graph.nodes)):
        if cheapest[node] != -1:
          head,tail,weight = cheapest[node]      #assegno una variabile per ogni
          value1 = find(father, head)  #elemento dell'arco contenuto in cheapest
          value2 = find(father ,tail)                         #in posizione node
          if value1 != value2 :
            mstweight += weight         #aumenta il peso del contatore mst
            union(father, rank, value1, value2) #super vertice
            mstlist.append((head,tail,weight))
            #print ("\nL'arco %d-%d con ampiezza %.*f è incluso nel mst"
            #% (head, tail, 16, weight)) #prende le 16 cifre decimali del peso
            trees = trees - 1
      cheapest = [-1] * len(graph.nodes)
    return mstweight,mstlist



if __name__ == "__main__":
    _args = _parseargs()
    nodes = _args.nodi
    edges = _args.archi
    maxWeight = _args.pesoMassimo
    funcName = _args.nomeFunzione
    print('Il Grafo\n')
    g = BGR(nodes,edges,maxWeight,funcName)


    print("\n Algoritmo di Boruvka :")
    cProfile.run('w1, mst1 = boruvka(g)','statisticheBoruvka')
    print("\nIl peso totale del mst è %.*f\n"%(16, w1))
    print("\nGli archi che compongono il Minimo Albero Ricoprente sono: \n")
    print(mst1)
    p = pstats.Stats('statisticheBoruvka')
    p.strip_dirs().sort_stats('time').print_stats()


    print("\n Algoritmo di Kruskal :")
    cProfile.run('w2, mst2 = MST.kruskal(g)','statisticheKruskal')
    print("\nIl peso totale del mst è %.*f\n"%(16, w2))
    print("\nGli archi che compongono il Minimo Albero Ricoprente sono:\n")
    print([str(item) for item in mst2])
    p = pstats.Stats('statisticheKruskal')
    p.strip_dirs().sort_stats('time').print_stats()


    print("\n Algoritmo di Prim :")
    cProfile.run('w3, mst3 = MST.prim(g)','statistichePrim')
    print("\nIl peso totale del mst è %.*f\n"%(16, w3))
    bfs = mst3.BFS()
    print("BFS sul mst prodotto:")
    print([str(item) for item in bfs])
    p = pstats.Stats('statistichePrim')
    p.strip_dirs().sort_stats('time').print_stats()

    if(w1 == w2) and (w1 == w3):
        print("Computato stesso peso dai 3 algoritmi.")
    else:
        print("Error! I tre algoritmi tornano un peso totale differente!")