algorithms_edu/algo/graph/network_flow/
edmonds_karp.rs

1use super::{MaxFlowSolver, NetworkFlowAdjacencyList};
2use std::collections::VecDeque;
3
4pub struct EdmondsKarpSolver {}
5
6impl MaxFlowSolver for EdmondsKarpSolver {
7    fn max_flow(graph: &mut NetworkFlowAdjacencyList) -> i32 {
8        let n = graph.node_count();
9        let mut visited = vec![0; n];
10        let mut visited_token = 1;
11
12        let mut bfs = |visited_token| {
13            let mut q = VecDeque::with_capacity(n);
14            let mut prev = vec![None; n];
15            visited[graph.source] = visited_token;
16            q.push_back(graph.source);
17            while let Some(node) = q.pop_front() {
18                if node == graph.sink {
19                    break;
20                }
21                for edge in &graph[node] {
22                    let _edge = edge.borrow();
23                    if _edge.reamaining_capacity() > 0 && visited[_edge.to] != visited_token {
24                        visited[_edge.to] = visited_token;
25                        prev[_edge.to] = Some(edge.clone());
26                        q.push_back(_edge.to);
27                    }
28                }
29            }
30            if prev[graph.sink].is_none() {
31                return 0;
32            }
33
34            let mut bottleneck = i32::MAX;
35            let mut node = graph.sink;
36
37            while let Some(prev_edge) = &prev[node] {
38                bottleneck = std::cmp::min(bottleneck, prev_edge.borrow().reamaining_capacity());
39                node = prev_edge.borrow().from;
40            }
41
42            node = graph.sink;
43
44            while let Some(prev_edge) = &prev[node] {
45                prev_edge.borrow_mut().augment(bottleneck);
46                node = prev_edge.borrow().from;
47            }
48
49            bottleneck
50        };
51        let mut flow = 0;
52        let mut f = -1;
53        while f != 0 {
54            f = bfs(visited_token);
55
56            flow += f;
57            visited_token += 1;
58        }
59        flow
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    fn test_max_flow(n: usize, edges: &[(usize, usize, i32)], expected_max_flow: i32) {
68        let mut graph = NetworkFlowAdjacencyList::from_edges(n, edges);
69        let max_flow = EdmondsKarpSolver::max_flow(&mut graph);
70        assert_eq!(max_flow, expected_max_flow);
71    }
72
73    #[test]
74    fn test_small_graph() {
75        test_max_flow(
76            6,
77            &[
78                // Source edges
79                (5, 0, 10),
80                (5, 1, 10),
81                // Sink edges
82                (2, 4, 10),
83                (3, 4, 10),
84                // Middle edges
85                (0, 1, 2),
86                (0, 2, 4),
87                (0, 3, 8),
88                (1, 3, 9),
89                (3, 2, 6),
90            ],
91            19,
92        );
93    }
94
95    #[test]
96    fn test_disconnected() {
97        test_max_flow(4, &[(3, 0, 9), (1, 2, 9)], 0);
98    }
99
100    #[test]
101    fn test_medium_graph() {
102        test_max_flow(
103            12,
104            &[
105                // from source
106                (11, 0, 5),
107                (11, 1, 20),
108                (11, 2, 10),
109                // to sink
110                (7, 10, 7),
111                (8, 10, 15),
112                (9, 10, 60),
113                // middle
114                (0, 1, 3),
115                (0, 5, 4),
116                (1, 4, 14),
117                (1, 5, 14),
118                (2, 1, 5),
119                (2, 3, 4),
120                (3, 4, 3),
121                (3, 9, 11),
122                (4, 6, 4),
123                (4, 8, 22),
124                (5, 6, 8),
125                (5, 7, 3),
126                (6, 7, 12),
127                (7, 8, 9),
128                (8, 9, 11),
129            ],
130            29,
131        );
132    }
133}
algorithms_edu/algo/graph/network_flow/edmonds_karp.rs

algorithms_edu/algo/graph/network_flow/
edmonds_karp.rs
