from collections import deque

""" ------------------------------------------------------------------ """
"""                                                                    """
""" Classe pour graphes non pondérés définis par une liste d'adjacence """
"""                                                                    """
""" -------------------------------------------------------------------"""

class Graphe:
    def __init__(self):
        self.Liste = {}

    def addArete(self, u, v):
        if v not in self.Liste:
            self.Liste[v] = []

        if u not in self.Liste:
            self.Liste[u] = []

        self.Liste[u].append(v)
        self.Liste[v].append(u)

    def cycles(self):
        liste_cycles = []
        for key in self.Liste:
            start = key
            pile = deque()
            pile.append((start, []))

            while pile:
                (S, path) = pile.pop()
                list_nodes = [n for n in self.Liste[S] if n not in path]
                for i in list_nodes:
                    if i == start:
                        liste_cycles.append([start] + path + [i])
                        cycle = True
                    else:
                        pile.append((i, path + [i]))

            if cycle:
                print('\033[31m'+'\nListe des cycles du graphe :'+'\033[30m')
                for i in liste_cycles:
                    print(i)
            else:
                print('\033[31m'+"\nIl n'y a aucun cycle dans ce graphe."+'\033[30m')

    def chemins(self,start,end):
        pile = deque()
        pile.append((start, [start]))
        liste_chemins = []

        while pile:
            (S, path) = pile.pop()
            list_nodes = [n for n in self.Liste[S] if n not in path]
            for i in list_nodes:
                if i == end:
                    liste_chemins.append(path + [i])
                    chemins = True
                else:
                    pile.append((i, path + [i]))

        if chemins:
            print('\033[31m'+'\nListe des chemins de '+start+' vers '+end+' : '+'\033[30m')
            for i in liste_chemins:
                print(i)
        else:
            print('\033[31m'+"\nIl n'y a aucun chemin allant de "+start+" vers "+end+"."+'\033[30m')

    def parcoursProfondeur(self,start):
        sortie = []
        pile = deque()
        pile.append(start)

        while pile:
            S = pile.pop()
            if S not in sortie:
                sortie.append(S)
                non_visites = [n for n in self.Liste[S] if n not in sortie]
                pile.extend(non_visites)

        print('\033[31m'+'\nParcours en profondeur en partant de '+start+' : '+'\033[30m')
        print(sortie)

    def parcoursLargeur(self,start):
        sortie = []
        file = deque()
        file.append(start)

        while file:
            S = file.popleft()
            if S not in sortie:
                sortie.append(S)
                unvisited = [n for n in self.Liste[S] if n not in sortie]
                file.extend(unvisited)

        print('\033[31m'+'\nParcours en largeur en partant de '+start+' : '+'\033[30m')
        print(sortie)

# Définition du graphe

G = Graphe()

G.addArete('A', 'B')
G.addArete('A', 'D')
G.addArete('A', 'E')
G.addArete('C', 'B')
G.addArete('C', 'D')
G.addArete('D', 'E')
G.addArete('E', 'F')
G.addArete('E', 'G')
G.addArete('F', 'G')
G.addArete('G', 'H')

# Affichage du graphe

print('\033[31m'+'Voici le graphe:'+'\033[30m')
for key,value in G.Liste.items():
    print(key,":",value)

# Liste des cycles du graphe

G.cycles()

# Chemins d'un sommet à un autre

G.chemins('A','H')

# Parcours en profondeur

G.parcoursProfondeur('A')

# Parcours en largeur

G.parcoursLargeur('A')


""" ----------------------------------------------------------------- """
"""                                                                   """
""" Classe pour graphes pondérés définis par une matrice de valuation """
"""                                                                   """
""" ------------------------------------------------------------------"""

class GraphePondM:
    def __init__(self):
        self.Liste = []

    def add(self,L):
        self.Liste.append(L)

    def dijkstra(self,s):
        infini = sum( sum( ligne ) for ligne in self.Liste ) + 1
        nb_sommets = len(self.Liste)

        s_connu = { s : [ 0 , [s] ] }
        s_inconnu = { k : [infini , ''] for k in range(nb_sommets) if k != s }

        for next in range(nb_sommets):
            if self.Liste[s][next]:
                s_inconnu[next] = [ self.Liste[s][next] , s ]

        print('\033[31m'+'\nPlus courts chemins de...'+'\033[30m')

        while s_inconnu and any( s_inconnu[k][0] < infini for k in s_inconnu ):
            u = min( s_inconnu , key = s_inconnu.get )
            longueur_u , precedent_u = s_inconnu[u]
            for v in range(nb_sommets):
                if self.Liste[u][v] and v in s_inconnu:
                    d = longueur_u + self.Liste[u][v]
                    if d < s_inconnu[v][0]:
                        s_inconnu[v] = [ d , u ]

            s_connu[u] = [ longueur_u , s_connu[precedent_u][1] + [u] ]
            del s_inconnu[u]
            print('\033[35m'+"Longueur",longueur_u,":"+'\033[30m', ' -> '.join( map( str , s_connu[u][1] ) ) )

        return s_connu

# Exemple d'implémentation d'un graphe orienté par matrice de valuation

G = GraphePondM()
G.add([0 , 8 , 6 , 28 , 5 , 0 , 0 , 0 , 0 ])
G.add([8 , 0 , 9 , 0 , 15 , 0 , 0 , 0 , 0 ])
G.add([6 , 9 , 0 , 13 , 0 , 0 , 0 , 38 , 0 ])
G.add([28 , 0 , 13 , 0 , 14 , 0 , 21 , 17 , 0])
G.add([5 , 15 , 0 , 14 , 0 , 10 , 17 , 0 , 0])
G.add([0 , 0 , 0 , 0 , 10 , 0 , 19 , 0 , 0])
G.add([0 , 0 , 0 , 21 , 17 , 19 , 0 , 5 , 17])
G.add([0 , 0 , 38 , 17 , 0 , 0  ,5  , 0, 16])
G.add([0 , 0 , 0 , 0 , 0 , 0 , 17 , 16  , 0])

G.dijkstra(0) # "0" est le premier sommet
# dans le cas d'une graphe orienté défini par sa matrice de valuation,
# les n sommets sont désignés par des entiers de 0 à n-1

""" --------------------------------------------------------------------- """
"""                                                                       """
""" Classe pour graphes pondérés non définis par une matrice de valuation """
"""                                                                       """
""" ----------------------------------------------------------------------"""

class GraphePond:
    def __init__(self):
        self.Liste = {}

    def add(self,u,v,p):
        if u not in self.Liste:
            self.Liste[u] = { v : p }
        else:
            self.Liste[u][v] = p

    def dijkstra(self,s):
        infini = sum( sum( self.Liste[sommet][i] for i in self.Liste[sommet] ) for sommet in self.Liste ) + 1

        s_connu = {s : [ 0 , [s] ] } # [longueur , plus court chemin]
        s_inconnu = {k : [infini , ''] for k in self.Liste if k != s } # [longueur , précédent]

        for next in self.Liste[s]:
            s_inconnu[next] = [ self.Liste[s][next] , s ]

        print('\033[31m'+"\nPlus courts chemins de..."+'\033[30m')

        while s_inconnu and any( s_inconnu[k][0] < infini for k in s_inconnu ):
            u = min( s_inconnu, key = s_inconnu.get )
            longueur_u  , precedent_u = s_inconnu[u]
            for v in self.Liste[u]:
                if v in s_inconnu:
                    d = longueur_u + self.Liste[u][v]
                    if d < s_inconnu[v][0]:
                        s_inconnu[v] = [d,u]

            s_connu[u] = [ longueur_u , s_connu[ precedent_u ][1] + [u] ]
            del s_inconnu[u]
            print('\033[35m'+"Longueur",longueur_u,": "+'\033[30m'+' -> '.join( s_connu[u][1] ) )

        return s_connu

# définition d'un graphe pondéré par liste d'adjacence

G = GraphePond()

G.add('K','M',4)
G.add('K','E',1)
G.add('M','E',2)
G.add('M','H',2)
G.add('E','M',1)
G.add('E','H',3)
G.add('E','F',1)
G.add('H','F',3)
G.add('F','H',1)
G.add('S','H',2)
G.add('S','F',2)

# Affichage du graphe

print('\033[31m'+'\nVoici le graphe :'+'\033[30m')
for key , value in G.Liste.items():
    print(key , ":" , value)

G.dijkstra('K')