Example usage

In the previous article of the graph algorithms series, we thoroughly explored minimum spanning trees (MSTs), including the widely used Kruskal’s and Prim’s algorithms. In this article, we delve into an important class of graph algorithms—network flow algorithms—and examine their practical applications.

At its core, network flow theory addresses how to optimally route resources from a source node to a sink node (also called the destination) within a directed flow network. Through concrete examples, we will study fundamental network flow problems and learn how to solve them using the Ford–Fulkerson algorithm.

Basic Concepts of Network Flow

In network flow, we work with a directed graph composed of the following elements:

• Nodes: Represent vertices in the graph, including a designated source node $s$ and a sink (or target) node $t$.
• Edges: Each directed edge $(u, v)$ has a non-negative capacity $c(u, v)$, indicating the maximum amount that can flow across it.
• Flow: A function $f(u, v)$ assigning to each edge a non-negative value representing the amount of flow sent from $u$ to $v$, subject to capacity constraints.

Formal Definition of Flow

A flow $f$ on a directed graph satisfies the following two conditions:

1. Capacity Constraint: For every edge $(u, v)$,
   $f(u, v) \leq c(u, v).$

2. Flow Conservation: For every intermediate node $u \in V \setminus \{s, t\}$, total inflow equals total outflow:
   $\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v).$
   By convention, the source $s$ has zero inflow, and the sink $t$ has zero outflow.

The Ford–Fulkerson Algorithm

Next, we introduce the Ford–Fulkerson method—a classic algorithm for computing the maximum flow from source $s$ to sink $t$. It iteratively augments flow along augmenting paths in the residual network.

Algorithm Steps

1. Initialize Flow: Set $f(u, v) = 0$ for all edges $(u, v)$.
2. Find Augmenting Path: Use DFS or BFS on the residual network to find a path from $s$ to $t$ where each edge has positive residual capacity.
3. Augment Flow: Determine the bottleneck capacity—the minimum residual capacity along the path—and increase flow by that amount along each forward edge (and decrease it equivalently along reverse edges).
4. Update Residual Network: Adjust residual capacities and reverse-edge flows. Repeat until no more augmenting paths exist.

Example Walkthrough

Let’s illustrate the Ford–Fulkerson algorithm with a concrete example.

Sample Network

Consider the following flow network:

        10
     (s)----->(A)
      |       /| \
      |      / |  \
      |     /  |   \ 10
     5|    /   |    \
      |   /    |     \
      v  v     v      v
     (B)----->(C)---->(t)
        15      10

Here, $s$ is the source, $t$ is the sink, and edge labels denote capacities.

Implementation

Below is a Python implementation of the Ford–Fulkerson algorithm using BFS (i.e., the Edmonds–Karp variant):

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)  # adjacency list representation
        self.capacity = {}               # edge capacities: (u, v) -> cap

    def add_edge(self, u, v, cap):
        self.graph[u].append(v)
        self.graph[v].append(u)  # add reverse edge
        self.capacity[(u, v)] = cap
        self.capacity[(v, u)] = 0  # reverse edge starts with 0 capacity

    def bfs(self, s, t, parent):
        visited = set()
        queue = deque([s])
        visited.add(s)

        while queue:
            u = queue.popleft()
            for v in self.graph[u]:
                if v not in visited and self.capacity[(u, v)] > 0:
                    visited.add(v)
                    parent[v] = u
                    queue.append(v)

        return t in visited

    def ford_fulkerson(self, s, t):
        parent = {}
        max_flow = 0

        while self.bfs(s, t, parent):
            # Find bottleneck capacity along the augmenting path
            path_flow = float('Inf')
            v = t
            while v != s:
                u = parent[v]
                path_flow = min(path_flow, self.capacity[(u, v)])
                v = parent[v]

            # Update residual capacities
            v = t
            while v != s:
                u = parent[v]
                self.capacity[(u, v)] -= path_flow
                self.capacity[(v, u)] += path_flow
                v = parent[v]

            max_flow += path_flow

        return max_flow

# Example usage
g = Graph()
g.add_edge('s', 'A', 10)
g.add_edge('s', 'B', 5)
g.add_edge('A', 'C', 10)
g.add_edge('B', 'C', 15)
g.add_edge('C', 't', 10)

max_flow = g.ford_fulkerson('s', 't')
print(f"Maximum flow: {max_flow}")

This code constructs the sample network and computes its maximum flow using the Ford–Fulkerson method. Running it yields the numerical value of the maximum flow.

Summary

Network flow algorithms are essential tools in algorithm design and optimization, enabling solutions to real-world problems such as maximum flow, minimum cut, bipartite matching, transportation logistics, and resource allocation. Mastering the Ford–Fulkerson algorithm lays the groundwork for tackling more advanced flow-related problems—including those solvable via variants like Edmonds–Karp, Dinic’s algorithm, or push-relabel methods.

In the next article, we will explore advanced concepts and applications of dynamic programming—specifically how to apply DP techniques to solve increasingly complex optimization problems. Stay curious, and keep diving deeper!