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!
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.
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.
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.
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
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]
