Calculate The Longest Path Between Two Nodes Networkx

I'm trying to make a Gantt chard using Networkx. All the nodes in the network are 'tasks' that need to be performed to complete the project. With Networkx it is easy to calculate t

Solution 1:

Looks like you are using DAGs.

Your problem is rather rare so there is no built-in function for it in networkx. You should do it manually:

max(nx.all_simple_paths(DAG, source, target), key=lambda x: len(x))

Here is the full testing code:

import networkx as nx
import random
from itertools import groupby

# Create random DAG
G = nx.gnp_random_graph(50,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])

# Get the longest path from node 1 to node 10max(nx.all_simple_paths(DAG, 1, 10), key=lambda x: len(x))

Solution 2:

Here is some code that I use. I agree is really should be part of NetworkX because it comes up pretty often for me. graph must be a DiGraph. s is the source node and dist is a dict keyed by nodes with weighted distances to s as values.

    def single_source_longest_dag_path_length(graph, s):
        assert(graph.in_degree(s) == 0)
        dist = dict.fromkeys(graph.nodes, -float('inf'))
        dist[s] = 0
        topo_order = nx.topological_sort(graph)
        for n in topo_order:
            for s in graph.successors(n):
                if dist[s] < dist[n] + graph.edges[n,s]['weight']:
                    dist[s] = dist[n] + graph.edges[n,s]['weight']
        return dist