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>Number of sequences is of order |V|*d^3, where d is average node output degree. From how graph is created, d is bounded. I suppose that d is not very small (like &lt; 5). That means, for 5M nodes graph there are > 1G paths.</p>

<p>Since finding one path is fast (they are short) it is not sure that DP like algorithm can help. DP like algorithms try to take an advantage of partially calculated data, so there is an overhead of storing and retrieving that data and maybe that is larger overhead than just to calculate needed partial data.</p>

<p>One idea is algorithm that traverse DAG in back topological order and do two things:</p>

<ul>
<li>for node keep all paths that starts from that node of length 3,</li>
<li>using successors paths of length 3 print all paths of length 4.</li>
</ul>

<p>This method can use lot of memory, but some of it can be freed for nodes that are not successor of any traverse boundary node.</p>

<p>Other idea is just to make simple algorithm more optimized. In your solution there are three for loops for each node. That means four for loops for all paths. Note that each loop is through nodes. It is possible
to join first two loops by iterating through edges. That is due each path has to start with one edge. Algorithm is like:</p>

<pre><code>for n1, n2 in DAG.edges():
  for n3 in DAG.successors(n2):
    for n4 in DAG.successors(n3):
      paths.append([n1, n2, n3, n4])
</code></pre>

<p>Or even simpler by first selecting middle edge:</p>

<pre><code>for n2, n3 in DAG.edges():
  for n1, n4 in itertools.product(DAG.predecessors(n2), DAG.successors(n3)):
    paths.append([n1, n2, n3, n4])
</code></pre>

<p>Outer loop can be optimized by not selecting middle edge that starts on source node or ends on target node. But that is quite fast detected in product() method. Maybe this optimization can help by not sending not needed data into other process.</p>

python algorithm graph networkx graph-traversal