List of nodes in a (shortest) path

[Lucas Brasilino]

Hi!

I'm starting to play with pygraph and I'm wondering if there is a way to return a the list of nodes
with such path (including starting and ending nodes).

 Since 'shortest_path()' returns the distance between a source node and all other nodes, I'd
like to actually know the path as a list of nodes between two nodes. Some thing like (a simple dumb example just
to depicts what I'm asking):

gr.add_nodes(['1','2','3'])
gr.add_edge(('1','2'))
gr.add_edge(('2','3'))

nodes_path = shortest_path_nodes(gr, '1','3') # graph, source node, destination node
print nodes_path
['1','2','3']

thanks!
Lucas

[Pedro Matiello]

Hello, Lucas.

There's nothing ready for this. Yet, it's not hard to write a function for this yourself. Here's an idea:

1. Call the shortest_path function with the desired graph and source node to retrieve the spanning tree (st):

>>> st, _ = shortest_path(gr, '1')

2. Follow the spanning tree from the target node to the source node. A possible solution:

>>> def path(st, target):

...     if (target is None):

...         return []

...     else:

...         return [target] + path(st, st[target])

... 

>>> path(st, '3')

['3', '2', '1']

This gives you the path backwards, but you can easily call reverse on the list once it's done.

[Lucas Brasilino]

Hi Pedro,

Thanks for the insight.

Lucas.