graph_flow/
edmonds_karp.rs

1//! Edmonds-Karp maximum flow via BFS augmenting paths.
2
3use crate::FlowGraph;
4use std::collections::VecDeque;
5
6/// Computes the **maximum flow** from `source` to `sink` using the
7/// Edmonds-Karp algorithm (Ford-Fulkerson with BFS augmenting paths).
8///
9/// Edmonds-Karp improves on [`ford_fulkerson`] by always choosing the
10/// **shortest** augmenting path (fewest edges) via BFS rather than an
11/// arbitrary path via DFS. This simple change reduces the number of
12/// augmentations from potentially O(max_flow) to O(V · E), giving a
13/// polynomial runtime guarantee regardless of capacity values.
14///
15/// # How it works
16///
17/// 1. BFS finds the shortest augmenting path from `source` to `sink` in the
18///    residual graph.
19/// 2. The bottleneck capacity (minimum residual along the path) is computed.
20/// 3. Flow is pushed: each forward edge's flow increases, each reverse edge's
21///    residual capacity increases by the same amount.
22/// 4. Repeat until BFS finds no path.
23///
24/// # Arguments
25///
26/// - `graph` — a mutable [`FlowGraph`]; flow values are updated in place.
27/// - `source` — index of the source node.
28/// - `sink` — index of the sink node.
29///
30/// # Returns
31///
32/// The total maximum flow value sent from `source` to `sink`.
33///
34/// # Complexity
35///
36/// O(V · E²). Polynomial in all cases — safe for general use.
37///
38/// # Examples
39///
40/// ```
41/// use graph_flow::{FlowGraph, edmonds_karp};
42///
43/// // CLRS Figure 26.1 style network:
44/// //   0 --16-- 1 --12-- 3
45/// //   |        |        |
46/// //   13       4        20
47/// //   |        |        |
48/// //   2 --14-- 4 --7--- 5 (sink=5)
49/// //   Note: simplified 4-node version below.
50/// let mut g = FlowGraph::new(4);
51/// g.add_edge(0, 1, 10.0);
52/// g.add_edge(0, 2, 5.0);
53/// g.add_edge(1, 3, 10.0);
54/// g.add_edge(2, 3, 5.0);
55///
56/// let flow = edmonds_karp(&mut g, 0, 3);
57/// assert_eq!(flow, 15.0);
58/// ```
59///
60/// [`ford_fulkerson`]: crate::ford_fulkerson::ford_fulkerson
61pub fn edmonds_karp(graph: &mut FlowGraph, source: usize, sink: usize) -> f64 {
62    let mut total_flow = 0.0;
63
64    loop {
65        // BFS to find shortest augmenting path.
66        // parent[v] = (node u, edge index in adjacency[u]) that discovered v.
67        let parent = bfs_path(graph, source, sink);
68
69        match parent {
70            None => break, // No augmenting path — max flow reached.
71            Some(parent) => {
72                // Find bottleneck along the path.
73                let bottleneck = path_bottleneck(graph, &parent, source, sink);
74
75                // Augment flow along the path (walk from sink back to source).
76                let mut node = sink;
77                while node != source {
78                    let (prev, edge_idx) = parent[node].unwrap();
79                    graph.push_flow(prev, edge_idx, bottleneck);
80                    node = prev;
81                }
82
83                total_flow += bottleneck;
84            }
85        }
86    }
87
88    total_flow
89}
90
91/// BFS over the residual graph from `source` to `sink`.
92///
93/// Returns `Some(parent)` where `parent[v] = Some((u, edge_idx))` encodes
94/// the edge `u → v` used to reach `v`, or `None` if `sink` is unreachable.
95fn bfs_path(graph: &FlowGraph, source: usize, sink: usize) -> Option<Vec<Option<(usize, usize)>>> {
96    let n = graph.node_count();
97    let mut parent: Vec<Option<(usize, usize)>> = vec![None; n];
98    let mut visited = vec![false; n];
99    let mut queue = VecDeque::new();
100
101    visited[source] = true;
102    queue.push_back(source);
103
104    while let Some(node) = queue.pop_front() {
105        if node == sink {
106            return Some(parent);
107        }
108
109        for (edge_idx, edge) in graph.adjacency[node].iter().enumerate() {
110            if !visited[edge.to] && edge.residual() > 0.0 {
111                visited[edge.to] = true;
112                parent[edge.to] = Some((node, edge_idx));
113                queue.push_back(edge.to);
114            }
115        }
116    }
117
118    None // sink not reached
119}
120
121/// Computes the bottleneck (minimum residual) along the BFS path from
122/// `source` to `sink` encoded in `parent`.
123fn path_bottleneck(
124    graph: &FlowGraph,
125    parent: &[Option<(usize, usize)>],
126    source: usize,
127    sink: usize,
128) -> f64 {
129    let mut bottleneck = f64::INFINITY;
130    let mut node = sink;
131
132    while node != source {
133        let (prev, edge_idx) = parent[node].unwrap();
134        bottleneck = bottleneck.min(graph.adjacency[prev][edge_idx].residual());
135        node = prev;
136    }
137
138    bottleneck
139}
graph_flow/edmonds_karp.rs

graph_flow/
edmonds_karp.rs
