from collections import deque

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("\nListe des cycles du graphe :")
                for i in liste_cycles:
                    print(i)
            else:
                print("Il n'y a aucun cycle dans ce graphe.")

    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("\nListe des chemins de '"+start+"' vers '"+end+"' : ")
            for i in liste_chemins:
                print(i)
        else:
            print("Il n'y a aucun chemin allant de '"+start+"' vers '"+end+"'.")

    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("\nParcours en profondeur en partant de '"+start+"' :")
        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("\nParcours en largeur en partant de '"+start+"' :")
        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 """

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')