Finding all paths/walks of given length in a netwo

Question

I'm using networkx and trying to find all the walks with length 3 in the graph, specifically the paths with three edges. I tried to find some information about the algorithms in the networkx documentation but I could only find the algorithms for the shortest path in the graph. Can I find a length of a path trough specific nodes, for example a path trough nodes 14 -> 11 -> 12 -> 16 if the shortest path is 14 -> 15 -> 16? Here's an image of a graph for an example http://i62.tinypic.com/2ekj602.jpg

Answer 1

Simplest version (another version is below which I think is faster):

def findPaths(G,u,n):
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1) if u not in path]
    return paths

This takes a network G and a node u and a length n. It recursively finds all paths of length n-1 starting from neighbors of u that don't include u. Then it sticks u at the front of each such path and returns a list of those paths.

Note, each path is an ordered list. They all start from the specified node. So for what you want, just wrap a loop around this:

allpaths = []
for node in G:
    allpaths.extend(findPaths(G,node,3))

Note that this will have any a-b-c-d path as well as the reverse d-c-b-a path.

If you find the "list comprehension" to be a challenge to interpret, here's an equivalent option:

def findPathsNoLC(G,u,n):
    if n==0:
        return [[u]]
    paths = []
    for neighbor in G.neighbors(u):
        for path in findPathsNoLC(G,neighbor,n-1):
            if u not in path:
                paths.append([u]+path)
    return paths

For optimizing this, especially if there are many cycles, it may be worth sending in a set of disallowed nodes. At each nested call it would know not to include any nodes from higher up in the recursion. This would work instead of the if u not in path check. The code would be a bit more difficult to understand, but it would run faster.

def findPaths2(G,u,n,excludeSet = None):
    if excludeSet == None:
        excludeSet = set([u])
    else:
        excludeSet.add(u)
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) if neighbor not in excludeSet for path in findPaths2(G,neighbor,n-1,excludeSet)]
    excludeSet.remove(u)
    return paths

Note that I have to add u to excludeSet before the recursive call and then remove it before returning.