Use networkx to calculate the longest path to a given node

Question

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

Answer 1

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)

Answer 2

You can use:

def longest_path_to_node(G, target, weight):
    leaves = [node for node, degree in G.in_degree() if degree == 0]
    max_weight = 0
    for leaf in leaves:
        paths = nx.all_simple_edge_paths(G, leaf, target)
        for path in paths:
           max_weight = max(max_weight, sum(G.edges[edge][weight]
                                            for edge in path))
    return max_weight

Output:

>>> longest_path_to_node(G, target=3, weight='w')
5

Answer 3

The answer by @user344577 selects the higher value of weight between the adjacent nodes, which won't be the longest path for all the cases (or for each nodes). @Corralien answer gives the right result, it calculates the length based on weight until the farthest ancestor, but it could be inefficient for big graphs. Here it's a faster option:

def length_longest_path_to_node(G, node, weight):
    all_ancestors = nx.ancestors(G, node)
    all_ancestors.add(node)
    G_sub = G.subgraph(all_ancestors)
    return nx.dag_longest_path_length(G_sub, weight)