Chemin dans un réseau nodal

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...
Code:

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]
Je souhaite en d'autres termes comprendre comment fonctionne l'algo afin d'obtenir ceci:

Code:

[[3,7,4,9],[3,4,4,9],[3,4,6,9]]

Merci à celui ou celle qui saura m'expliquer!

Ju

PS: J'ai bien entendu essayé par moi meme de résoudre mon problem.

Salut,
L'algorithme original fonctionne très bien.
La modification que vous avez apporte ici:

Code:

1
2
3
4
5
6
7
8
9
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 []

"casse" la liste de listes.

- W

Merci beaucoup Wiztricks,

J'étais passé complètement à côté... Je cherchais la solution du côté de la construction de la liste et non de son "renvoi".
Code:

1 2 if start == end: return [path]
Merci encore d'avoir pris le temps de me répondre.

Ju