How to compute edge and node bottleneck coefficients in a weighted directed graph using networkx?

Question

I am trying to analyze a weighted network, and I am focusing on identifying the bottleneck nodes and edges coefficients. I have never done that before on Python and I have the following code:

import networkx as nx

# create a weighted graph
G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 10), (1, 3, 5), (2, 3, 4), (2, 4, 8), (3, 4, 3)])

# compute the edge bottlenecks
edge_bottlenecks = {}
for u, v, data in G.edges(data=True):
    # Compute the minimum weight cut using the Karger algorithm
    edge_cut_value, edge_partition = nx.minimum_cut(G, u, v, flow_func=nx.algorithms.flow.edmonds_karp)
    # Compute the bottleneck value for the edge
    edge_bottleneck = edge_cut_value / data['weight']
    edge_bottlenecks[(u, v)] = edge_bottleneck

# compute the node bottlenecks
node_bottlenecks = {}
for node in G.nodes():
    # Compute the minimum weight cut using the Karger algorithm
    node_cut_value, node_partition = nx.minimum_cut(G, node, flow_func=nx.algorithms.flow.edmonds_karp)
    # Compute the bottleneck value for the node
    node_bottleneck = node_cut_value / sum([G.edges[u, v]['weight'] for u, v in G.edges(node)])
    node_bottlenecks[node] = node_bottleneck

print("Edge bottlenecks:", edge_bottlenecks)
print("Node bottlenecks:", node_bottlenecks)

I get an error message saying "NetworkXUnbounded: Infinite capacity path, flow unbounded above." I can't understand why I am getting such an error message. How can I solve the issue? Thank you.

Answer 1

Afaict, networkx uses capacities instead of weights to determine the edge cuts, and the error you're seeing is because there are no capacities set on your edges, so it defaults to infinite capacity for each edge. If there is even a single path of infinite capacity, minimum_cut will raise the NetworkXUnbounded error you're seeing.

You can set capacities at edge creation time with something like :

G.add_edge(1,2, capacity=3.0)
G.add_edge(1,3, capacity=1.0)
G.add_edge(2,3, capacity=3.0)
G.add_edge(2,4, capacity=5.0)
G.add_edge(3,4, capacity=4.0)

hth

Answer 2

My mistake was how I formulated the graph. First, it is a directed graph, which I should have specified, and I also should have entered the correct syntax when adding edges. I referred to the networkx online resources at https://pydocs.github.io/p/networkx/2.8.2/api/networkx.algorithms.flow.maxflow.maximum_flow. Using the example on the mentioned webpage, the correct code to get the bottleneck coefficients for the nodes and edges is:

import networkx as nx

# Create directed graph
G = nx.DiGraph()
G.add_edge("x", "a", capacity=3.0)
G.add_edge("x", "b", capacity=1.0)
G.add_edge("a", "c", capacity=3.0)
G.add_edge("b", "c", capacity=5.0)
G.add_edge("b", "d", capacity=4.0)
G.add_edge("d", "e", capacity=2.0)
G.add_edge("c", "y", capacity=2.0)
G.add_edge("e", "y", capacity=3.0)

# Compute the node bottleneck coefficients
node_bottlenecks = {}
for node in G.nodes():
    # Compute the minimum weight cut using maximum flow
    node_cut_value, node_partition = nx.minimum_cut(G, "x", "y")
    
    # Check if the node has outgoing edges with non-zero capacity
    outgoing_edges = G.out_edges(node, data=True)
    if any([edge['capacity'] > 0 for _, _, edge in outgoing_edges]):
        # Compute the bottleneck value for the node
        node_bottleneck = node_cut_value / sum([edge['capacity'] for _, _, edge in outgoing_edges])
        node_bottlenecks[node] = node_bottleneck


# Compute the edge bottleneck coefficients
edge_bottlenecks = {}
for u, v, data in G.edges(data=True):
    # Compute the minimum cut using maximum flow
    edge_cut_value, edge_partition = nx.minimum_cut(G, "x", "y")
    # Compute the bottleneck value for the edge
    edge_bottleneck = edge_cut_value / data['capacity']
    edge_bottlenecks[(u, v)] = edge_bottleneck

print("Node bottleneck coefficients:", node_bottlenecks)
print("Edge bottleneck coefficients:", edge_bottlenecks)
```