Reducing a weighted directed graph into a DAG with networkx

user_24545 0
Viewed 444

Suppose there is a weighted directed graph, possibly with cycles

import neteorkx as nx

G = nx.DiGraph()
G.add_weighted_edges_from(
    [
        ("a", "b", 10),
        ("b", "c", 10),
        ("c", "d", 10),
        ("d", "e", 5),
        ("d", "a", 3),
    ]
)

What is the proper way to reduce that graph such that all cycles are removed and the weights are adjusted accordingly?

e.g. in this example since the D -(3)-> A edge is removed, we drop all weights in the path by 3, giving a reduced form of A -(7)-> B -(7)-> C -(7)-> D -(5)-> E

Does networkx provide a standardized algorithm for this, or do I need to implement this myself?

networkx directed-acyclic-graphs graph-theory graph python
1 Answers

Since I haven't found any immediate solutions, I turned to writing my own custom code for this, and right now it doesn't look that bad.

It currently looks something like this:

try:
    while cycle := nx.find_cycle(G, orientation="original"):
        edges = [(u, v) for u, v, _ in list(cycle)]
        u, v = edges.pop()
        weight = G[u][v]["weight"]
        G.remove_edge(u, v)
        for u, v in edges:
            G[u][v]["weight"] -= weight
except nx.exception.NetworkXNoCycle:
    pass
user_245450
Related