List of all paths from source to stream in a directed acyclic graph

Question

Possible duplicate:
[python]: path between two nodes

Can someone point me to some resources on how to do this? I am using networkx as my python library.

Thanks!

Answer 1

This is based on Alex Martelli's answer, but it should work. It depends on the expression source_node.children giving an iterability that will iterate over all the children of source_node . It also relies on the working path for the == operator to compare two nodes to make sure they are the same. Using is may be a better choice. Apparently, in the library used, the syntax for iterating over all children is graph[source_node] , so you will need to adjust the code accordingly.

 def allpaths(source_node, sink_node): if source_node == sink_node: # Handle trivial case return frozenset([(source_node,)]) else: result = set() for new_source in source_node.children: paths = allpaths(new_source, sink_node, memo_dict) for path in paths: path = (source_node,) + path result.add(path) result = frozenset(result) return result 

My main problem is that this makes the first search for depth, it will waste effort when there are several paths from source to node, that grandson, great-grandson, etc. the whole source, but not necessarily the parent, to sink. If he remembered the answer for this source and plunged into a node, additional efforts could be avoided.

Here is an example of how this will work:

 def allpaths(source_node, sink_node, memo_dict = None): if memo_dict is None: # putting {}, or any other mutable object # as the default argument is wrong memo_dict = dict() if source_node == sink_node: # Don't memoize trivial case return frozenset([(source_node,)]) else: pair = (source_node, sink_node) if pair in memo_dict: # Is answer memoized already? return memo_dict[pair] else: result = set() for new_source in source_node.children: paths = allpaths(new_source, sink_node, memo_dict) for path in paths: path = (source_node,) + path result.add(path) result = frozenset(result) # Memoize answer memo_dict[(source_node, sink_node)] = result return result 

It also allows you to save a dictionary of notes between calls, so if you need to calculate the answer for several nodes of the source and receiver, you can avoid a lot of effort.

Answer 2

This one actually works with networkx, and it is 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 

Answer 3

I’m not sure that there are special optimization opportunities - before looking for any of them, I would make a simple recursive solution, something like (using networkx only the function that indexes the graph using node gives iterability, giving way to its neighboring nodes [ [a dict, in the case of networkx, but I do not use it in particular]]) ...:

 def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()): set_of_result_paths = set() for n in source_nodes: next_from_n = [] for an in G[n]: if an in set_of_sink_nodes: set_of_result_paths.add(path_prefix + (n, an)) else: next_from_n.append(an) if next_from_n: set_of_result_paths.update( allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,))) return set_of_result_paths 

This should be convincingly correct (but I am not going to do the proof, because it is very late, and I am tired and fuzzy-head ;-) and you can use any further optimizations; -).

The first optimization I would try would be some kind of simple memoizing: if I already computed a set of paths from some node N to any node target (no matter the prefix leading to N, when I did that calculation), I I can put this in a dict under the key N and avoid further re-calculations if and when I get N again on a different route; -).