All paths of length L from node n using python

Question

Given a graph G, a node n and a length L, I'd like to collect all (non-cyclic) paths of length L that depart from n.

Do you have any idea on how to approach this?

By now, I my graph is a networkx.Graph instance, but I do not really care if e.g. igraph is recommended.

Thanks a lot!

Answer 1

Use a depth limited search (http://en.wikipedia.org/wiki/Depth-limited_search) where you keep a set of visited nodes for the detection of a cycle when on a path. For example you can build a tree from your node n with all nodes and length of L then prune the tree.

I did a quick search of graph algorithms to do this, but didn't find anything. There is a list of graph algorithms (http://en.wikipedia.org/wiki/Category:Graph_algorithms) that may have just what you are looking for.

Answer 2

Here is another (rather naive) implementation I came up with after reading the answers here:

def findAllPaths(node, childrenFn, depth, _depth=0, _parents={}):
    if _depth == depth - 1:
        # path found with desired length, create path and stop traversing
        path = []
        parent = node
        for i in xrange(depth):
            path.insert(0, parent)
            if not parent in _parents:
                continue
            parent = _parents[parent]
            if parent in path:
                return # this path is cyclic, forget
        yield path
        return

    for nb in childrenFn(node):
        _parents[nb] = node # keep track of where we came from
        for p in findAllPaths(nb, childrenFn, depth, _depth + 1, _parents):
            yield p


graph = {
    0: [1, 2],
    1: [4, 5],
    2: [3, 10],
    3: [8, 9],
    4: [6],
    5: [6],
    6: [7],
    7: [],
    8: [],
    9: [],
    10: [2] # cycle
}

for p in findAllPaths(0, lambda n: graph[n], depth=4):
    print(p)

# [0, 1, 4, 6]
# [0, 1, 5, 6]
# [0, 2, 3, 8]
# [0, 2, 3, 9]

Answer 3

I would just like to expand on Lance Helsten's excellent answer:

The depth-limited search searches for a particular node within a certain depth (what you're calling the length L), and stops when it finds it. If you will take a look at the pseudocode in the wiki link in his answer, you'll understand this:

DLS(node, goal, depth) {
  if ( depth >= 0 ) {
    if ( node == goal )
      return node

    for each child in expand(node)
      DLS(child, goal, depth-1)
  }
}

In your case, however, as you're looking for all paths of length L from a node, you will not stop anywhere. So the pseudocode must be modified to:

DLS(node, depth) {
    for each child in expand(node) {
      record paths as [node, child]
      DLS(child, depth-1)
    }
}

After you're done with recording all the single-link paths from successive nests of the DLS, just take a product of them to get the entire path. The number of these gives you the number of paths of the required depth starting from the node.

Answer 4

This solution might be improved in terms efficiency but it seems very short and makes use of networkx functionality:

G = nx.complete_graph(4)
n =  0
L = 3
result = []
for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()):
    print(paths)
    result+=paths

Answer 5

A very simple way to approach (and solve entirely) this problem is to use the adjacency matrix A of the graph. The (i,j) th element of A^L is the number of paths between nodes i and j of length L. So if you sum these over all j keeping i fixed at n, you get all paths emanating from node n of length L.

This will also unfortunately count the cyclic paths. These, happily, can be found from the element A^L(n,n), so just subtract that.

So your final answer is: Σj{A^L(n,j)} - A^L(n,n).

Word of caution: say you're looking for paths of length 5 from node 1: this calculation will also count the path with small cycles inside like 1-2-3-2-4, whose length is 5 or 4 depending on how you choose to see it, so be careful about that.