TopolearnCapacity planning, assignment problems and network reliability all reduce to flow and matching algorithms.
Maximum flow: in a DiGraph whose edges have a capacity attribute, nx.maximum_flow(G, s, t) returns the largest amount that can travel from source to sink, plus a dict showing flow on each edge. nx.maximum_flow_value returns just the number. Edges without a capacity are treated as infinite.
Minimum cut: by the max-flow min-cut theorem, the max flow equals the smallest total capacity of edges whose removal separates s from t. nx.minimum_cut(G, s, t) returns that value and the two node sets, revealing the bottleneck. For unweighted reliability questions, nx.minimum_edge_cut and nx.node_connectivity tell you how many edges or nodes must fail to disconnect the graph.
Min-cost flow (nx.min_cost_flow, nx.network_simplex) adds a weight (cost) per unit and demand on nodes, for cheapest shipping plans.
Matching pairs up nodes with no node used twice:
- Bipartite graphs, like workers and jobs:
nx.bipartite.maximum_matching(G, top_nodes=workers)(Hopcroft-Karp), andnx.bipartite.minimum_weight_full_matchingfor the assignment problem with costs. - General graphs:
nx.max_weight_matching(G)returns a set of edges.
Matchings come back as dicts mapping both directions (bipartite) or sets of pairs (general), so read the docs for each function's format.
Example
import networkx as nx
G = nx.DiGraph()
G.add_edge("s", "a", capacity=10)
G.add_edge("s", "b", capacity=5)
G.add_edge("a", "b", capacity=15)
G.add_edge("a", "t", capacity=4)
G.add_edge("b", "t", capacity=9)
value, flow = nx.maximum_flow(G, "s", "t")
print(value, flow["s"]["a"] + flow["s"]["b"]) # 13 13
cut_value, (reach, rest) = nx.minimum_cut(G, "s", "t")
print(cut_value, sorted(reach)) # 13 ['a', 'b', 's'] (cut a->t, b->t)
B = nx.Graph()
workers, jobs = ["ana", "ben", "cy"], ["cook", "drive", "fix"]
B.add_edges_from([("ana", "cook"), ("ana", "drive"), ("ben", "cook"), ("cy", "fix")])
m = nx.bipartite.maximum_matching(B, top_nodes=workers)
print({w: m[w] for w in workers if w in m})
# {'ana': 'drive', 'ben': 'cook', 'cy': 'fix'}Remember
- Max flow = min cut: the cut shows the bottleneck edges
- Edges need a
capacityattribute; missing means infinite - Use bipartite matching for assignment problems
Watch out for
- Forgetting capacities on some edges, which makes them infinite and the flow unbounded.