Skip to content

Network Flow

Problem

Given a directed graph with edge capacities, find the maximum flow from a source node to a sink node.

Approach

Edmonds-Karp: repeatedly find augmenting paths using BFS on the residual graph. Each BFS finds the shortest augmenting path, guaranteeing polynomial time.

When to Use

Maximum throughput — "max bandwidth", "maximum matching", "supply chain optimization". Model as source -> sink capacity network. Aviation: air traffic flow management, gate assignment optimization.

Complexity
Time O(V * E^2)
Space O(V^2) for the capacity matrix

Implementation

network_flow

Maximum flow via Edmonds-Karp (BFS-based Ford-Fulkerson).

Problem

Given a directed graph with edge capacities, find the maximum flow from a source node to a sink node.

Approach

Edmonds-Karp: repeatedly find augmenting paths using BFS on the residual graph. Each BFS finds the shortest augmenting path, guaranteeing polynomial time.

When to use

Maximum throughput — "max bandwidth", "maximum matching", "supply chain optimization". Model as source -> sink capacity network. Aviation: air traffic flow management, gate assignment optimization.

Complexity

Time: O(V * E^2) Space: O(V^2) for the capacity matrix

edmonds_karp 

edmonds_karp(
    num_nodes: int,
    edges: list[tuple[int, int, int]],
    source: int,
    sink: int,
) -> int

Return the maximum flow from source to sink.

edges is a list of (u, v, capacity).

edmonds_karp( ... 4, [(0, 1, 10), (0, 2, 10), (1, 3, 10), (2, 3, 10), (1, 2, 1)], 0, 3 ... ) 20

Source code in src/algo/graphs/network_flow.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def edmonds_karp(
    num_nodes: int,
    edges: list[tuple[int, int, int]],
    source: int,
    sink: int,
) -> int:
    """Return the maximum flow from *source* to *sink*.

    *edges* is a list of (u, v, capacity).

    >>> edmonds_karp(
    ...     4, [(0, 1, 10), (0, 2, 10), (1, 3, 10), (2, 3, 10), (1, 2, 1)], 0, 3
    ... )
    20
    """
    capacity: list[list[int]] = [[0] * num_nodes for _ in range(num_nodes)]
    adj: list[list[int]] = [[] for _ in range(num_nodes)]

    for u, v, cap in edges:
        capacity[u][v] += cap
        adj[u].append(v)
        adj[v].append(u)  # reverse edge for residual graph

    total_flow = 0

    while True:
        parent = _bfs(adj, capacity, source, sink, num_nodes)
        if parent is None:
            break

        # Find bottleneck along the path
        path_flow = maxsize
        node = sink
        while node != source:
            prev = parent[node]
            path_flow = min(path_flow, capacity[prev][node])
            node = prev

        # Update residual capacities
        node = sink
        while node != source:
            prev = parent[node]
            capacity[prev][node] -= path_flow
            capacity[node][prev] += path_flow
            node = prev

        total_flow += path_flow

    return total_flow
tests/graphs/test_network_flow.py
"""Tests for maximum network flow (Edmonds-Karp)."""

from algo.graphs.network_flow import edmonds_karp


class TestEdmondsKarp:
    def test_simple_two_paths(self) -> None:
        # s->a->t and s->b->t, each capacity 10
        edges = [(0, 1, 10), (0, 2, 10), (1, 3, 10), (2, 3, 10)]
        assert edmonds_karp(4, edges, 0, 3) == 20

    def test_bottleneck(self) -> None:
        edges = [(0, 1, 100), (1, 2, 1), (2, 3, 100)]
        assert edmonds_karp(4, edges, 0, 3) == 1

    def test_no_path(self) -> None:
        edges = [(0, 1, 5)]
        assert edmonds_karp(3, edges, 0, 2) == 0

    def test_parallel_edges(self) -> None:
        edges = [(0, 1, 5), (0, 1, 3)]
        assert edmonds_karp(2, edges, 0, 1) == 8

    def test_diamond_with_cross(self) -> None:
        edges = [
            (0, 1, 10),
            (0, 2, 10),
            (1, 3, 10),
            (2, 3, 10),
            (1, 2, 1),
        ]
        assert edmonds_karp(4, edges, 0, 3) == 20

    def test_single_edge(self) -> None:
        assert edmonds_karp(2, [(0, 1, 7)], 0, 1) == 7

Implement it yourself

Run: just challenge graphs network_flow

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

network_flow

Maximum flow via Edmonds-Karp (BFS-based Ford-Fulkerson).

Problem

Given a directed graph with edge capacities, find the maximum flow from a source node to a sink node.

Approach

Edmonds-Karp: repeatedly find augmenting paths using BFS on the residual graph. Each BFS finds the shortest augmenting path, guaranteeing polynomial time.

When to use

Maximum throughput — "max bandwidth", "maximum matching", "supply chain optimization". Model as source -> sink capacity network. Aviation: air traffic flow management, gate assignment optimization.

Complexity

Time: O(V * E^2) Space: O(V^2) for the capacity matrix

edmonds_karp 

edmonds_karp(
    num_nodes: int,
    edges: list[tuple[int, int, int]],
    source: int,
    sink: int,
) -> int

Return the maximum flow from source to sink.

edges is a list of (u, v, capacity).

edmonds_karp( ... 4, [(0, 1, 10), (0, 2, 10), (1, 3, 10), (2, 3, 10), (1, 2, 1)], 0, 3 ... ) 20

Source code in src/algo/graphs/network_flow.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def edmonds_karp(
    num_nodes: int,
    edges: list[tuple[int, int, int]],
    source: int,
    sink: int,
) -> int:
    """Return the maximum flow from *source* to *sink*.

    *edges* is a list of (u, v, capacity).

    >>> edmonds_karp(
    ...     4, [(0, 1, 10), (0, 2, 10), (1, 3, 10), (2, 3, 10), (1, 2, 1)], 0, 3
    ... )
    20
    """
    capacity: list[list[int]] = [[0] * num_nodes for _ in range(num_nodes)]
    adj: list[list[int]] = [[] for _ in range(num_nodes)]

    for u, v, cap in edges:
        capacity[u][v] += cap
        adj[u].append(v)
        adj[v].append(u)  # reverse edge for residual graph

    total_flow = 0

    while True:
        parent = _bfs(adj, capacity, source, sink, num_nodes)
        if parent is None:
            break

        # Find bottleneck along the path
        path_flow = maxsize
        node = sink
        while node != source:
            prev = parent[node]
            path_flow = min(path_flow, capacity[prev][node])
            node = prev

        # Update residual capacities
        node = sink
        while node != source:
            prev = parent[node]
            capacity[prev][node] -= path_flow
            capacity[node][prev] += path_flow
            node = prev

        total_flow += path_flow

    return total_flow