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