Network Flow: Ford-Fulkerson and Edmonds-Karp

Network flow is one of the most powerful frameworks in combinatorial optimization. The max flow problem asks: given a directed graph with edge capacities, what is the maximum amount of “stuff” (water, data, traffic) that can flow from a source node to a sink node without exceeding any edge’s capacity?

The beauty of network flow is that it solves many seemingly unrelated problems: bipartite matching, minimum cut, project selection, baseball elimination, and image segmentation all reduce to max flow.

The Max Flow Problem

Input: A directed graph G = (V, E) with:

• A source node s (where flow originates)
• A sink node t (where flow terminates)
• A capacity function c(u, v) for each edge (u, v)

Output: The maximum total flow from s to t, subject to:

1. Capacity constraint: Flow on each edge must not exceed capacity. 0 <= f(u,v) <= c(u,v)
2. Flow conservation: For every node except s and t, total flow in equals total flow out.

The Residual Graph

The residual graph is the key concept that makes flow algorithms work. For each edge (u, v) with capacity c and current flow f:

• The forward residual edge (u, v) has capacity c - f (remaining capacity)
• The backward residual edge (v, u) has capacity f (flow that can be “undone”)

The backward edges are crucial. They allow the algorithm to correct mistakes by rerouting flow.

class FlowNetwork:
    """
    Flow network with residual graph support.
    """
    def __init__(self, num_nodes):
        self.n = num_nodes
        self.capacity = [[0] * num_nodes for _ in range(num_nodes)]
        self.flow = [[0] * num_nodes for _ in range(num_nodes)]
        self.graph = [[] for _ in range(num_nodes)]

    def add_edge(self, u, v, cap):
        """Add a directed edge from u to v with given capacity."""
        self.capacity[u][v] += cap
        if v not in self.graph[u]:
            self.graph[u].append(v)
        if u not in self.graph[v]:
            self.graph[v].append(u)  # For residual backward edge

    def residual_capacity(self, u, v):
        """Get residual capacity of edge (u, v)."""
        return self.capacity[u][v] - self.flow[u][v]

    def augment(self, path, bottleneck):
        """Push flow along an augmenting path."""
        for i in range(len(path) - 1):
            u, v = path[i], path[i + 1]
            self.flow[u][v] += bottleneck
            self.flow[v][u] -= bottleneck  # Backward flow

Ford-Fulkerson Method

Ford-Fulkerson is a method (not a specific algorithm) that repeatedly finds augmenting paths from source to sink in the residual graph and pushes flow along them. It terminates when no augmenting path exists.

def ford_fulkerson_dfs(network, source, sink):
    """
    Ford-Fulkerson using DFS to find augmenting paths.
    Warning: Not guaranteed to terminate with irrational capacities.
    Time: O(E * max_flow) for integer capacities.
    """
    max_flow = 0

    def dfs(node, visited, bottleneck):
        if node == sink:
            return bottleneck

        visited.add(node)

        for neighbor in network.graph[node]:
            if neighbor not in visited:
                residual = network.residual_capacity(node, neighbor)
                if residual > 0:
                    flow = dfs(neighbor, visited,
                              min(bottleneck, residual))
                    if flow > 0:
                        network.flow[node][neighbor] += flow
                        network.flow[neighbor][node] -= flow
                        return flow
        return 0

    while True:
        visited = set()
        flow = dfs(source, visited, float('inf'))
        if flow == 0:
            break
        max_flow += flow

    return max_flow

Why DFS Can Be Slow

DFS-based Ford-Fulkerson can be extremely slow. Consider a graph with a bottleneck edge of capacity 1000000. DFS might find paths that only push 1 unit of flow each, requiring 1000000 iterations. The fix: use BFS.

Edmonds-Karp Algorithm

Edmonds-Karp is Ford-Fulkerson with BFS for finding augmenting paths. BFS finds the shortest augmenting path (fewest edges), which guarantees O(VE^2) time regardless of capacity values.

from collections import deque

def edmonds_karp(network, source, sink):
    """
    Edmonds-Karp algorithm (BFS-based Ford-Fulkerson).
    Time: O(V * E^2)
    Space: O(V + E)
    """
    max_flow = 0

    while True:
        # BFS to find shortest augmenting path
        parent = [-1] * network.n
        parent[source] = source
        queue = deque([(source, float('inf'))])

        while queue:
            node, flow = queue.popleft()
            for neighbor in network.graph[node]:
                if parent[neighbor] == -1 and neighbor != source:
                    residual = network.residual_capacity(node, neighbor)
                    if residual > 0:
                        parent[neighbor] = node
                        new_flow = min(flow, residual)
                        if neighbor == sink:
                            # Found augmenting path, push flow
                            max_flow += new_flow
                            # Trace back and update flow
                            current = sink
                            while current != source:
                                prev = parent[current]
                                network.flow[prev][current] += new_flow
                                network.flow[current][prev] -= new_flow
                                current = prev
                            break
                        queue.append((neighbor, new_flow))
            else:
                continue
            break
        else:
            # No augmenting path found
            break

    return max_flow

Cleaner Implementation

def max_flow_edmonds_karp(num_nodes, edges, source, sink):
    """
    Complete Edmonds-Karp implementation.
    edges: list of (u, v, capacity) tuples
    Returns: maximum flow value
    """
    # Build capacity matrix and adjacency list
    cap = [[0] * num_nodes for _ in range(num_nodes)]
    adj = [[] for _ in range(num_nodes)]

    for u, v, c in edges:
        cap[u][v] += c
        adj[u].append(v)
        adj[v].append(u)

    flow = [[0] * num_nodes for _ in range(num_nodes)]
    total_flow = 0

    def bfs():
        """Find shortest augmenting path using BFS."""
        parent = [-1] * num_nodes
        parent[source] = source
        queue = deque([source])

        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                residual = cap[node][neighbor] - flow[node][neighbor]
                if parent[neighbor] == -1 and residual > 0 and neighbor != source:
                    parent[neighbor] = node
                    if neighbor == sink:
                        return parent
                    queue.append(neighbor)

        return None

    while True:
        parent = bfs()
        if parent is None:
            break

        # Find bottleneck
        bottleneck = float('inf')
        node = sink
        while node != source:
            prev = parent[node]
            bottleneck = min(bottleneck, cap[prev][node] - flow[prev][node])
            node = prev

        # Update flow
        node = sink
        while node != source:
            prev = parent[node]
            flow[prev][node] += bottleneck
            flow[node][prev] -= bottleneck
            node = prev

        total_flow += bottleneck

    return total_flow

Example

# Flow network from the SVG diagram
edges = [
    (0, 1, 10),  # S -> A, cap 10
    (0, 2, 8),   # S -> B, cap 8
    (1, 3, 6),   # A -> C, cap 6
    (1, 4, 5),   # A -> D, cap 5 (cross edge)
    (2, 4, 9),   # B -> D, cap 9
    (3, 5, 7),   # C -> T, cap 7
    (4, 5, 8),   # D -> T, cap 8
]

result = max_flow_edmonds_karp(6, edges, 0, 5)
print(f"Maximum flow: {result}")  # Maximum flow: 13

Max-Flow Min-Cut Theorem

The max-flow min-cut theorem states that the maximum flow from source to sink equals the minimum capacity of any cut separating source from sink.

A cut is a partition of vertices into two sets S (containing source) and T (containing sink). The capacity of the cut is the sum of capacities of edges going from S to T.

Finding the Min Cut

After computing max flow, the min cut is found by running BFS on the residual graph. All nodes reachable from the source form set S; the rest form set T.

def find_min_cut(num_nodes, edges, source, sink):
    """
    Find the minimum cut after computing max flow.
    Returns: max flow value, list of edges in the min cut
    """
    cap = [[0] * num_nodes for _ in range(num_nodes)]
    adj = [[] for _ in range(num_nodes)]

    for u, v, c in edges:
        cap[u][v] += c
        adj[u].append(v)
        adj[v].append(u)

    flow = [[0] * num_nodes for _ in range(num_nodes)]

    # Run Edmonds-Karp to find max flow
    total_flow = 0

    def bfs():
        parent = [-1] * num_nodes
        parent[source] = source
        queue = deque([source])
        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                residual = cap[node][neighbor] - flow[node][neighbor]
                if parent[neighbor] == -1 and residual > 0 and neighbor != source:
                    parent[neighbor] = node
                    if neighbor == sink:
                        return parent
                    queue.append(neighbor)
        return None

    while True:
        parent = bfs()
        if parent is None:
            break
        bottleneck = float('inf')
        node = sink
        while node != source:
            prev = parent[node]
            bottleneck = min(bottleneck, cap[prev][node] - flow[prev][node])
            node = prev
        node = sink
        while node != source:
            prev = parent[node]
            flow[prev][node] += bottleneck
            flow[node][prev] -= bottleneck
            node = prev
        total_flow += bottleneck

    # Find min cut: BFS on residual graph from source
    reachable = set()
    queue = deque([source])
    reachable.add(source)

    while queue:
        node = queue.popleft()
        for neighbor in adj[node]:
            if neighbor not in reachable:
                if cap[node][neighbor] - flow[node][neighbor] > 0:
                    reachable.add(neighbor)
                    queue.append(neighbor)

    # Edges crossing the cut
    cut_edges = []
    for u, v, c in edges:
        if u in reachable and v not in reachable:
            cut_edges.append((u, v, c))

    return total_flow, cut_edges

Application: Bipartite Matching

Maximum bipartite matching reduces to max flow. Create a source connected to all left nodes, a sink connected to all right nodes, and directed edges from left to right. Each edge has capacity 1.

def max_bipartite_matching(left_nodes, right_nodes, edges):
    """
    Find maximum matching in a bipartite graph.
    left_nodes: number of nodes on left side
    right_nodes: number of nodes on right side
    edges: list of (left_idx, right_idx) pairs
    Returns: size of maximum matching
    """
    # Node numbering: 0=source, 1..left=left nodes,
    # left+1..left+right=right nodes, last=sink
    total = 1 + left_nodes + right_nodes + 1
    source = 0
    sink = total - 1

    flow_edges = []

    # Source to left nodes (capacity 1 each)
    for i in range(left_nodes):
        flow_edges.append((source, i + 1, 1))

    # Left to right edges (capacity 1 each)
    for left_idx, right_idx in edges:
        flow_edges.append((left_idx + 1, left_nodes + 1 + right_idx, 1))

    # Right nodes to sink (capacity 1 each)
    for j in range(right_nodes):
        flow_edges.append((left_nodes + 1 + j, sink, 1))

    return max_flow_edmonds_karp(total, flow_edges, source, sink)

Example

# Matching students to projects
# 3 students, 3 projects
# Student 0 likes projects 0, 1
# Student 1 likes projects 0, 2
# Student 2 likes projects 1
edges = [(0, 0), (0, 1), (1, 0), (1, 2), (2, 1)]

matching = max_bipartite_matching(3, 3, edges)
print(f"Maximum matching: {matching}")  # 3

Application: Project Selection

Given projects with profits (positive) and costs (negative), with dependencies (must do project A before B), find the maximum profit subset.

def max_profit_selection(projects, dependencies):
    """
    Project selection problem.
    projects: list of profit values (positive = profit, negative = cost)
    dependencies: list of (i, j) meaning project i requires project j
    Returns: maximum achievable profit
    """
    n = len(projects)
    source = n
    sink = n + 1
    total_nodes = n + 2

    edges = []
    total_positive = 0

    for i, profit in enumerate(projects):
        if profit > 0:
            total_positive += profit
            edges.append((source, i, profit))  # Source -> profitable projects
        else:
            edges.append((i, sink, -profit))  # Cost projects -> sink

    for i, j in dependencies:
        edges.append((i, j, float('inf')))  # Dependency edges (infinite cap)

    min_cut = max_flow_edmonds_karp(total_nodes, edges, source, sink)
    return total_positive - min_cut

Dinic’s Algorithm (Bonus: Faster Alternative)

Dinic’s algorithm improves on Edmonds-Karp by using level graphs and blocking flows. It runs in O(V^2 * E) time, which is faster in practice.

def dinic(num_nodes, edges, source, sink):
    """
    Dinic's algorithm for maximum flow.
    Time: O(V^2 * E)
    """
    from collections import deque

    cap = [[0] * num_nodes for _ in range(num_nodes)]
    adj = [[] for _ in range(num_nodes)]

    for u, v, c in edges:
        cap[u][v] += c
        adj[u].append(v)
        adj[v].append(u)

    flow = [[0] * num_nodes for _ in range(num_nodes)]

    def build_level_graph():
        """BFS to build level graph."""
        level = [-1] * num_nodes
        level[source] = 0
        queue = deque([source])

        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                if level[neighbor] == -1 and cap[node][neighbor] - flow[node][neighbor] > 0:
                    level[neighbor] = level[node] + 1
                    queue.append(neighbor)

        return level if level[sink] != -1 else None

    def send_flow(node, pushed, level, iter_ptr):
        """DFS to find blocking flow."""
        if node == sink:
            return pushed

        while iter_ptr[node] < len(adj[node]):
            neighbor = adj[node][iter_ptr[node]]
            residual = cap[node][neighbor] - flow[node][neighbor]

            if level[neighbor] == level[node] + 1 and residual > 0:
                d = send_flow(neighbor, min(pushed, residual), level, iter_ptr)
                if d > 0:
                    flow[node][neighbor] += d
                    flow[neighbor][node] -= d
                    return d

            iter_ptr[node] += 1

        return 0

    total_flow = 0

    while True:
        level = build_level_graph()
        if level is None:
            break

        iter_ptr = [0] * num_nodes
        while True:
            pushed = send_flow(source, float('inf'), level, iter_ptr)
            if pushed == 0:
                break
            total_flow += pushed

    return total_flow

Complexity Comparison

Algorithm	Time	When to Use
Ford-Fulkerson (DFS)	O(E * F)	Small max flow F
Edmonds-Karp (BFS)	O(V * E^2)	General purpose
Dinic’s	O(V^2 * E)	Large graphs
Dinic’s (unit capacity)	O(E * sqrt(V))	Bipartite matching

Where F = max flow value, V = vertices, E = edges.

Practice Problems

1. Maximum Flow (various judges) - Direct max flow computation
2. Minimum Cut - Finding the min cut from max flow
3. Bipartite Matching - Reducing to max flow
4. Baseball Elimination (classic) - Elimination via max flow
5. Project Selection - Min cut formulation
6. Network Flow Applications (Codeforces, SPOJ) - Various reductions

Key Takeaways

Network flow is a versatile framework. The max flow problem asks for the maximum amount of flow from source to sink respecting edge capacities. Ford-Fulkerson repeatedly finds augmenting paths in the residual graph. Edmonds-Karp uses BFS for O(VE^2) guaranteed time. The max-flow min-cut theorem connects maximum flow to minimum cuts. Many optimization problems (bipartite matching, project selection, image segmentation) reduce to max flow. Understanding residual graphs and augmenting paths is the key to grasping all flow algorithms.