809 Fundamental

809-max-flow-ford-fulkerson — Max Flow (Ford-Fulkerson with BFS)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "809-max-flow-ford-fulkerson — Max Flow (Ford-Fulkerson with BFS)" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Maximum flow (Ford-Fulkerson, 1956) finds the maximum amount that can flow from a source to a sink in a capacitated network. Key difference from OCaml: 1. **Residual graph**: Both languages maintain residual capacities as a 2D matrix; the backward edge increase is the key insight enabling augmentation undoing.

Tutorial

The Problem

Maximum flow (Ford-Fulkerson, 1956) finds the maximum amount that can flow from a source to a sink in a capacitated network. The Edmonds-Karp variant uses BFS (finding shortest augmenting paths) and runs in O(VE²). Applications include network traffic routing, image segmentation (min-cut = max-flow), bipartite matching (König's theorem), and supply chain optimization. It is one of the most practically important algorithms in operations research.

🎯 Learning Outcomes

• Implement Edmonds-Karp: BFS to find shortest augmenting paths repeatedly

• Maintain a residual capacity matrix cap[u][v] that decreases with forward flow and increases backward

• Find path flow as the minimum capacity along the augmenting path

• Update residual capacities: decrease forward, increase backward (enabling un-doing)

• Apply the max-flow min-cut theorem: max flow = min cut capacity

Code Example

#![allow(clippy::all)]
//! # Max Flow (Ford-Fulkerson with BFS)
use std::collections::VecDeque;
pub fn max_flow(n: usize, edges: &[(usize, usize, i32)], source: usize, sink: usize) -> i32 {
    let mut cap = vec![vec![0i32; n]; n];
    for &(u, v, c) in edges {
        cap[u][v] += c;
    }
    let mut flow = 0;
    loop {
        let mut parent = vec![None; n];
        let mut q = VecDeque::new();
        q.push_back(source);
        parent[source] = Some(source);
        while let Some(u) = q.pop_front() {
            if u == sink {
                break;
            }
            for v in 0..n {
                if parent[v].is_none() && cap[u][v] > 0 {
                    parent[v] = Some(u);
                    q.push_back(v);
                }
            }
        }
        if parent[sink].is_none() {
            break;
        }
        let mut path_flow = i32::MAX;
        let mut v = sink;
        while v != source {
            let u = parent[v].unwrap();
            path_flow = path_flow.min(cap[u][v]);
            v = u;
        }
        v = sink;
        while v != source {
            let u = parent[v].unwrap();
            cap[u][v] -= path_flow;
            cap[v][u] += path_flow;
            v = u;
        }
        flow += path_flow;
    }
    flow
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_flow() {
        assert_eq!(
            max_flow(
                4,
                &[(0, 1, 10), (0, 2, 10), (1, 2, 2), (1, 3, 4), (2, 3, 9)],
                0,
                3
            ),
            13
        );
    }
}

(* 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)

Key Differences

Residual graph: Both languages maintain residual capacities as a 2D matrix; the backward edge increase is the key insight enabling augmentation undoing.

BFS choice: Edmonds-Karp (BFS augmenting paths) guarantees polynomial time; DFS (Ford-Fulkerson) can cycle with irrational capacities — BFS is strictly better.

Push-relabel: The push-relabel algorithm (Goldberg-Tarjan) achieves O(V²E) and is faster in practice; available in petgraph's flow module for Rust.

Image segmentation: Min-cut (dual to max-flow) is used in s-t graph cut for image segmentation; computer vision libraries use this heavily.

OCaml Approach

OCaml implements with Array.make_matrix n n 0 for capacities and Array.make n None for parent tracking. The BFS uses Queue.t. OCaml's Array.set updates capacities. The Ocamlgraph.Flow.Goldberg module implements push-relabel (faster in practice). Flow applications in OCaml appear in network simulation and bioinformatics pipelines.

Full Source

#![allow(clippy::all)]
//! # Max Flow (Ford-Fulkerson with BFS)
use std::collections::VecDeque;
pub fn max_flow(n: usize, edges: &[(usize, usize, i32)], source: usize, sink: usize) -> i32 {
    let mut cap = vec![vec![0i32; n]; n];
    for &(u, v, c) in edges {
        cap[u][v] += c;
    }
    let mut flow = 0;
    loop {
        let mut parent = vec![None; n];
        let mut q = VecDeque::new();
        q.push_back(source);
        parent[source] = Some(source);
        while let Some(u) = q.pop_front() {
            if u == sink {
                break;
            }
            for v in 0..n {
                if parent[v].is_none() && cap[u][v] > 0 {
                    parent[v] = Some(u);
                    q.push_back(v);
                }
            }
        }
        if parent[sink].is_none() {
            break;
        }
        let mut path_flow = i32::MAX;
        let mut v = sink;
        while v != source {
            let u = parent[v].unwrap();
            path_flow = path_flow.min(cap[u][v]);
            v = u;
        }
        v = sink;
        while v != source {
            let u = parent[v].unwrap();
            cap[u][v] -= path_flow;
            cap[v][u] += path_flow;
            v = u;
        }
        flow += path_flow;
    }
    flow
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_flow() {
        assert_eq!(
            max_flow(
                4,
                &[(0, 1, 10), (0, 2, 10), (1, 2, 2), (1, 3, 4), (2, 3, 9)],
                0,
                3
            ),
            13
        );
    }
}

(* 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)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_flow() {
        assert_eq!(
            max_flow(
                4,
                &[(0, 1, 10), (0, 2, 10), (1, 2, 2), (1, 3, 4), (2, 3, 9)],
                0,
                3
            ),
            13
        );
    }
}

Deep Comparison

OCaml vs Rust: Max Flow Ford Fulkerson

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement min-cut identification: after computing max flow, run BFS on the residual graph from source; the min cut is the set of edges from reachable to unreachable vertices.

Use max-flow to solve maximum bipartite matching: create a source connected to all left vertices, all right vertices connected to sink, and run max-flow.

Implement the push-relabel algorithm (preflow-push) and benchmark it against Edmonds-Karp on dense graphs with 100+ nodes.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust