# Path between two nodes

Posted on

### Question :

Path between two nodes

I’m using networkx to work with graphs. I have pretty large graph (it’s near 200 nodes in it) and I try to find all possible paths between two nodes. But, as I understand, networkx can find only shortest path. How can I get not just shortest path, but all possible paths?

UPD: path can contain each node only once.

UPD2: I need something like find_all_paths() function, described here: python.org/doc/essays/graphs.html But this function doesn’t work well with large number of nodes and edged =(

igraph, another graph module for Python can calculate all the shortest paths between a given pair of nodes. Calculating all the paths does not make sense as you have infinitely many such paths.

An example for calculating all the shortest paths from vertex 0:

``````>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]
``````

If you have igraph 0.6 or later (this is the development version at the time of writing), you can restrict the result of `get_all_shortest_paths` to a given end vertex as well:

``````>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
[0, 1, 2, 12, 13, 14, 15],
[0, 10, 11, 12, 13, 14, 15],
[0, 1, 11, 12, 13, 14, 15],
[0, 1, 2, 3, 13, 14, 15],
[0, 1, 2, 3, 4, 5, 15]]
``````

Of course you have to be careful; for instance, assume that you have a 100 x 100 grid graph (that can easily be generated by `Graph.Lattice([100, 100], circular=False)` in igraph). The number of shortest paths leading from the top left node to the bottom right node equals the number of possibilities to choose 100 elements out of 200 (proof: the length of the shortest path there has 200 edges, 100 of which will go “horizontally” in the grid and 100 of which will go “vertically”). This probably does not fit into your memory, therefore even calculating all the shortest paths between these two nodes is not really feasible here.

If you really need all the paths between two nodes, you can rewrite the function given on the webpage you mentioned using igraph, which will probably be faster than a pure Python solution as igraph’s core is implemented in C:

``````def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in set(graph.neighbors(start)) - set(path):
paths.extend(find_all_paths(graph, node, end, path))
return paths
``````

It can be optimized more by converting the graph to an adjacency list representation first as it would spare repeated calls to `graph.neighbors`:

``````def find_all_paths(graph, start, end):
path = path + [start]
if start == end:
return [path]
paths = []
for node in adjlist[start] - set(path):
return paths

adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
``````

Edit: fixed first example to work in igraph 0.5.3 as well, not only in igraph 0.6.

This one actually works with networkx, and it’s non-recursive, which may be nice for large graphs.

``````def find_all_paths(graph, start, end):
path  = []
paths = []
queue = [(start, end, path)]
while queue:
start, end, path = queue.pop()
print 'PATH', path

path = path + [start]
if start == end:
paths.append(path)
for node in set(graph[start]).difference(path):
queue.append((node, end, path))
return paths
``````