NetworkX most efficient way to find the longest path in a DAG at start vertex with no errors
<p>Starting from a certain vertex, how would one find the longest path relative to that vertex? I've been browsing all over and can't find a solution to this problem which actually works for all possible cases of DAGs. Source code in NetworkX would be preferred but regular python is fine too. Im genuinely curious as to why I can't manage to find any proper working example, I do understand it is an NP-type problem but I would like to know the most efficient way it is done.</p>

<p>First, I would check if this graph is connected. If so, then the longest path is the path across all nodes. If not, it means this vertex is contained in a connected component. Then I would use <a href="https://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.connected.connected_component_subgraphs.html" rel="nofollow"><code>connected_component_subgraphs</code></a> to find the largest component this vertex lies in. After that, the longest path is the path across all nodes in this largest component. </p>

<p>Of course, this works only if you don't allow cycles in your path. </p>

<pre><code>import networkx as nx 
G = nx.DiGraph()  
G.add_edges_from([(0,1),(0,4),(4,5),(4,6),(5,6),(6,1),(0,2),(2,3),(1,2)])  
for path in nx.all_simple_paths(G, source=0, target=3):  
    print(path)
</code></pre>

<p>The result:</p>

<pre><code>[0, 1, 2, 3]
[0, 2, 3]
[0, 4, 5, 6, 1, 2, 3]
[0, 4, 6, 1, 2, 3]
</code></pre>

<p>The third one is what you like.</p>

python python-3.x networkx directed-acyclic-graphs longest-path