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]))
        # ajout pour avoir le chemin le plus court, on pondère chaque chemin par le nombre de sommet qu'il contient
        result = []

        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:
                    e = path + [i]
                    result.append([len(e), e])
                    chemins = True
                else:
                    pile.append((i, path + [i]))

        if chemins:
            result.sort(key=lambda col:col[0])
            print("\nListe des chemins de '"+start+"' vers '"+end+"' : ")
            for i in result:
                print('Chemin de longueur',i[0]-1)
                print(i[1])
        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()

# ligne 1
G.addArete('S1-1', 'S2-1')
G.addArete('S1-2', 'S1-3')
G.addArete('S1-3', 'S1-4')
G.addArete('S1-4', 'S2-4')
G.addArete('S1-5', 'S1-6')
G.addArete('S1-6', 'S2-6')
G.addArete('S1-7', 'S1-8')
G.addArete('S1-7', 'S2-7')
G.addArete('S1-9', 'S1-10')
G.addArete('S1-10', 'S1-11')
G.addArete('S1-10', 'S2-10')
G.addArete('S1-11', 'S2-11')

#ligne 2
G.addArete('S2-1', 'S2-2')
G.addArete('S2-2', 'S2-3')
G.addArete('S2-3', 'S3-3')
G.addArete('S2-4', 'S2-5')
G.addArete('S2-5', 'S2-6')
G.addArete('S2-6', 'S3-6')
G.addArete('S2-7', 'S2-8')
G.addArete('S2-8', 'S3-8')
G.addArete('S2-9', 'S2-10')
G.addArete('S2-9', 'S3-9')
G.addArete('S2-10', 'S3-10')
G.addArete('S2-11', 'S3-11')

# ligne 3
G.addArete('S3-1', 'S4-1')
G.addArete('S3-2', 'S3-3')
G.addArete('S3-2', 'S4-2')
G.addArete('S3-3', 'S4-3')
G.addArete('S3-4', 'S3-5')
G.addArete('S3-4', 'S4-5')
G.addArete('S3-5', 'S3-6')
G.addArete('S3-6', 'S3-7')
G.addArete('S3-7', 'S4-7')
G.addArete('S3-8', 'S3-9')
G.addArete('S3-8', 'S4-8')
G.addArete('S3-9', 'S3-10')
G.addArete('S3-9', 'S4-9')
G.addArete('S3-11', 'S4-11')

# ligne 4
G.addArete('S4-1', 'S4-2')
G.addArete('S4-2', 'S4-3')
G.addArete('S4-3', 'S4-4')
G.addArete('S4-4', 'S4-5')
G.addArete('S4-5', 'S5-5')
G.addArete('S4-6', 'S4-7')
G.addArete('S4-6', 'S5-6')
G.addArete('S4-8', 'S5-8')
G.addArete('S4-9', 'S5-9')
G.addArete('S4-10', 'S4-11')
G.addArete('S4-10', 'S5-10')

# ligne 5
G.addArete('S5-1', 'S5-2')
G.addArete('S5-1', 'S6-1')
G.addArete('S5-2', 'S5-3')
G.addArete('S5-3', 'S5-4')
G.addArete('S5-3', 'S6-3')
G.addArete('S5-4', 'S5-5')
G.addArete('S5-4', 'S6-4')
G.addArete('S5-6', 'S5-7')
G.addArete('S5-6', 'S6-6')
G.addArete('S5-7', 'S6-7')
G.addArete('S5-8', 'S6-8')
G.addArete('S5-10', 'S5-11')
G.addArete('S5-10', 'S6-10')
G.addArete('S5-11', 'S6-11')

# ligne 6
G.addArete('S6-1', 'S6-2')
G.addArete('S6-3', 'S7-3')
G.addArete('S6-4', 'S6-5')
G.addArete('S6-5', 'S6-6')
G.addArete('S6-6', 'S6-7')
G.addArete('S6-6', 'S7-6')
G.addArete('S6-8', 'S7-8')
G.addArete('S6-9', 'S7-9')
G.addArete('S6-10', 'S6-11')
G.addArete('S6-11', 'S7-11')

# ligne 7
G.addArete('S7-1', 'S7-2')
G.addArete('S7-1', 'S8-1')
G.addArete('S7-2', 'S7-3')
G.addArete('S7-3', 'S7-4')
G.addArete('S7-5', 'S7-6')
G.addArete('S7-6', 'S7-7')
G.addArete('S7-7', 'S7-8')
G.addArete('S7-7', 'S8-7')
G.addArete('S7-8', 'S8-8')
G.addArete('S7-9', 'S7-10')
G.addArete('S7-9', 'S8-9')
G.addArete('S7-10', 'S7-11')

# ligne 8
G.addArete('S8-1', 'S8-2')
G.addArete('S8-3', 'S8-4')
G.addArete('S8-4', 'S9-4')
G.addArete('S8-5', 'S8-6')
G.addArete('S8-5', 'S9-5')
G.addArete('S8-6', 'S8-7')
G.addArete('S8-7', 'S8-8')
G.addArete('S8-9', 'S8-10')
G.addArete('S8-10', 'S9-10')
G.addArete('S8-11', 'S9-11')

# ligne 9
G.addArete('S9-1', 'S9-2')
G.addArete('S9-1', 'S10-1')
G.addArete('S9-2', 'S9-3')
G.addArete('S9-3', 'S9-4')
G.addArete('S9-4', 'S9-5')
G.addArete('S9-5', 'S9-6')
G.addArete('S9-6', 'S9-7')
G.addArete('S9-7', 'S9-8')
G.addArete('S9-9', 'S10-9')
G.addArete('S9-10', 'S10-10')
G.addArete('S9-11', 'S10-11')

# ligne 10
G.addArete('S10-1', 'S11-1')
G.addArete('S10-2', 'S10-3')
G.addArete('S10-2', 'S11-2')
G.addArete('S10-3', 'S11-3')
G.addArete('S10-4', 'S10-5')
G.addArete('S10-5', 'S10-6')
G.addArete('S10-6', 'S10-7')
G.addArete('S10-6', 'S11-6')
G.addArete('S10-8', 'S10-9')
G.addArete('S10-8', 'S11-8')
G.addArete('S10-9', 'S11-9')
G.addArete('S10-10', 'S10-11')


# ligne 11
G.addArete('S11-1', 'S11-2')
G.addArete('S11-2', 'S11-3')
G.addArete('S11-3', 'S11-4')
G.addArete('S11-4', 'S11-5')
G.addArete('S11-5', 'S11-6')
G.addArete('S11-6', 'S11-7')
G.addArete('S11-7', 'S11-8')
G.addArete('S11-9', 'S11-10')
G.addArete('S11-10', 'S11-11')

""" chemins """

G.chemins("S1-1","S11-11")