Network Flow

Edges have carried cost so far: length, time, fare. This lesson gives edges a different meaning — capacity. The question is no longer “which is the cheapest path” but “how much can be pushed from a source to a target.”

The problem gathers a wide family — from pipelines to communication networks to task assignment — under a single roof.

Flow Network

A flow network is a directed graph in which every edge carries a non-negative capacity. There are two special vertices: the source and the sink.

A flow assigns a value to every edge and satisfies two constraints:

Capacity constraint. The flow on any edge cannot exceed its capacity.

Conservation constraint. At every vertex other than the source and the sink, flow in equals flow out.

The value of a flow is the net flow leaving the source. The goal is to maximize this value.

capacity: dict[str, dict[str, int]] = {
    "S": {"A": 10, "C": 10},
    "A": {"B": 4, "C": 2, "D": 8},
    "B": {"T": 10},
    "C": {"D": 9},
    "D": {"B": 6, "T": 10},
    "T": {},
}

The total capacity leaving the source is 20, but this is only an upper bound — the network’s internal structure may impose a lower ceiling.

Residual Network and Augmenting Path

A greedy approach — “find an empty path, fill it, repeat” — gives the wrong result: a choice made early can block a better distribution found later, and it cannot be undone.

The solution is the concept of a residual network. In the residual network, two values are kept for every edge:

• The forward remaining capacity: capacity minus the current flow.
• A backward capacity equal to the current flow.

The backward edge is the ability to “cancel the flow sent along this edge.” No choice is ever permanently wrong this way — the algorithm can correct its own earlier decision later.

Any path from the source to the sink in the residual network is called an augmenting path. The amount that can be sent along the path is its smallest remaining capacity (the bottleneck).

Ford–Fulkerson method: Find an augmenting path while one remains, and increase the flow along it.

The Edmonds–Karp Variant

The method does not say how the augmenting path should be chosen. If the path is chosen by breadth-first search every time — that is, as the path with the fewest edges — the resulting variant costs $O(V \cdot E^2)$ and terminates regardless of the choice.

from collections import deque, defaultdict


def residual_network(capacity: dict[str, dict[str, int]]) -> dict[str, dict[str, int]]:
    residual: dict[str, dict[str, int]] = defaultdict(dict)
    for v in capacity:
        for w, c in capacity[v].items():
            residual[v][w] = c
            residual[w].setdefault(v, 0)      # backward edge: starts at zero
    return residual


def edmonds_karp(capacity: dict[str, dict[str, int]],
                 source: str, sink: str) -> tuple[int, set[str]]:
    """(maximum flow, vertices reachable from the source in the residual network)"""
    residual = residual_network(capacity)
    total = 0

    while True:
        previous: dict[str, str | None] = {source: None}
        queue = deque([source])
        while queue and sink not in previous:
            v = queue.popleft()
            for w, c in residual[v].items():
                if c > 0 and w not in previous:
                    previous[w] = v
                    queue.append(w)

        if sink not in previous:           # no augmenting path left
            return total, set(previous)

        v, bottleneck = sink, float("inf")
        while previous[v] is not None:     # find the bottleneck
            bottleneck = min(bottleneck, residual[previous[v]][v])
            v = previous[v]

        v = sink
        while previous[v] is not None:     # send the flow, grow the backward edge
            residual[previous[v]][v] -= bottleneck
            residual[v][previous[v]] += bottleneck
            v = previous[v]
        total += bottleneck


flow, reachable = edmonds_karp(capacity, "S", "T")
print(flow, sorted(reachable))       # 19 ['C', 'S']

Against the 20 units of capacity leaving the source, the maximum flow is 19. What sets the limit is stored in the second returned value.

Maximum Flow – Minimum Cut

A cut splits the vertices into two parts, one containing the source, the other the sink. The cut’s capacity is the sum of the capacities of the edges going from the source’s side to the sink’s side.

Every flow’s value is less than or equal to every cut’s capacity — a flow must cross the cut. The theorem says something stronger:

$$\text{maximum flow} = \text{minimum cut capacity}$$

The justification follows from the algorithm. When the algorithm stops, there is no path from the source to the sink in the residual network; the vertices reachable from the source define a cut. Every forward edge crossing this cut is full (otherwise reachability would continue), and every backward edge is empty. So the value of the flow is exactly equal to this cut’s capacity.

cut = [(v, w) for v in capacity for w in capacity[v]
       if v in reachable and w not in reachable]

print(cut)                                              # [('S', 'A'), ('C', 'D')]
print(sum(capacity[v][w] for v, w in cut))              # 19

The result is not just a number but a diagnosis: the network’s bottleneck is the S→A and C→D edges. If capacity is to be increased, expanding any other edge will not increase the flow.

A byproduct of the theorem is the integrality property: if the capacities are integers, some maximum flow is also integer-valued. This is decisive in problems where the flow can be interpreted as the assignment of discrete objects.

Reduction: Bipartite Matching

The power of network flow lies in other problems being reducible to it.

The maximum matching problem on a bipartite graph is this: match every left vertex to a right vertex connected to it by an edge, with no vertex used twice.

The reduction is simple: 1-capacity edges from an artificial source to the left vertices, 1 capacity on the existing edges, 1-capacity edges from the right vertices to an artificial sink.

def maximum_matching(left: list[str], right: list[str],
                     links: dict[str, list[str]]) -> int:
    network: dict[str, dict[str, int]] = defaultdict(dict)
    for v in left:
        network["S"][v] = 1
    for v, targets in links.items():
        for w in targets:
            network[v][w] = 1
    for w in right:
        network[w]["T"] = 1
    network["T"] = {}
    return edmonds_karp(network, "S", "T")[0]


print(maximum_matching(["a1", "a2", "a3"], ["i1", "i2", "i3"],
                       {"a1": ["i1", "i2"], "a2": ["i1"], "a3": ["i2", "i3"]}))   # 3

print(maximum_matching(["a1", "a2", "a3"], ["i1", "i2", "i3"],
                       {"a1": ["i1"], "a2": ["i1"], "a3": ["i1"]}))               # 1

In the first example, all three candidates are placed in different jobs; in the second, all three want the same job, so only one can be placed. The integrality property is essential here: a half matching would be meaningless.

The same method also converts problems such as task assignment, the count of disjoint paths, and project selection into flow. Reduction is one of the central techniques of algorithm design, and it will also be used in the Theory of Computation course to define complexity classes.

Termination and Sensitivity to Choice

The Ford–Fulkerson method can cause trouble when the augmenting path is chosen arbitrarily: if paths that augment by a very small amount are chosen at every step, the number of steps can equal the flow’s value even with integer capacities. If the capacities are not integers, the method may never terminate at all.

Choosing by breadth-first search (Edmonds–Karp) removes this problem: the length of augmenting paths never decreases, and the total number of steps is bounded by $O(V \cdot E)$. This is a concrete example of the distinction between a “method” and an “algorithm” — what turns a method into an algorithm is pinning down the choice it leaves open.

Summary

• A flow network consists of edges with capacity; a flow satisfies the capacity and conservation constraints.
• Backward edges in the residual network allow earlier decisions to be undone and fix the greedy approach’s error.
• Ford–Fulkerson grows the flow as long as an augmenting path remains; Edmonds–Karp chooses the path by breadth-first search and gives the $O(V E^2)$ bound.
• Maximum flow equals minimum cut capacity; the set reachable in the residual network gives that cut.
• If the capacities are integers, some maximum flow is integer-valued.
• Problems such as bipartite matching are solved by reducing them to a flow network.

Next Step

Graph algorithms worked on data with connections between elements. The next topic moves to a different structure: sequences of symbols in order. Searching for a pattern in text looks, at first glance, like a linear scan, but it speeds up noticeably once the pattern’s own structure is used. The topic will begin by measuring the cost of brute-force search.