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>Here is a function that returns the paths of a given length between all nodes in the graph.  It iterates between all sets of nodes and uses the <code>networkx.all_simple_paths</code> to get the paths.</p>

<pre><code>import networkx as nx

g = nx.DiGraph()

g.add_nodes_from(['A','B','C','D','E'])

g.add_path(['A','B','C','D'])
g.add_path(['A','B','C','E'])
g.add_path(['A','C','D','E'])
g.add_path(['B','C','D','D'])

def find_paths(graph, number_nodes=4):
    paths = []
    for source in graph.nodes_iter():
        for target in graph.nodes_iter():
            if not source==target:
                p_source_target = nx.all_simple_paths(graph, 
                                                      source, 
                                                      target, 
                                                      cutoff=number_nodes-1)
                paths.extend([p for p in p_source_target if len(p)==number_nodes])
    return paths

find_paths(g)
# output:
[['B', 'C', 'D', 'E'],
 ['A', 'C', 'D', 'E'],
 ['A', 'B', 'C', 'E'],
 ['A', 'B', 'C', 'D']]
</code></pre>

python algorithm graph networkx graph-traversal