All-paths algorithm
Buck
This is non-recursive, so it should perform reasonably on large
graphs.
I'd be delighted to donate this to the networkx project.
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
--Buck
jordi torrents
2011/4/18 Buck <workit...@gmail.com>:
> Below is an algorithm to find all non-cyclic paths between two points.
> This is non-recursive, so it should perform reasonably on large
> graphs.
The problem with finding all paths between two nodes is not an
implementation issue but the fact that the number of such paths in
most graphs is astronomical. Besides, if the graph contain cycles, you
have to deal with the possibility of infinite distinct paths between
two vertices (as you do in your implementation).
If you try to run your function in a moderately small and sparse graph
(eg nx.gnp_random_graph(100,0.05)) you'll notice that it is not a
practical approach for most real world networks. Depending on the use
that you intend for this function, it may be useful to consider only
node-independent paths between pairs of vertices (paths that only
share the source and the target nodes). We are working on an
implementation of a fast approximation for this problem that gives a
lower bound of such paths [1] for directed and undirected (but
unweighted) graphs. You can follow the discussion and try what we have
so far at:
https://networkx.lanl.gov/trac/ticket/538
Salut!