Network Flow Basics

Analogy categoryAnalogies

Introduction

Network flow models a directed graph where each edge has a capacity representing the maximum amount of 'flow' it can carry, and asks how much total flow can be pushed from a source vertex to a sink vertex without violating any capacity constraint. This abstraction captures a surprisingly wide range of problems: bandwidth allocation in computer networks, bipartite matching (assigning workers to jobs), scheduling, and image segmentation. The central result, the max-flow min-cut theorem, states that the maximum amount of flow achievable equals the minimum total capacity of edges that, if removed, would disconnect the source from the sink -- a 'min cut'.

🏏

Cricket analogy: Network flow is like modeling how many runs can be pushed through a chain of running partners between striker and boundary, where each partner's capacity, running speed, limits the total, and the min cut is the slowest link in the chain.

Algorithm/Syntax

python

from collections import deque, defaultdict

def edmonds_karp(capacity, source, sink, n):
    """capacity: dict[(u, v)] = cap, defined for both directions (0 if no edge).
    n: number of vertices. Returns the max flow value.
    """
    graph = defaultdict(list)
    cap = defaultdict(int)
    for (u, v), c in capacity.items():
        graph[u].append(v)
        graph[v].append(u)  # reverse edge enables 'undoing' flow
        cap[(u, v)] += c

    def bfs_find_path():
        parent = {source: None}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            if u == sink:
                break
            for v in graph[u]:
                if v not in parent and cap[(u, v)] > 0:
                    parent[v] = u
                    queue.append(v)
        if sink not in parent:
            return None
        path = []
        v = sink
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        return list(reversed(path))

    max_flow = 0
    while True:
        path = bfs_find_path()
        if path is None:
            break
        bottleneck = min(cap[(u, v)] for u, v in path)
        for u, v in path:
            cap[(u, v)] -= bottleneck   # use forward capacity
            cap[(v, u)] += bottleneck   # increase residual reverse capacity
        max_flow += bottleneck

    return max_flow

Explanation

Ford-Fulkerson is the general method: repeatedly find an augmenting path from source to sink through edges with remaining (residual) capacity, push as much flow as the path's bottleneck edge allows, and update the residual graph by decreasing forward capacity and increasing reverse capacity (so flow can later be 'rerouted' or partially undone if it turns out suboptimal). This continues until no augmenting path exists, at which point the flow is maximum. Edmonds-Karp is a specific implementation of Ford-Fulkerson that always chooses the shortest augmenting path (by number of edges, found via BFS) rather than an arbitrary one; this choice guarantees the algorithm terminates in a polynomial number of iterations even with irrational or unusual capacities, whereas a naive Ford-Fulkerson using DFS or arbitrary path selection can be slow or fail to terminate in pathological cases with irrational capacities.

🏏

Cricket analogy: Ford-Fulkerson is like repeatedly finding the best available running route between wickets and pushing as many runs as the slowest fielder allows, updating who's now tired, the residual capacity; Edmonds-Karp always picks the shortest route first via BFS, guaranteeing the run chase finishes in reasonable time.

Example

python

# Vertices 0=source, 3=sink; edges with capacities
capacity = {
    (0, 1): 3, (0, 2): 2,
    (1, 2): 1, (1, 3): 2,
    (2, 3): 3,
}
print(edmonds_karp(capacity, source=0, sink=3, n=4))  # 4

# Trace: augmenting path 0->1->3 pushes min(3, 2) = 2 units (edge (1,3) saturates).
# Next augmenting path 0->2->3 pushes min(2, 3) = 2 units (edge (0,2) saturates).
# Next BFS search finds no more augmenting paths (0->1->2->3 is blocked because
# (1,3) and (0,2) are saturated), so the algorithm stops with total max flow = 4.
# This matches the min cut {(0,1), (2,3)-portion} whose combined effective
# capacity across the source side of the cut sums to 4.

Complexity

Edmonds-Karp runs in O(V * E^2) time: each BFS augmenting-path search costs O(E), and it can be shown that at most O(V * E) augmenting paths are needed before the algorithm terminates. This is a strict improvement over generic Ford-Fulkerson, whose runtime O(E * max_flow) depends on the numeric value of the maximum flow and can be exponential for poorly chosen augmenting paths on graphs with large integer capacities. More advanced algorithms like Dinic's algorithm achieve O(V^2 * E), better still for large graphs.

🏏

Cricket analogy: Always choosing the shortest available running route, Edmonds-Karp, bounds the number of run-chasing attempts polynomially, unlike blindly choosing any route, generic Ford-Fulkerson, which could take forever on a huge target; a more advanced fielding strategy, Dinic's, does even better on a big chase.

Key Takeaways

Max-flow min-cut theorem: the maximum flow from source to sink equals the minimum total capacity of a cut separating them.
Ford-Fulkerson repeatedly finds augmenting paths in the residual graph and pushes flow until none remain.
Edmonds-Karp specializes Ford-Fulkerson by using BFS to always pick the shortest augmenting path, guaranteeing O(V * E^2) time.
Residual (reverse) edges let the algorithm 'undo' previously assigned flow if a better routing is later found.
Network flow underlies bipartite matching, scheduling, and segmentation problems, not just literal transportation networks.

Practice what you learned

1. What does the max-flow min-cut theorem state?

2. What distinguishes Edmonds-Karp from generic Ford-Fulkerson?

3. Why does the algorithm add a reverse (residual) edge each time it pushes flow along a forward edge?

4. What is the time complexity of the Edmonds-Karp algorithm on a graph with V vertices and E edges?

Was this page helpful?

Bellman-Ford Algorithm

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#NetworkFlowBasics#Network#Flow#Algorithm#Syntax#Networking#StudyNotes#SkillVeris