#utilitaire pour theorie des graphes


#constantes diverses 
largeur = 700
hauteur = 450
Nb, Echx, Echy = 20, 25, 25
NbVilles, NbRoutes = 0, 0


#modules a importer
from tkinter import * #comment echapper a ca
from time import sleep
from random import *
Fen = Tk() #fenetre generale
#canevas de visalisation du graphe
Can = Canvas(Fen, width=largeur, height=hauteur, bg="azure2")
Can.grid(row=0,column=0)
#canevas de visualisation de la matrice d'adjacence
Matrix = Canvas(Fen, width=(Nb+1)*Echx, height=hauteur, bg="Grey91")
Matrix.grid(row=0,column=1)
Matrix.create_text(15,hauteur-20,anchor=W,text="Pour creer (ou renforcer) une route, cliquez sur sa case sur le tableau ci-dessus.")
Matrix.create_text(15,hauteur-10,anchor=W,text="Pour effacer (ou diminuer) une route, choisissez aussi sa case, mais utilisez clic droit.")


#listes diverses
Villes, Routes, Tab, M = [], [], [], []

 
def VilleNouvelle() :
    #pour chaque creation de ville, on agrandit la matrice d'adjacence et on l'affiche sur Matrix
    global NbVilles
    NbVilles +=1
    Matrix.create_rectangle(2,NbVilles*Echy+2,Echx+2,(NbVilles+1)*Echy+2)
    for k in range(NbVilles) :
        Matrix.create_rectangle((NbVilles)*Echx+2,k*Echy+2,(NbVilles+1)*Echx+2,(k+1)*Echy+2)
    Matrix.create_rectangle((NbVilles)*Echx+2,(k+1)*Echy+2,(NbVilles+1)*Echx+2,(k+2)*Echy+2,fill="DarkGrey")    
    Matrix.create_text((0.5+NbVilles)*Echx+2,Echy/2+2,text=chr(NbVilles+64))    
    Matrix.create_text(Echx/2+2,(0.5+NbVilles)*Echy+2,text=chr(NbVilles+64))
    for ligne in Tab :
        ligne.append(None)
    Tab.append([None]*NbVilles)
    for ligne in M :
        ligne.append(0)
    M.append([0]*NbVilles)
    for ligne in Routes :
        ligne.append(None)
    Routes.append([None]*NbVilles)


#classes diverses d'objets    
class ville :
    #une ville est un sommet du graphe
    #avec abscisse et ordonnee
    #plus un rayon et une couleur (par defaut) pour la visualisation par l'objet dessin
    def __init__(self, x=10, y=10, rayon=10, distance=0,couleur = "LightBlue") :
        global NbVilles
        self.x, self.y = x, y #coordonnees initiales
        self.rayon = rayon
        self.couleur=couleur
        self.index=NbVilles
        self.distance=distance
        VilleNouvelle()
        self.dessin=Can.create_oval(self.x-self.rayon, self.y-self.rayon, self.x+self.rayon, self.y+self.rayon, fill="White")
        self.info  = Can.create_text(self.x, self.y, text=chr(self.index+65), fill="Black")
        self.infoD = Can.create_text(self.x+10, self.y-10, text="0", fill="Brown")
        
        Can.update()
        
class route :
    #une route est une arete (orientee), qui relie donc deux villes : depart et arrivee
    #plus une couleur et une information supplementaire eventuelle
    def __init__(self, depart, arrivee, epaisseur=2, couleur ="LightGrey",valeur=1):
        self.depart=depart
        self.arrivee=arrivee
        self.epaisseur=epaisseur
        self.valeur=valeur
        self.couleur=couleur
        self.dessin=Can.create_line(depart.x,depart.y,arrivee.x,arrivee.y,width=self.epaisseur,fill=self.couleur)
        self.info  =Can.create_text((depart.x+arrivee.x)/2,(depart.y+arrivee.y)/2,text=self.valeur)
        Can.update()

def CreerVille() :
    Villes.append(ville())
    Message.configure(text="Une nouvelle ville est visible en haut, vous pouvez la deplacer avec la souris.")
    
    

CreeVille = Button(Fen, text="Creation d'une nouvelle ville", command=CreerVille)
CreeVille.grid(column=0,row=1)
Message = Label(Fen, text="Utilitaire de creation de graphes.")
Message.grid(column=0,row=2)


#utilitaires du canevas de visualisation du graphe
def MouseDown(event) :
    #quand on clique sur une ville
    global ExisteVille, LaVille, SesRoutesD, SesRoutesA
    x, y = event.x, event.y
    ExisteVille = False
    for i in range(NbVilles) :
        v = Villes[i]
        if abs(v.x-x)<v.rayon and abs(v.y-y)<v.rayon :
            LaVille=v
            ExisteVille = True
            Index=i
    if ExisteVille : #on n'a pas tape dans le vide
        Can.itemconfig(LaVille.dessin, fill="Yellow")
        SesRoutesD, SesRoutesA = [], []
        for j in range(NbVilles) :
            if Index>j and M[Index][j] != 0 :
                SesRoutesD.append(Routes[Index][j])
                Can.itemconfig(Routes[Index][j].dessin,fill="Orange")
            if Index<j and M[j][Index] !=0 :
                SesRoutesA.append(Routes[j][Index])
                Can.itemconfig(Routes[j][Index].dessin,fill="Orange")
        
        
 
def MouseMove(event) :
    #quand on deplace une ville
    xm, ym = event.x, event.y
    PeutBouger = xm<largeur and ym<hauteur and xm>0 and ym>0
    if ExisteVille and PeutBouger :
        dx, dy = xm-LaVille.x, ym-LaVille.y
        Can.move(LaVille.dessin,dx,dy)
        Can.move(LaVille.info,dx,dy)
        Can.move(LaVille.infoD,dx,dy)
        LaVille.x, LaVille.y = xm, ym
        for r in SesRoutesD :
            Can.coords(r.dessin,xm,ym,r.arrivee.x,r.arrivee.y)
            Can.coords(r.info,(r.depart.x+r.arrivee.x)/2,(r.depart.y+r.arrivee.y)/2)
            r.x, r.y = xm, ym
        for r in SesRoutesA :
            Can.coords(r.dessin,r.depart.x,r.depart.y,xm,ym)
            Can.coords(r.info,(r.depart.x+r.arrivee.x)/2,(r.depart.y+r.arrivee.y)/2)
            r.x, r.y = xm, ym

def MouseUp(event) :
    #remise en couleur normale quand on relache
    Can.itemconfig(LaVille.dessin, fill=LaVille.couleur)
    for r in SesRoutesD :
        Can.itemconfig(r.dessin, fill = r.couleur)
    for r in SesRoutesA :
        Can.itemconfig(r.dessin, fill = r.couleur)
    Message.configure(text="")
    
        
#associaition des actions de souris aux procedures
Can.bind("<Button-1>", MouseDown)
Can.bind("<Button1-Motion>", MouseMove)
Can.bind("<Button1-ButtonRelease>", MouseUp)


#creation des routes
def ChoisisRoute(event) :
    x, y = event.x, event.y
    i = (x-2)//Echx-1 #recuperation des index
    j = (y-2)//Echy-1
    i, j = max(i,j), min(i,j) #symetrisation
    if j<i<NbVilles : #verification de la coherence
        if M[i][j]==0 : #cas de la creation d'une route
            print("Creation",i,j)
            M[i][j]+=1#aretes non orientees
            M[j][i]+=1#tableau symetrique
            Routes[i][j]=route(depart=Villes[i],arrivee=Villes[j])
            Tab[i][j]=Matrix.create_text((i+1.5)*Echx+2,(j+1.5)*Echy+2,text="1")
            Tab[j][i]=Matrix.create_text((j+1.5)*Echx+2,(i+1.5)*Echy+2,text="1")
        else : #cas du renforcement d'une route
            M[i][j]+=1
            M[j][i]+=1
            Matrix.itemconfig(Tab[i][j],text=str(M[i][j]))
            Matrix.itemconfig(Tab[j][i],text=str(M[i][j]))
            Routes[i][j].valeur+=1
            Can.itemconfig(Routes[i][j].info,text=str(Routes[i][j].valeur))
            
def DetruisRoute(event) :
    x, y = event.x, event.y
    i = (x-2)//Echx-1 #recuperation des index
    j = (y-2)//Echy-1
    if j<i<NbVilles : #verification de la coherence
        if M[i][j]<2 : #cas de la destruction d'une route
            M[i][j]=0
            M[j][i]=0
            Can.delete(Routes[i][j].dessin)
            Can.delete(Routes[i][j].info)
            Routes[i][j]=None
            Matrix.itemconfig(Tab[i][j],text="")
            Matrix.itemconfig(Tab[j][i],text="")
        else : #cas de l'allegement d'une route
            M[i][j]-=1
            M[j][i]-=1
            Matrix.itemconfig(Tab[i][j],text=str(M[i][j]))
            Matrix.itemconfig(Tab[j][i],text=str(M[i][j]))
            Routes[i][j].valeur-=1
            Can.itemconfig(Routes[i][j].info,text=str(Routes[i][j].valeur))
            
            

Matrix.bind("<Button-1>", ChoisisRoute)
Matrix.bind("<Button-3>", DetruisRoute)

#================================================================================================
#=================================== algorithme de Dijkstra =====================================
def AlgoDijkstra() :
    hauteurD=150
    Dijkstra = Canvas(Fen, width=largeur, height=hauteurD, bg="White")
    Dijkstra.grid(row=3,column=0)
    EchD = 25
    for ligne in M :
        print(ligne)
                                
    #utilitaire classique
    def Voisins(i) :
        #recherche des voisins d'un sommet sur le graphe
        L = []
        for j in range(len(M)) :
            if M[i][j] != 0 :
                L.append(j)
        return(L)


    #utilitaires de visualisation et gestion du tas
    tas=[]
    Dijkstra.create_text(15,10,anchor=W,text="Tas des villes a visiter ")
    for k in range(NbVilles) :
        Dijkstra.create_rectangle(15+k*EchD, 20, 15+(k+1)*EchD, 35)
        Dijkstra.create_rectangle(15+k*EchD, 35, 15+(k+1)*EchD, 50)
    VisuTas0=[Dijkstra.create_text(5+(k+1)*EchD,28,text="",fill="Black") for k in range(NbVilles)]
    VisuTas1=[Dijkstra.create_text(5+(k+1)*EchD,43,text="",fill="Red") for k in range(NbVilles)]

    def PopMin() :
        #extrait l'element du tas dont la variable d'indice 1 est la plus petite
        for k in range(len(tas)-1) :
            if tas[k+1][1]>tas[k][1] :
                tas[k][0], tas[k][1], tas[k+1][0], tas[k+1][1] = tas[k+1][0], tas[k+1][1], tas[k][0], tas[k][1]#echange de type tri-bulle, sur des listes, attention
                Dijkstra.itemconfig(VisuTas0[k],text=chr(tas[k][0]+65))
                Dijkstra.itemconfig(VisuTas1[k],text=str(tas[k][1]))
                Dijkstra.itemconfig(VisuTas0[k+1],text=chr(tas[k+1][0]+65))
                Dijkstra.itemconfig(VisuTas1[k+1],text=str(tas[k+1][1]))
                Dijkstra.update()
                sleep(3)
        choix=tas.pop()
        Dijkstra.itemconfig(VisuTas0[len(tas)],text="")
        Dijkstra.itemconfig(VisuTas1[len(tas)],text="")
        Dijkstra.update()
        
        return(choix)
            
    def AddTas(elt) :
        #ajoute un element au tas et visualise
        tas.append(elt)
        n=len(tas)-1
        Dijkstra.itemconfig(VisuTas0[n],text=chr(elt[0]+65))
        Dijkstra.itemconfig(VisuTas1[n],text=str(elt[1]))
        Dijkstra.update()


    AddTas([0,0]) #on place dans le tas la ville A
    prec=[None]*NbVilles #pour l'instant, personne n'a de predecesseur (même la ville A)
    black=[False]*NbVilles #liste des villes visitees (information booleenne)
    
    dist=[float('inf')]*NbVilles #toutes les villes sont à distance infinie
    dist[0] = 0 #sauf la première
    while len(tas)>0 : #tant ue le tas n'est pas epuise
        Choix = PopMin() #on cherche la ville non visitee la plus proche de la racine A et on la sort de Tas
        Ville, Distance = Choix[0], Choix[1] #on retient de uelleville il s'agit et à uelle distance de la source A elle est
        print("Choix",Choix) #tiens, on affiche
        if not(black[Ville]) : #si la ville 
            black[Ville]=True #on la met à Black
            for Voisin in Voisins(Ville) : #on regarde ses voisins
                Dep, Arr = max(Ville,Voisin), min(Ville,Voisin) #jste pour l'affichage
                Can.itemconfig(Routes[Dep][Arr].dessin,fill="Yellow") #on met la nouvelle route en jaune
                DistanceVoisin = Distance+M[Ville][Voisin] #on calcule la distance pour Voisin si on transite par Ville
                if DistanceVoisin < dist[Voisin] : #si ceci a rapproche la ville Voisin de la source A
                    dist[Voisin] = DistanceVoisin #on actualise la distance
                    prec[Voisin]= Ville #on sait ue pour aller à Voisin, on devra plutôt passer par Ville
                    Can.itemconfig(Villes[Voisin].infoD,text=str(DistanceVoisin)) #on actualise l'affichage de distance à la source
                    Can.update() #oui, TkInter est parfois lourd
                    sleep(3.5) #prenons le temps d'y voir clair
                    AddTas([Voisin, DistanceVoisin]) #on place Voisin dans le Tas
    print(black) #on a fini, on affiche la liste des villes visitees (le graphe n'est peut être pas connexe !)
    print("prec",prec) #information des predecesseurs de chacun
    print("dist",dist) #et de leurs distance à l'origine


BoutonDijkstra=Button(Fen,text="Dijkstra",command=AlgoDijkstra)
BoutonDijkstra.grid(row=2,column=1)
    
Fen.mainloop()