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.
