# -*- coding: utf-8 -*-
"""
Created on Fri Jul 14 20:52:09 2017

@author: domps
"""

#  Résolution du pb de l'arbre couvrant minimal.
# Cf livre Founier page 52.
# Je me place dans le cas où la liste des aretes
# n'est pas triée, d'où l'utilité de la fonction
# trouve_arete_mini.
# voir aussi livre Gondran page 175.
# Ca a l'air de marcher !!!


# Prend la liste de listes d'adjaccence
# d'un graphe valué non orienté.
# Renvoie la liste des arretes avec 
# leurs poids x.
# Une arête est représentée par un tuple (depart, arrivee, valeur)
# comme recommandé dans Fournier page 55 et 36
def liste_adjacence_vers_liste_aretes(L) :
    L_aretes = []
    n = len(L)
    for i in range(n) :
        info_voisins = L[i]
        for a in info_voisins :
            j, v = a[0], a[1] # j est un voisin, v la valeur de l'arête
            if j >= i : # pour ne pas les compter deux fois
                L_aretes.append((i, j, v))
    return L_aretes



# renvoie une arete de longueur minimale dans un
# ensemble d'arete F du type décrit plus haut.
def trouve_arete_mini(F) :
    v_min = float('inf')
    for arete in F :
        v = arete[2]
        if v < v_min :
            arete_choisie = arete
            v_min = v
    return arete_choisie
        

    



# détermine si l'ajout de l'arête 
# fait apparaître un cycle. 
# Dans la négative, on fusionne les 
# composantes cycliques des deux extrémités
# de l'arête en leur attribuant le même marqueur.
#def introduit_un_cycle_ou_fusion(arete, marqueur) :
#        i, j = arete[0], arete[1]  
#        if marqueur[i] ==  marqueur[j] : # ils sont dans la même composante connexe
#            return True
#        else :
#            if i < j : 
#                m_0 = marqueur[i] # marqueur à garder
#                m_1 = marqueur[j] # marqueur à changer
#            else : 
#                m_0 = marqueur[j]
#                m_1 = marqueur[i]
#            marqueur[:] = [m_0 if x == m_1 else x for x in marqueur]
#            return False
   
def introduit_un_cycle_ou_fusion(arete, marqueur) :
        i, j = arete[0], arete[1]  
        if marqueur[i] ==  marqueur[j] : # ils sont dans la même composante connexe
            return True
        else :
            m_0 = marqueur[i] # marqueur à garder
            m_1 = marqueur[j] # marqueur à changer
            marqueur[:] = [m_0 if x == m_1 else x for x in marqueur]
            return False



     
# S'applique à un graphe.
# Il est plus pratique de le décrire par
# ses aretes, mais on a aussi besoin de
# ses sommets pour gerer la cyclicité.
# Finalement, on a desoin des deux 
# et il semble arbitraire de choisir soit
# les listes d'ajacence, soit la liste des aretes.
# J'ai choisi de prendre en entrée la liste d'adjacence
# On pourrait aussi prendre en argument la liste des sommets
# et la liste des arêtes, ce qui est la définition usuelle d'un graphe.    
def Kruskal(L_adjacence) :   
    n = len(L_adjacence)
    F = liste_adjacence_vers_liste_aretes(L_adjacence)
    A = []
    marqueur = [i for i in range(n)] # Pour dire à quelle composant connexe chaque sommet appartient    
    while len(A) < n - 1 : # l'acm contient n-1 arêtes
        arete = trouve_arete_mini(F)
        print('On selectionne', arete)
        F.remove(arete)
        test_cycle = introduit_un_cycle_ou_fusion(arete, marqueur)
        if test_cycle :
            print('On rejette ', arete, ' qui formerait un cycle') # pour info
        else :
            A.append(arete)          
        print('marqueur', marqueur)
    return A # On renvoie la listes des aretes retenues. 
   

                
        
# Quand un graphe est décrit par la liste
# de ses aretes, on n'a pas directement
# son nombre de sommets. On en aura pourtant
# besoin dans l'algo de Kruskal.
# Ce code naÏf est peu efficace à cause des << in >>.
# On doit pouvoir faire mieux pour un graphe connexe.    
def cherche_sommets(F) :
    n = 0
    A = []
    for a in F :
        i, j = a[1], a[0] # on doit traiter i et j
        if i not in A : # car certains noeuds peuvent
            A.append(i) # etre des feuilles
            n +=1
        if j not in A :
            A.append(j)
            n += 1
    return n, A    
    
    
    

#    
#  LISTES D'ADJACENCES POUR DES EXEMPLE
#    
# Ex 4 page 55 livre Gondran
L_adj_4 = [[(1,3),(2,10)],[(0,3),(2,6),(3,2),(4,7),(5,4)],
        [(0,10),(1,6),(5,3)],[(1,2),(4,1)],[(1,7),(3,1),(5,2)],[(1,4),(2,3),(4,2)]]
L_are_4 = liste_adjacence_vers_liste_aretes(L_adj_4)


# TD de Laurent sur Dijkstra
L_adj_TD = [[(1,2),(2,4),(3,1)],[(3,1),(5,2)],[(3,1),(4,3)],[(2,1),(5,2),(6,2)],
            [(0,2),(6,1),(8,3)],[],[(4,2),(9,2)],
             [(3,2),(5,1),(6,2),(9,2)],[(6,1),(9,2)],
              [(6,1)]]      
L_are_TD = liste_adjacence_vers_liste_aretes(L_adj_TD)  

# Fournier page 53 avec villes de France
# 0 = Lille, 1 = Brest, 2 = Paris, etc
L_adj_villes = [[(1,725),(2,222),(3,522)],[(0,725),(2,596),(4,623)],
                [(1,596),(0,222),(3,490),(4,583),(5,932),(6,857)],
                 [(0,522),(2,490),(5,804)],[(1,623),(2,583),(6,451)],
                  [(2,932),(3,804),(6,476)],
                   [(4,451),(2,857),(5,476)]]
L_are_villes = liste_adjacence_vers_liste_aretes(L_adj_villes)


###  APPLICATIONS
acm_4 = Kruskal(L_adj_4)
acm_TD = Kruskal(L_adj_TD)
acm_villes = Kruskal(L_adj_villes)