All shortest paths between two nodes

[Atanas]

Hi,

is there a function that returns *all* shortest paths between two
nodes in a graph? The function networkx.shortest_path(Graph, a, b),
for example, returns just *a* shortest path between nodes a and b -
what I am looking for is a function that returns all the shortest
paths between a and b.

Thanks

[Dan Schult]

There is currently no such function in networkx, but it might not be
too bad to change an existing shortest_path routine to make it
track all possible shortest paths. If you get something working
let us know as we'd be interested in including it.

Dan

[Aric Hagberg]

There is something that *almost* does that: networkx.predecessor().
That returns a dictionary of predecessors in a shortest path starting
at a given node.

For example

In [28]: G=networkx.Graph()

In [29]: G.add_cycle([0,1,2,3])

In [30]: p=networkx.predecessor(G,0) # shortest path starting at 0

In [31]: p
Out[31]: {0: [], 1: [0], 2: [1, 3], 3: [0]}

Then you just need to identify your target (say 2) and follow the
paths back:

In [32]: p[2]
Out[32]: [1, 3] # both one and 3 are on the shortest path

In [33]: p[1] # predecessor of 1 is the source so we are done
Out[33]: [0]

For weighted graphs you can use dijkstra_predecessor_and_distance()
(which returns two dictionaries).

Aric

[Atanas]

Thanks for your answers; I did indeed notice the predecessor function
and was going to implement an all shortest path search function using
it, just wanted to make sure it didn't exist already. I would be
happy to share my code when I'm ready.

Greetings,
Atanas

On Aug 15, 5:52 am, Aric Hagberg <aric.hagb...@gmail.com> wrote:

[Atanas]

Hi,

I implemented a function that returns all shortest paths between two
nodes in an undirected graph. Here is the code, feel free to improve
and include in NetworkX:


def all_shortest_paths(G,a,b):
""" Return a list of all shortest paths in graph G between nodes a
and b """
ret = []
pred = nx.predecessor(G,b)
if not pred.has_key(a): # b is not reachable from a
return []
pth = [[a,0]]
pthlength = 1 # instead of array shortening and appending, which
are relatively
ind = 0 # slow operations, we will just overwrite array
elements at position ind
while ind >= 0:
n,i = pth[ind]
if n == b:
ret.append(map(lambda x:x[0],pth[:ind+1]))
if len(pred[n]) > i:
ind += 1
if ind == pthlength:
pth.append([pred[n][i],0])
pthlength += 1
else:
pth[ind] = [pred[n][i],0]
else:
ind -= 1
if ind >= 0:
pth[ind][1] += 1
return ret

[William Tu]

Hi,

I implement another function that returns all possible paths between
two nodes in a directed graph. Here is the code, feel free to improve
it.

def find_pair_all_path(g, frm_id, to_id, p_list, maxhop):
""" given graph g, and pm_list, create a list for all path
g: graph, limit: the maximum hop count
write all paths from frm_id to to_id at allpath_list
"""
debug = 0
path_list = p_list[:]
if debug: print "from %d to %d path %s" % (frm_id, to_id,
path_list)
if len(path_list) > maxhop:
if debug: print "path too long"
return None
elif len(path_list) == 0:
path_list.append(frm_id)
if to_id in path_list:
if debug: print "path contains loop"
return None

neigh = g.neighbors(frm_id)
if debug: print "\tid: %d neighbot: %s" % (frm_id, neigh)
for n in neigh:
if n == to_id:
if debug: print "found destination:", path_list
found_path_list = path_list[:]
found_path_list.append(to_id)
allpath_list.append(found_path_list)
elif n in path_list:
continue
else:
new_path_list = path_list[:]
new_path_list.append(n)
find_pair_all_path(g, n, to_id, new_path_list, maxhop)
return None

if __name__ == "__main__":
g = nx.complete_graph(40)
print("number of nodes:", g.number_of_nodes())
print("number of edges:", g.number_of_edges())
allpath_list = []
find_pair_all_path(g, 0, 1, [], 3)
print allpath_list

William Tu

On Aug 21 2009, 4:58 am, Atanas <atanas.kambu...@gmail.com> wrote:
> Hi,
>

> I implemented a function that returnsallshortest paths between two

> nodes in an undirected graph.  Here is the code, feel free to improve
> and include in NetworkX:
>
> def all_shortest_paths(G,a,b):

>     """ Return a list ofallshortest paths in graph G between nodes a

[jordi torrents]

Hi William,

2011/4/8 William Tu <u901...@gmail.com>:

> Hi,
>
> I implement another function that returns all possible paths between
> two nodes in a directed graph. Here is the code, feel free to improve
> it.

I'm curious about the use cases for finding all paths between two
nodes, could you please elaborate on the use that you will give to
this function? Note that the OP of this thread was interested in all
*shortest* paths. Your implementation deals with the potentially
infinite paths problem (for graphs with cycles) by establishing a
maximum length for the paths returned (maxhop), is this a problem for
the use that you intend with this function?

I'm interested in this because I'm working on an implementation for
finding node-independent paths between two nodes (paths that only
share the source and target nodes). I have a first approximation (not
optimal) almost finished that I plan to upload to NetworkX Trac
shortly. This is useful as a (first step towards a) fast approximation
to find k-connected components in a moderately large networks (of the
order of hundreds of thousands of nodes and edges), see [1] for a
description of the algorithm and a possible way to approximate the
k-connected components.

Knowing other use cases for related problems could help me developing
code that would also be useful in other scenarios.

Salut!

[1] http://eclectic.ss.uci.edu/~drwhite/working.pdf

[William Tu]

Hi,

I'm implementing a routing algorithm for a large network and tries to
avoid congestion and provide multiple paths for reliability. In stead
of using only shortest paths, I tried to exploit other *longer* paths
(n hops more than shortest path) and make use of it. For the fault
tolerance reason, I'm trying to find vertex disjoint and edge disjoint
paths for a given pair (A-B). So that once a switch or network link is
down, the path for (A-B) can be switched to their backup path. I'm
using my find_pair_all_path function to first enumerating all possible
paths, find the vertex/edge disjoint paths fir this pair, and
determine which one is the best in terms of congestion avoidance.

Thanks for sharing the paper. I'm also looking for a way to find the
node-independent paths, my current method, enumerating all paths and
find node-independent paths from it, is super slow.I'm looking
forwarding to see your implementation.

William Tu

On Apr 8, 11:47 pm, jordi torrents <jtorre...@milnou.net> wrote:
> Hi William,
>

> 2011/4/8 William Tu <u9012...@gmail.com>:
>
> > Hi,
>
> > I implement another function that returnsallpossible paths between

> > two nodes in a directed graph. Here is the code, feel free to improve
> > it.
>

> I'm curious about the use cases for findingallpaths between two

[jordi torrents]

William and everybody,

I've opened a ticket with an implementation of the algorithm proposed
by White and Newman for finding node independent paths:

https://networkx.lanl.gov/trac/ticket/538

It is a first approximation and it's not well tested. As I explain in
the ticket, I have doubts regarding how to implement the search when
the nodes are adjacent and regarding how to implement a refinement
(gaining speed and losing accuracy) proposed by the authors. The later
is quite important for me because I would like to use this algorithm
in moderately large networks.

Comments, suggestions, code or tests would be greatly appreciated.

Salut!

2011/4/9 William Tu <u901...@gmail.com>:

> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>
>