How to efficiently find all paths formed by k number of nodes in a directed acyclic graph?
<p>I have a DAG that looks like this:
<a href="http://i.stack.imgur.com/d4MN0.png" rel="nofollow">Example DAG</a></p>

<p>I want to extract all the paths constituted by 4 nodes in this graph.</p>

<p>My expected result should look like this:</p>

<p>N1 -> N2 -> N3 -> N4</p>

<p>N1 -> N2 -> N3 -> N5</p>

<p>N1 -> N3 -> N4 -> N5</p>

<p>N2 -> N3 -> N4 -> N5</p>

<p>My current attempt looks like this</p>

<pre><code>def path_finder(n1):
    paths = []
    if DAG.has_node(n1):
        for n2 in DAG.successors(n1):
            for n3 in DAG.successors(n2):
                for n4 in DAG.successors(n3):
                    paths.append([n1, n2, n3, n4])
    return paths
</code></pre>

<p>I'm calling this function for each node. <code>DAG</code> is a global variable, more specifically it is a <code>networkx</code> object (<code>DAG = networkx.DiGraph()</code> )  This naive function is pathetically slow. Is there a more efficient strategy to do this?</p>

<p>I have looked at question <a href="http://stackoverflow.com/questions/20262712/enumerating-all-paths-in-a-directed-acyclic-graph">20262712</a> but was self-solved by the author of the question in rather obscure way. </p>

<p>Thanks</p>

<p>UPDATE:</p>

<p>Since I couldn't get any satisfactory algorithm to solve this, I ended up parallelizing the job using my naive function as a worker while dumping all the data into a queue. I used <code>pool.imap_unordered</code> to launch worker function and aggregated the results from queue. It still is slow (takes couple of hours for 5M nodes). I should also furnish the data for the average degree of nodes that I'm dealing with, because that will have an effect upon how fast my workers runs. But, I'll leave that out for now.</p>

<p>Part of your problem could be that if you come across a node <code>u</code> as the second node in a path then you do all of the calculations to find all the paths of length 3.  But then if you come across <code>u</code> again as the second node, you repeat all of these calculations.</p>

<p>So try to avoid this.  We'll do it recursively calculating all the length 3 paths first (which requires calculating length 2 paths)</p>

<pre><code>def get_paths(G, n):
    '''returns a dict, paths, such that paths[u] is a list of all paths 
       of length n that start from u'''
    if n == 1: #base case, return a dict so that D[u] is a
               #list of all length 1 paths starting from u.
               #it's a boring list.
        return {u: [[u]] for u in G.nodes()}
    #if we get to here n&gt;1 (unless input was bad)
    subpath_dict = get_paths(G,n-1)  #contains all length n-1 paths, 
                                     #indexed by first node
    path_dict = {}
    for u in G:
        path_dict[u] = []  
        for v in G.successors(u):
            path_dict[u].extend([[u]+subpath for subpath in subpath_dict[v]])
    return(path_dict)

G=nx.DiGraph()
G.add_path([1,2,3,4,5,6])
G.add_path([1,3,6,8,10])

path_dict = get_paths(G,4)
path_list = []
for paths in path_dict.values():
    path_list.extend(paths)
</code></pre>

python algorithm graph networkx graph-traversal