### Importation des modules ###
from pylab import *

from tkinter import *


### Partie programmation de L'ACM par l'algorithme de KRUSKAL ###



def Ajout(L,M) :
    """ ajoute les éléments de M à L sans redondance """
    return L+[x for x in M if not(x in L)]
    

def Prive(L,M) :
    """ retourne la liste L privée de M """
    return [x for x in L if not(x in M)]
          
    
        
    
def Omega(a) :
    """ fonction de poids pour l'arête A """
    return sqrt((a[0][0]-a[1][0])**2+(a[0][1]-a[1][1])**2)


def Tri_Rapide(L,F) :
    """ tri récursivement la liste L via la fonction F """
    if L==[] :
        return []
    else :
        return Tri_Rapide([x for x in L[1:] if F(x)<F(L[0])],F) +[L[0]]+Tri_Rapide([x for x in L[1:] if F(x)>=F(L[0])],F)

def Min_Dehors(L) :
    """ retourne le plus petit entier n>0 tel que n est hors de L """
    k=1
    while k in L :
        k+=1
    return k



def Algo_Kruskal(Sommets,Aretes) :
    """ implémente la recherche de l'ACM en testant les composantes connexes par une numérotation """
    A=Tri_Rapide(Aretes,Omega)    
    ## tri par arêtes de poids croissant
    Comp_Connexes=[[s,0] for s in Sommets]
    ## numérotation nulle par défaut
    S_Temp=[]
    A_Temp=[]
    j=0
    while  [c[1] for c in Comp_Connexes if c[1]!=1]!=[] :   
    # tant que tous les sommets ne sont pas marqués de la composante connexe 1 ...
        Test=False #test d'ajout 
        a=A[j]
        index_a=[k for k in range(len(Comp_Connexes)) if Comp_Connexes[k][0] in a] 
        numeros_a=[Comp_Connexes[k][1] for k in index_a]
        numero_supp=Min_Dehors([c[1] for c in Comp_Connexes])
        if numeros_a==[0,0] : # deux sommets non marqués
            Test=True
            for k in index_a :
                Comp_Connexes[k][1]=numero_supp # création d'une nlle composante connexe
        elif 0 in numeros_a : # un seul sommet non marqué
            Test=True
            if numeros_a[0]==0 : #premier sommet non marqué
                Comp_Connexes[index_a[0]][1]=Comp_Connexes[index_a[1]][1] #rattachement à la composante connexe
            else  : #second sommet non marqué
                Comp_Connexes[index_a[1]][1]=Comp_Connexes[index_a[0]][1] #rattachement à la composante connexe
        elif numeros_a[0]!=numeros_a[1] : #deux sommets marqués dans deux composantes connexes différentes
            Test=True
            numero_mini,numero_maxi=min(numeros_a),max(numeros_a)
            for c in Comp_Connexes :
                if c[1]==numero_maxi :
                    c[1]=numero_mini
                    
                #harmonisation des deux composantes connexes par le numéro minimal
        ### pas de else correspondant à deux sommets appartenant à une même composante connexe : on laisse tomber
        if Test :
            S_Temp=Ajout(S_Temp,a)
            A_Temp.append(a)
        j+=1 
            
        
    return [S_Temp,A_Temp]


### Partie programmation de L'ACM par l'algorithme de PRIM ###
# fonctions Prive et Omega déjà implémentées

def Algo_Prim(Sommets,Aretes) :
    """ implémente l'algorithme de Prim à partir du premier sommet """
    S_Temp=[Sommets[0]]
    A_Temp=[]
    while len(S_Temp) !=len(Sommets) :
        
        aretes_Temp=[]
        for s in S_Temp :
            for t in Prive(Sommets,S_Temp) :
                if [s,t] in Aretes or [t,s] in Aretes : # aretes non orientées
                    aretes_Temp.append([s,t]) # mise en mémoire [s,t]
                # aretes_Temp contient toutes les arêtes reliant un sommet marqué avec un sommet non encore marqué
        val_Temp,arete_mini=Omega(aretes_Temp[0]),aretes_Temp[0] # initialisation du poids minimal
        for a in aretes_Temp[1:] :
            if  Omega(a)<val_Temp :
                val_Temp,arete_mini=Omega(a.copy()),a.copy()
        # arete_mini est la meilleure arête 
        A_Temp.append(arete_mini)
        S_Temp.append(arete_mini[1])
                
    return [S_Temp,A_Temp]


### Interface graphique



rayon=15 ### rayon des disques autour des sommets
Sommets,Aretes=[],[]
compteur=0


def Graphe() :
    global Sommets,Aretes,compteur
    
    canevas.bind("<Button-1>",construire_sommets)
    canevas.bind("<Button-3>",construire_aretes)


flag=1

### pour ne créer qu'une seule fois le widget 'calcul_ACM'

def construire_sommets(event) :
    global Sommets,Aretes,compteur,flag,bouton_ACM_Kruskal,bouton_ACM_Prim
    x,y=event.x,event.y
    
    if Test_Debordement([M[0] for M in Sommets],[x,y]) == [] :
        ### si le clic ne déborde pas sur un sommet existant
        Sommets.append([[x,y],compteur])
        canevas.create_oval(x-rayon,y-rayon,x+rayon,y+rayon,fill='#BE81F7')
        canevas.create_text(x,y,text=str(compteur),font='bold',fill='black')
        
        #Sommets est une liste dont les occurrences sont ds listes dont voici les objets : 
        #[0] : sommet
        #[1] : numéro du sommet
        
        compteur+=1
        
        if flag  :
            ### la première fois que l'on rencontre cette ligne
            bouton_ACM_Prim = Button(fenetre, text ="ACM par PRIM", command =recherche_Prim)
            bouton_ACM_Prim.pack(side=RIGHT, padx =3, pady =3)
            
            bouton_ACM_Kruskal = Button(fenetre, text ="ACM par KRUSKAL", command =recherche_Kruskal)
            bouton_ACM_Kruskal.pack(side=RIGHT, padx =3, pady =3)
            flag=0
            ### on ne met ce bouton qu'une seule fois

def Test_Debordement(sommets,point) :
    global Sommets,Aretes,compteur
    Test=[]
    for S in sommets :
        if (S[0]-point[0])**2+ (S[1]-point[1])**2 <1600 :
            Test=S
            break
    return Test
    ### Soit Test=[], auquel cas pas de débordement, soit Test=S$ auquel débordement
    ### avec le sommet S
    
compteur_Temp,L_Temp=0,[]

### pour comptabiliser deux clics convenables et tracer l'arête entre les deux


def construire_aretes(event) :
    global Sommets,Aretes,compteur,compteur_Temp,L_Temp,s_Temp1,s_Temp2,flag
    x,y=event.x,event.y
    
    s=Test_Debordement([M[0] for M in Sommets],[x,y])
    if s!=[] and compteur_Temp==0 :
        ### si on a empiètement sur l'un des sommets et premier clic
        s_Temp1=canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#F7FE2E')
        L_Temp.append(s)
        ### mise en mémoire du sommet 
        compteur_Temp+=1
        construire_aretes
        
    if s!=[] and compteur_Temp==1 and s!=L_Temp[0] :
        ### on vient de cliquer sur un deuxième sommet
        ### si on a empiètement sur l'un des autres sommets et second clic
        s_Temp2=canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#F5A9A9')
        fenetre.update()
        L_Temp.append(s)
        Trace_Arete(L_Temp[0],L_Temp[1])
        fenetre.after(300)
        canevas.delete(s_Temp1)
        canevas.delete(s_Temp2)
        fenetre.update()
        
        index_Temp=0
        compteur_index=0
        k=0
        Arete_Orientee=[]
        
        while compteur_index !=2 :
            if Sommets[k][0] in L_Temp  :
                ### [k] est l'index du premier sommet cliqué
                compteur_index+=1
                Arete_Orientee.append(Sommets[k][0])
                ### mise en mémoire du sommet_père portant le plus petit numéro
            k+=1
            ### on passe à l'index suivant
        
        if not(Arete_Orientee in Aretes) :
            Aretes.append(Arete_Orientee)

        ### on met en mémoire l'arête orientée crééeet 
        
        compteur_Temp,L_Temp=0,[]
        ### pour pouvoir recommencer les click
        
def inutile(event) :
    1   

               

def recherche_Kruskal() :
    global Sommets,Aretes
    canevas.bind("<Button-1>",inutile)
    canevas.bind("<Button-3>",inutile)
    bouton_graphe.destroy()

    Calcul_ACM=Algo_Kruskal([s[0] for s in Sommets],Aretes)
    Sommets_Temp=Calcul_ACM[0]
    Aretes_Marquees=Calcul_ACM[1]
    Sommets_Marques=[]
    
    while len(Sommets_Marques) != len(Sommets_Temp) :
        for a in Aretes_Marquees :
                Trace_Arete(a[0],a[1],couleur='red')
                for i in range(2) :
                    if not(a[i] in Sommets_Marques) :
                        x,y=a[i]
                        canevas.create_oval(x-rayon,y-rayon,x+rayon,y+rayon,fill='#F7FE2E')
                        for S in Sommets :
                            if S[0]==[x,y] :
                                canevas.create_text(x,y,text=str(S[1]),font='bold',fill='black')
                        Sommets_Marques.append(a[i])
                                
                fenetre.after(1000)
                fenetre.update()
                        
                
                
                
                
        
    fenetre_fin=Tk()
    for k in range(3) :
        texte=Label(fenetre_fin,text="Algorithme de Kruskal terminé !!",font='Arial 20',fg="red")
        texte.pack()
        fenetre_fin.after(300)
        fenetre_fin.update()
        texte.destroy()
        fenetre_fin.after(200)
        fenetre_fin.update()
    
    texte=Label(fenetre_fin,text="Algorithme de Kruskal terminé !!",font='Arial 20',fg="red")  
    texte.pack ()         
    b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit)
    b.pack(side =BOTTOM)
    fenetre_fin.mainloop()
    fenetre_fin.destroy()   
                
                
def recherche_Prim() :
    global Sommets,Aretes
    canevas.bind("<Button-1>",inutile)
    canevas.bind("<Button-3>",inutile)
    bouton_graphe.destroy()
    
    
    
    
    Calcul_ACM=Algo_Prim([s[0] for s in Sommets],Aretes)
    Sommets_Temp=Calcul_ACM[0]
    Aretes_Marquees=Calcul_ACM[1]
    Sommets_Marques=[]
    
    while len(Sommets_Marques) != len(Sommets_Temp) :
        for a in Aretes_Marquees :
                Trace_Arete(a[0],a[1],couleur='#00FF00')
                for i in range(2) :
                    if not(a[i] in Sommets_Marques) :
                        x,y=a[i]
                        canevas.create_oval(x-rayon,y-rayon,x+rayon,y+rayon,fill='#F7D358')
                        for S in Sommets :
                            if S[0]==[x,y] :
                                canevas.create_text(x,y,text=str(S[1]),font='bold',fill='black')
                        Sommets_Marques.append(a[i])
                                
                fenetre.after(1000)
                fenetre.update()
                        
    fenetre_fin=Tk()
    for k in range(3) :
        texte=Label(fenetre_fin,text="Algorithme de Prim terminé !!",font='Arial 20',fg="red")
        texte.pack()
        fenetre_fin.after(300)
        fenetre_fin.update()
        texte.destroy()
        fenetre_fin.after(200)
        fenetre_fin.update()
    
    texte=Label(fenetre_fin,text="Algorithme de Prim terminé !!",font='Arial 20',fg="red")  
    texte.pack ()         
    b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit)
    b.pack(side =BOTTOM)
    fenetre_fin.mainloop()
    fenetre_fin.destroy()   
                
                
                
                
                
                
def Trace_Arete(M,N,couleur='blue') :
    """couleur bleue par défaut, on changera la couleur lors du parcours dans le graphe """
    norme=((M[0]-N[0])**2+(M[1]-N[1])**2)**(0.5)
    Ligne=[[M[0]+rayon*(N[0]-M[0])/norme, M[1]+rayon*(N[1]-M[1])/norme],
    [N[0]-rayon*(N[0]-M[0])/norme,N[1]-rayon*(N[1]-M[1])/norme]]
    return canevas.create_line(Ligne[0][0],Ligne[0][1],Ligne[1][0],Ligne[1][1],width=4,fill=couleur)
    
     
### Interface

Taille_largeur=800
Taille_hauteur=450
fenetre = Tk()
titre=Label(fenetre,text="La recherche de l'arbre couvrant minimal par l'algorithme de Kruskal ou Prim",fg="red",font="Arial 16 italic")
titre.pack(side=TOP)
canevas = Canvas(fenetre, width =Taille_largeur, height =Taille_hauteur, bg ='#A9F5F2')

    
canevas.pack(side =TOP, padx =5, pady =5)

bouton_quitter= Button(fenetre, text="Quitter", command=fenetre.quit)
bouton_quitter.pack(side=RIGHT)

bouton_graphe= Button(fenetre, text="Construire le graphe", command=Graphe)
bouton_graphe.pack(side=RIGHT)


fenetre.mainloop()
fenetre.destroy()