list of all paths from source to sink in directed acyclic graph [duplicate]

Question

Possible Duplicate:
[python]: path between two nodes

Can anyone point me to some resources on how to do this? I'm 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 yielding an iterable that will iterate over all the children of source_node. It also relies on there being a working way for the == operator to compare two nodes to see if they are the same. Using is may be a better choice. Apparently, in the library you're using, the syntax for getting an iterable over all the 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 concern is that this does a depth first search, it will waste effort when there are several paths from the source to a node that's a grandchild, great grandchild, etc all of source, but not necessarily a parent of sink. If it memoized the answer for a given source and sink node it would be possible to avoid the extra effort.

Here is an example of how that would 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

This also allows you to save the memoization dictionary between invocations so if you need to compute the answer for multiple source and sink nodes you can avoid a lot of extra effort.