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

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

### Comparaison des temps d'exécution ###

def Graphe_G_n(n) :
    """ construit le graphe de sommets dans [0,n-1]**2 et dont les arêtes sont de longueur 1 """
    
    Sommets=[[i,j] for i in range(n) for j in range(n) ]
    Aretes=[[s,t]  for s in Sommets for t in Sommets if (abs(s[0]-t[0])+abs(s[1]-t[1])==1 and s[0]+s[1]<t[0]+t[1])] 
    return [Sommets,Aretes]

def Traces_Temps_Calculs(n) :
    LX=list(range(2,n))
    LY_Kruskal,LY_Prim=[],[]
    for k in LX :
        G_n=Graphe_G_n(k)
        t_0=time.clock()
        Algo_Kruskal(G_n[0],G_n[1])
        t_1=time.clock()
        LY_Kruskal.append(log(t_1-t_0))
        t_2=time.clock()
        Algo_Prim(G_n[0],G_n[1])
        t_3=time.clock()
        LY_Prim.append(log(t_3-t_2))
    figure()
    plot(LX,LY_Kruskal,color='red',marker="o")
    plot(LX,LY_Prim,color="blue",marker="o")
    grid()
    xlabel('taille du graphe')
    ylabel("temps d'exécution")
    legend(('Kruskal','Prim'),'upper center',shadow=True)
    show()
    
    
Traces_Temps_Calculs(9)

# Commentaire : avant n=5, l'algorithme Prim est un peu meilleur et la tendance s'inverse après n=5.