Python networkx - find heaviest path in DAG between 2 nodes

Question

I'm totally surprised with python networkx not supporting heavies path between specific 2 nodes

I have very big graph (DAG), ~70K nodes where there is a weight attributes on each edge (weight is >= 0)

I want to create a function take source and target and return the heaviest path between this specific 2 nodes.

I have tried using all_simple_path and implemented get_weight function that takes path and return total weight, as suggested in some solutions.

however all_simple_path never ends with this graph, the graph does not have any cycle for sure (ran networkx find_cycle function), this solution worked for very small graphs.

all suggested solutions I found here and other places return heaviest path in the whole graph (start to end), while dag has this function (dag_longest_path), but its not what I need.

Any networkx function or graphs lib in python I can use to get heavies path between 2 nodes ? or any direction to achieve the requirement ?

Thanks in advance!

If you mean something along the lines of "longest path", then that's going to be hard. Here's a song about it: youtube.com/watch?v=H6_TYSWTPzg, and here's a wikipedia article about it: en.wikipedia.org/wiki/Longest_path_problem — Joel
Do you mean the path with the maximum sum of weights? If so, then this is a very hard problem to solve, and I would not expect it to finish in a reasonable time for a network as large as the one you have. — Joel

Azim Mazinani Azim Mazinani · Accepted Answer · 2020-06-10T20:49:48

It's just the matter of summing up the weights (or any other edge numeric attribute) of edges in each path by iterating over the all_simple_paths and take the maximum value at the end:

import networkx as nx
import random

G = nx.complete_graph(10)

# add a random weight between 0 and 1 to each edge
for src, target, _ in G.edges.data():
    G[src][target]['weight'] = round(random.random(), 2)

def aggregate_weights(G, path):
    """
    Calculate sum of the weights in a path.
    """
    return sum([G[i][i + 1]['weight'] for i in range(len(path) - 2)])

def find_heaviest_path(G, source, target):
    """
    Find the heaviest path between source and target nodes.
    """
    return max([aggregate_weights(G, path) for path in nx.all_simple_paths(G, source, target)])

Note: the above algorithm has a high time complexity.

Python networkx - find heaviest path in DAG between 2 nodes

1 Answers