Bonjour tout le monde,
Je me suis intéréssé dans le cadre d'un projet personnel à la notion de "graph" telle que présenté ici:
http://www.python.org/doc/essays/graphs.html
Je me suis amusé à créer un "réseau" de noeuds reliés entre eux (une seule direction possible, pas de boucle). Le lien ci-dessus présente une méthode pour lister de façon recursive tous les chemins possibles entre deux noeuds.
Mon soucis c'est que je ne parviens pas à comprendre pleinement l'algorithme employé. Dans l'exemple ci-dessous je créé un graph simple de 10 noeuds et je cherche à connaitre l'essemble des chemins possible entre deux d'entre eux. Le resultat obtenu est correcte, cependant je souhaite sortir non pas une unique liste de tout les noeuds parcouru de tout les chemins possible, mais une liste contenant autant de sous-liste qu'il y a de chemins possibles...
Je souhaite en d'autres termes comprendre comment fonctionne l'algo afin d'obtenir ceci:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 class Node(object): """ Define a node """ def __init__(self, value=None): self.value = value def findpaths(graph,start,end,path=[]): """ Get a list of all paths between a start and end node Credit: Guido Van Rossum """ path = path + [start] if start == end: return path if not graph.has_key(start): return [] paths = [] for node in graph[start]: if node not in path: newpaths = findpaths(graph,node,end,path) for newpath in newpaths: paths.append(newpath) return paths # Nodes n1 = Node(3) n2 = Node(7) n3 = Node(4) n4 = Node(2) n5 = Node(4) n6 = Node(6) n7 = Node(8) n8 = Node(5) n9 = Node(9) n10 = Node(3) graph = {n1:[n2,n3], n2:[n4,n5], n3:[n5,n6], n4:[n7,n8], n5:[n8,n9], n6:[n9,n10], n7:[], n8:[], n9:[], n10:[]} paths = findpaths(graph,n1,n9) print [node.value for node in paths] >>[3,7,4,9,3,4,4,9,3,4,6,9]
Merci à celui ou celle qui saura m'expliquer!
Code : Sélectionner tout - Visualiser dans une fenêtre à part [[3,7,4,9],[3,4,4,9],[3,4,6,9]]
Ju
PS: J'ai bien entendu essayé par moi meme de résoudre mon problem.
Partager