Given a DAG, remove nodes exclusively present in paths shorter than length 3
<p>I'm working with directed acyclic graphs in networkx. I have graphs that look like the figure below.
<a href="http://i.stack.imgur.com/OcdZN.png" rel="nofollow"><img src="http://i.stack.imgur.com/OcdZN.png" alt="enter image description here"></a></p>

<p>What I essentially want to do is remove all the nodes from this graph that are exclusively connected to paths with length less than 3. For example, in the graph above I would delete all the blue nodes and keep only the red ones.</p>

<p>What would be a best algorithm for this keeping in mind that these graphs can grow very large (upto 10K nodes)?</p>

<p>A similar question <a href="http://stackoverflow.com/questions/19306914/remove-all-nodes-in-a-binary-three-which-don-t-lie-in-any-path-with-sum-k">here</a> focuses on binary trees only and will not be applicable to my case. I'd prefer to achieve this on Python (networkx).</p>

<p>Thanks!</p>

<ol>
<li>generate the height map (a dictionary from node to height)</li>
<li>generate the inverse graph if needed (all edges are reversed)</li>
<li>generate the depth map (which is just the height map of the inverse graph)</li>
<li>nodes = [ n for n in nodes if hmap[n] + dmap[n] >= 3 ]</li>
</ol>

<p>That's O(nodes+edges)</p>

python graph graph-algorithm networkx graph-traversal