pythonnetworkx

Get cumulative weight of edges without repeating already traversed paths


I have a water pipe network where each node is a house and each edge is a pipe connecting houses. The edges have a water volume as an attribute.

I want to calculate the total volume reaching node 13.

It should sum to 5+2+1+6+0+3+14+4+12+5+8+10+6+9=85

enter image description here

I've tried something like this, but it will repeat already traversed paths. For example I dont want to sum the value from node 1 to 2 (the weight 5) more than once:

import networkx as nx
from itertools import combinations

G = nx.DiGraph()

edges = [(1,2,5), (2,5,0), (3,2,2), (3,4,1), (4,5,6), (5,6,3), (7,8,14), (8,6,4), (6,9,12), (9,11,8), (10,9,5),(10,12,10), (11,12,6),(12,13,9)]

for edge in edges:
    n1, n2, weight = edge 
    G.add_edge(n1, n2, volume=weight)

for n1, n2 in combinations(G.nodes,2):
    paths = list(nx.all_simple_paths(G=G, source=n1, target=n2))
    for path in paths:
        total_weight = nx.path_weight(G=G, path=path, weight="volume")
        print(f"From node {n1} to {n2}, there's the path {'-'.join([str(x) for x in path])} \n with the total volume: {total_weight}")
        # From node 1 to 2, there's the path 1-2 
        # with the total volume: 5
        # From node 1 to 5, there's the path 1-2-5 
        # with the total volume: 5
        # From node 1 to 6, there's the path 1-2-5-6 
        # ...

Solution

  • IIUC, just get a subgraph of all ancestors of 13 (and including 13), then compute the weighted size (= sum of all edge weights):

    target = 13
    G.subgraph(nx.ancestors(G, target)|{target}).size(weight='volume')
    

    Output: 85