Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading