Discussion :

[Julien N]

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]

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

[[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.

[wiztricks]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Julien N]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
if start == end:
    return [path]

Merci encore d'avoir pris le temps de me répondre.


Ju