Maximum Flow (BGL Book Chapter 8)

Based on “The Boost Graph Library” by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine

Overview

The maximum flow problem is the problem of determining how much of some quantity (say, water, data, or goods) can move through a network from a source to a sink.

There is a long history of algorithms for solving the maximum flow problem, with the first algorithm due to Ford and Fulkerson. The best general-purpose algorithms known include the Edmonds-Karp algorithm (a refinement of Ford-Fulkerson) and the push-relabel algorithm of Goldberg.

Definitions

A flow network is a directed graph G = (V, E) with:

  • A source vertex s (where flow originates)

  • A sink vertex t (where flow is collected)

  • Each edge has a positive real-valued capacity

The flow function f must satisfy three constraints:

  1. Capacity constraint: f(u, v) <= c(u, v) for all edges

  2. Skew symmetry: f(u, v) = -f(v, u) for all vertex pairs

  3. Flow conservation: Flow into a vertex equals flow out (except for s and t)

The maximum flow is the maximum possible value of net flow entering the sink vertex t.

Max-Flow Min-Cut Theorem

An important property of a flow network is that the maximum flow is related to the capacity of the narrowest part of the network. According to the Max-Flow Min-Cut Theorem, the maximum value of the flow from source s to sink t equals the minimum capacity among all (S, T) cuts.

An (S, T) cut is a separation of the graph’s vertices into two sets S and T, where s is in S and t is in T. The capacity of a cut is the sum of the capacities of edges crossing from S to T.

Edge Connectivity

Whether an engineer is designing a telephone network, a LAN for a large company, or the router connections for the Internet backbone, an important consideration is how resilient the network is to damage.

Edge connectivity is the minimum number of edges that can be cut to produce a graph with two disconnected components. This can be computed using maximum flow: set the capacity of every edge to one, and the maximum flow between any two vertices gives the minimum number of edges separating them.

NWGraph Implementation

NWGraph provides maximum flow algorithms including the Edmonds-Karp algorithm.

Listing 10 Complete source code
  1/**
  2 * @file ch8_maxflow.cpp
  3 *
  4 * @brief Maximum Flow (BGL Book Chapter 8)
  5 *
  6 * This example demonstrates the maximum flow problem using the
  7 * Ford-Fulkerson method with BFS (Edmonds-Karp algorithm).
  8 *
  9 * Application: Network bandwidth allocation, bipartite matching,
 10 * transportation networks, supply chain optimization.
 11 *
 12 * @copyright SPDX-FileCopyrightText: 2022 Battelle Memorial Institute
 13 * @copyright SPDX-FileCopyrightText: 2022 University of Washington
 14 *
 15 * SPDX-License-Identifier: BSD-3-Clause
 16 *
 17 * @authors
 18 *   Andrew Lumsdaine
 19 *
 20 */
 21
 22#include <iostream>
 23#include <limits>
 24#include <map>
 25#include <queue>
 26#include <vector>
 27
 28/**
 29 * @brief BFS to find augmenting path from source to sink
 30 *
 31 * @return true if path exists, false otherwise
 32 */
 33bool bfs_find_path(const std::vector<std::vector<std::pair<size_t, double>>>& residual,
 34                   size_t source, size_t sink,
 35                   std::vector<size_t>& parent) {
 36  size_t N = residual.size();
 37  std::vector<bool> visited(N, false);
 38
 39  std::queue<size_t> Q;
 40  Q.push(source);
 41  visited[source] = true;
 42  parent[source] = source;
 43
 44  while (!Q.empty()) {
 45    size_t u = Q.front();
 46    Q.pop();
 47
 48    for (auto&& [v, cap] : residual[u]) {
 49      if (!visited[v] && cap > 0) {
 50        visited[v] = true;
 51        parent[v] = u;
 52        if (v == sink) {
 53          return true;
 54        }
 55        Q.push(v);
 56      }
 57    }
 58  }
 59
 60  return false;
 61}
 62
 63/**
 64 * @brief Edmonds-Karp algorithm for maximum flow
 65 *
 66 * This is the Ford-Fulkerson method using BFS to find augmenting paths.
 67 * BFS ensures the shortest augmenting path is found, giving O(VE^2) complexity.
 68 */
 69double edmonds_karp(size_t N,
 70                    const std::vector<std::tuple<size_t, size_t, double>>& edges,
 71                    size_t source, size_t sink) {
 72  // Build residual graph as adjacency list with capacities
 73  // We need to track both forward and backward edges
 74  std::vector<std::vector<std::pair<size_t, double>>> residual(N);
 75
 76  // Map to find reverse edge quickly
 77  std::map<std::pair<size_t, size_t>, size_t> edge_index;
 78
 79  for (auto&& [u, v, cap] : edges) {
 80    edge_index[{u, v}] = residual[u].size();
 81    residual[u].push_back({v, cap});
 82
 83    // Add reverse edge with 0 capacity if it doesn't exist
 84    if (edge_index.find({v, u}) == edge_index.end()) {
 85      edge_index[{v, u}] = residual[v].size();
 86      residual[v].push_back({u, 0});
 87    }
 88  }
 89
 90  std::vector<size_t> parent(N);
 91  double max_flow = 0;
 92
 93  // Find augmenting paths until none exist
 94  while (bfs_find_path(residual, source, sink, parent)) {
 95    // Find minimum residual capacity along the path
 96    double path_flow = std::numeric_limits<double>::max();
 97    for (size_t v = sink; v != source; v = parent[v]) {
 98      size_t u = parent[v];
 99      size_t idx = edge_index[{u, v}];
100      path_flow = std::min(path_flow, residual[u][idx].second);
101    }
102
103    // Update residual capacities
104    for (size_t v = sink; v != source; v = parent[v]) {
105      size_t u = parent[v];
106      size_t fwd_idx = edge_index[{u, v}];
107      size_t rev_idx = edge_index[{v, u}];
108
109      residual[u][fwd_idx].second -= path_flow;
110      residual[v][rev_idx].second += path_flow;
111    }
112
113    max_flow += path_flow;
114  }
115
116  return max_flow;
117}
118
119int main() {
120  std::cout << "=== Maximum Flow Problem ===" << std::endl;
121  std::cout << "Based on BGL Book Chapter 8" << std::endl << std::endl;
122
123  // Create a flow network
124  // This represents a transportation network where we want to find
125  // the maximum flow from source (0) to sink (7)
126  //
127  //         10        9
128  //     0 -----> 1 -----> 5
129  //     |        |  \     |
130  //   5 |      4 |   \ 15 | 10
131  //     v        v    \   v
132  //     2 -----> 3 -----> 7
133  //     |   4    |   15   ^
134  //   8 |      15|       /
135  //     v        v      / 10
136  //     4 -----> 6 ----/
137  //         15
138
139  std::cout << "Flow network (source=0, sink=7):" << std::endl;
140  std::cout << "Edges with capacities:" << std::endl;
141
142  std::vector<std::tuple<size_t, size_t, double>> edges = {
143      {0, 1, 10},
144      {0, 2, 5},
145      {0, 3, 15},
146      {1, 2, 4},
147      {1, 4, 9},
148      {1, 5, 15},
149      {2, 3, 4},
150      {2, 5, 8},
151      {3, 6, 30},
152      {4, 5, 15},
153      {4, 7, 10},
154      {5, 6, 15},
155      {5, 7, 10},
156      {6, 2, 6},
157      {6, 5, 4},
158      {6, 7, 10}
159  };
160
161  for (auto&& [u, v, cap] : edges) {
162    std::cout << "  " << u << " -> " << v << " : capacity " << cap << std::endl;
163  }
164  std::cout << std::endl;
165
166  size_t source = 0;
167  size_t sink = 7;
168  size_t N = 8;
169
170  double max_flow = edmonds_karp(N, edges, source, sink);
171
172  std::cout << "Maximum flow from " << source << " to " << sink << ": " << max_flow << std::endl;
173  std::cout << std::endl;
174
175  // Simpler example
176  std::cout << "=== Simple Example ===" << std::endl;
177  std::cout << "    10" << std::endl;
178  std::cout << "0 -----> 1" << std::endl;
179  std::cout << "|        |" << std::endl;
180  std::cout << "5|        |10" << std::endl;
181  std::cout << "v        v" << std::endl;
182  std::cout << "2 -----> 3" << std::endl;
183  std::cout << "    10" << std::endl;
184  std::cout << std::endl;
185
186  std::vector<std::tuple<size_t, size_t, double>> simple_edges = {
187      {0, 1, 10},
188      {0, 2, 5},
189      {1, 3, 10},
190      {2, 3, 10}
191  };
192
193  double simple_flow = edmonds_karp(4, simple_edges, 0, 3);
194  std::cout << "Maximum flow: " << simple_flow << std::endl;
195  std::cout << "(Limited by source outflow: 10 + 5 = 15)" << std::endl;
196
197  return 0;
198}

Building and Running the Example

First, configure and build the example:

# From the NWGraph root directory
mkdir -p build && cd build
cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make ch8_maxflow

Then run the example:

./examples/bgl-book/ch8_maxflow

The program computes the maximum flow through a sample network and identifies the minimum cut.

Sample Output

Flow Network - Maximum Flow

Source: A, Sink: H

Maximum flow: 7 units

Flow on each edge:
A -> B: 3/4
A -> C: 4/5
B -> D: 3/3
...

Minimum cut edges: {(B,D), (C,F)}

Key NWGraph Features Demonstrated

  • Directed graphs with capacities: Modeling flow networks

  • Augmenting path algorithms: Ford-Fulkerson method

  • Residual graphs: Tracking remaining capacity

  • Min-cut computation: Finding network bottlenecks

References

  • Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 4th Edition (2022), Chapter 24: Maximum Flow (Ford-Fulkerson, Edmonds-Karp, Push-Relabel)

  • Siek, Lee, and Lumsdaine. The Boost Graph Library (2002), Chapter 8

See Also