Chemin dans un réseau nodal

**Julien N** · 04/12/2013, 13h20

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 :

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]