Search code examples
pythonnetworkxshortest-pathdigraphs

Use networkx to calculate the longest path to a given node

I have a networkx digraph. I would like to compute the longest path to a given node (from any possible node where there exists a directed path between the two). There are functions like nx.dag_longest_path_length but those do not directly support this.

Possible solutions that I thought of are:

  • Use nx.shortest_path_length which has the target parameter and negate the weights? Then find maximum over the source nodes using a simple for loop.
  • Use something like nx.dag_longest_path_length(G.subgraph(G.predecessors(target)))?

Neither of those seems particularly nice IMHO. Is there a cleaner way? If one of those approaches should be used, which one and why?

Example:

G = nx.DiGraph()
G.add_edge(1, 3, w=3)
G.add_edge(2, 3, w=5)
G.add_edge(3, 4, w=1)
# Now I want to be able to do something like this:
longest_path_to_node(G, target=3, weight="w")  # Expected output: 5
Solution

  • Eventually, I went with this solution. Not sure if it's computationally the most efficient

    import itertools
import networkx as nx

def longest_path_to_node_length(g, target, weight):
    subgraph_nodes = itertools.chain(g.predecessors(target), (target,))
    return nx.dag_longest_path_length(g.subgraph(subgraph_nodes), weight=weight)