809. Max Flow: Ford-Fulkerson with BFS (Edmonds-Karp)

Difficulty: 5 Level: Master Find the maximum flow through a network from source to sink using BFS augmenting paths — O(V × E²) with guaranteed termination and integer-optimal solutions.

The Problem This Solves

Maximum flow models any problem where you're maximising throughput through a constrained network: bandwidth allocation across internet links, pipeline capacity for oil or water, maximum number of edge-disjoint paths (for redundancy), and bipartite matching (which reduces to max-flow). The max-flow min-cut theorem — that maximum flow equals minimum cut capacity — is one of the most elegant results in combinatorial optimisation, with direct applications in computer vision (image segmentation as a graph cut problem). Edmonds-Karp specifies Fulkerson's algorithm with BFS to find the shortest augmenting path (by hop count). This eliminates the pathological cases of pure Ford-Fulkerson that can loop forever on irrational capacities, and gives the O(VE²) bound.

The Intuition

Maintain a residual capacity matrix: `cap[u][v]` is how much more flow can be sent from u to v. Initially this equals the original capacity. Find any path from source to sink with positive residual capacity (augmenting path). Send as much flow as possible along this path (bottleneck = minimum edge capacity). Update residuals: decrease forward edges, increase backward edges. Repeat until no augmenting path exists. The backward edge `cap[v][u] += flow` is the key insight — it allows "undoing" flow on a path by sending flow backwards. BFS finds shortest augmenting paths, giving the Edmonds-Karp variant.

How It Works in Rust

use std::collections::VecDeque;

// O(V × E²) — BFS finds shortest augmenting paths each iteration
// cap: V×V residual capacity matrix (modified in-place)
fn max_flow(cap: &mut Vec<Vec<i64>>, src: usize, snk: usize) -> i64 {
 let n = cap.len();
 let mut total = 0i64;

 loop {
     // BFS to find an augmenting path
     let mut parent = vec![usize::MAX; n];
     parent[src] = src;
     let mut deque = VecDeque::from([src]);

     'bfs: while let Some(u) = deque.pop_front() {
         for v in 0..n {
             if parent[v] == usize::MAX && cap[u][v] > 0 {
                 parent[v] = u;
                 if v == snk { break 'bfs; }
                 deque.push_back(v);
             }
         }
     }

     if parent[snk] == usize::MAX { break; }  // no augmenting path

     // Find bottleneck: min capacity along the path
     let mut flow = i64::MAX;
     let mut v = snk;
     while v != src { let u = parent[v]; flow = flow.min(cap[u][v]); v = u; }

     // Update residual capacities
     v = snk;
     while v != src {
         let u = parent[v];
         cap[u][v] -= flow;   // forward edge: consume capacity
         cap[v][u] += flow;   // backward edge: allow cancellation
         v = u;
     }
     total += flow;
 }
 total
}

The dense adjacency matrix `Vec<Vec<i64>>` is used here (O(V²) space) because max-flow algorithms naturally need to look up `cap[u][v]` and `cap[v][u]` in O(1). For sparse graphs, an edge-list representation with forward/backward edge pairs would be more memory-efficient.

What This Unlocks

Bipartite matching: model as a flow network (source → left nodes → right nodes → sink, all capacity 1); max-flow gives maximum matching. Hungarian algorithm is an alternative but max-flow generalises to weighted matching.
Image segmentation (graph cuts): model pixels as nodes, similarity as edge capacities; min-cut separates foreground from background. The min-cut equals max-flow by the max-flow min-cut theorem.
Network reliability: maximum number of edge-disjoint paths equals max-flow with unit capacities — measuring how many link failures a network can survive.

Key Differences

Concept	OCaml	Rust
Residual matrix	`int array array`	`Vec<Vec<i64>>` modified in-place
BFS queue	`Queue.t`	`VecDeque<usize>`
Path tracking	`parent` array or `Hashtbl`	`Vec<usize>` with `usize::MAX` as sentinel
Bottleneck scan	Recursive path walk	Iterative `while v != src` loop
Break from inner BFS	`raise Exit` exception	`break 'bfs` labelled break

// Edmonds-Karp Max Flow — BFS augmenting paths, O(VE²)
use std::collections::VecDeque;

fn max_flow(cap: &mut Vec<Vec<i64>>, src: usize, snk: usize) -> i64 {
    let n = cap.len();
    let mut total = 0i64;

    loop {
        // BFS to find augmenting path
        let mut parent = vec![usize::MAX; n];
        parent[src] = src;
        let mut deque = VecDeque::from([src]);

        while let Some(u) = deque.pop_front() {
            if u == snk { break; }
            for v in 0..n {
                if parent[v] == usize::MAX && cap[u][v] > 0 {
                    parent[v] = u;
                    deque.push_back(v);
                }
            }
        }

        if parent[snk] == usize::MAX { break; } // no augmenting path

        // Find bottleneck
        let mut flow = i64::MAX;
        let mut v = snk;
        while v != src {
            let u = parent[v];
            flow = flow.min(cap[u][v]);
            v = u;
        }

        // Update residual
        v = snk;
        while v != src {
            let u = parent[v];
            cap[u][v] -= flow;
            cap[v][u] += flow;
            v = u;
        }
        total += flow;
    }
    total
}

fn main() {
    let n = 6;
    let mut cap = vec![vec![0i64; n]; n];
    let mut set = |u: usize, v: usize, c: i64| cap[u][v] = c;
    set(0,1,16); set(0,2,13);
    set(1,2,10); set(1,3,12);
    set(2,1, 4); set(2,4,14);
    set(3,2, 9); set(3,5,20);
    set(4,3, 7); set(4,5, 4);

    println!("Max flow (0->5): {}  (expected 23)", max_flow(&mut cap, 0, 5));
}

(* Edmonds-Karp Max Flow — BFS augmenting paths, O(VE²) *)
open Queue

let max_flow_bfs cap n src snk =
  let cap = Array.init n (fun i -> Array.copy cap.(i)) in  (* mutable copy *)
  let total = ref 0 in

  let rec augment () =
    (* BFS to find augmenting path *)
    let parent = Array.make n (-1) in
    parent.(src) <- src;
    let q = Queue.create () in
    Queue.push src q;
    let found = ref false in
    while not (Queue.is_empty q) && not !found do
      let u = Queue.pop q in
      for v = 0 to n - 1 do
        if parent.(v) = -1 && cap.(u).(v) > 0 then begin
          parent.(v) <- u;
          if v = snk then found := true
          else Queue.push v q
        end
      done
    done;
    if !found then begin
      (* Find bottleneck *)
      let flow = ref max_int in
      let v = ref snk in
      while !v <> src do
        let u = parent.(!v) in
        flow := min !flow cap.(u).(!v);
        v    := u
      done;
      (* Update residual capacities *)
      let v = ref snk in
      while !v <> src do
        let u = parent.(!v) in
        cap.(u).(!v) <- cap.(u).(!v) - !flow;
        cap.(!v).(u) <- cap.(!v).(u) + !flow;
        v := u
      done;
      total := !total + !flow;
      augment ()
    end
  in
  augment ();
  !total

let () =
  let n = 6 in
  let cap = Array.make_matrix n n 0 in
  let set u v c = cap.(u).(v) <- c in
  set 0 1 16; set 0 2 13;
  set 1 2 10; set 1 3 12;
  set 2 1  4; set 2 4 14;
  set 3 2  9; set 3 5 20;
  set 4 3  7; set 4 5  4;
  Printf.printf "Max flow (0->5): %d  (expected 23)\n" (max_flow_bfs cap n 0 5)