1 use petgraph::algo::ford_fulkerson;
2 use petgraph::prelude::Graph;
3 
4 #[test]
test_ford_fulkerson()5 fn test_ford_fulkerson() {
6     // Example from https://downey.io/blog/max-flow-ford-fulkerson-algorithm-explanation/
7     let mut graph = Graph::<usize, u16>::new();
8     let source = graph.add_node(0);
9     let _ = graph.add_node(1);
10     let _ = graph.add_node(2);
11     let destination = graph.add_node(3);
12     graph.extend_with_edges(&[(0, 1, 3), (0, 2, 2), (1, 2, 5), (1, 3, 2), (2, 3, 3)]);
13     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
14     assert_eq!(5, max_flow);
15 
16     // Example from https://brilliant.org/wiki/ford-fulkerson-algorithm/
17     let mut graph = Graph::<usize, f32>::new();
18     let source = graph.add_node(0);
19     let _ = graph.add_node(1);
20     let _ = graph.add_node(2);
21     let _ = graph.add_node(3);
22     let _ = graph.add_node(4);
23     let destination = graph.add_node(5);
24     graph.extend_with_edges(&[
25         (0, 1, 4.),
26         (0, 2, 3.),
27         (1, 3, 4.),
28         (2, 4, 6.),
29         (3, 2, 3.),
30         (3, 5, 2.),
31         (4, 5, 6.),
32     ]);
33     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
34     assert_eq!(7.0, max_flow);
35 
36     // Example from https://cp-algorithms.com/graph/edmonds_karp.html
37     let mut graph = Graph::<usize, f32>::new();
38     let source = graph.add_node(0);
39     let _ = graph.add_node(1);
40     let _ = graph.add_node(2);
41     let _ = graph.add_node(3);
42     let _ = graph.add_node(4);
43     let destination = graph.add_node(5);
44     graph.extend_with_edges(&[
45         (0, 1, 7.),
46         (0, 2, 4.),
47         (1, 3, 5.),
48         (1, 4, 3.),
49         (2, 1, 3.),
50         (2, 4, 2.),
51         (3, 5, 8.),
52         (4, 3, 3.),
53         (4, 5, 5.),
54     ]);
55     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
56     assert_eq!(10.0, max_flow);
57 
58     // Example from https://www.programiz.com/dsa/ford-fulkerson-algorithm (corrected: result not 6 but 5)
59     let mut graph = Graph::<u8, f32>::new();
60     let source = graph.add_node(0);
61     let _ = graph.add_node(1);
62     let _ = graph.add_node(2);
63     let _ = graph.add_node(3);
64     let _ = graph.add_node(4);
65     let destination = graph.add_node(5);
66     graph.extend_with_edges(&[
67         (0, 1, 8.),
68         (0, 2, 3.),
69         (1, 3, 9.),
70         (2, 3, 7.),
71         (2, 4, 4.),
72         (3, 5, 2.),
73         (4, 5, 5.),
74     ]);
75     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
76     assert_eq!(5.0, max_flow);
77 
78     let mut graph = Graph::<u8, u8>::new();
79     let source = graph.add_node(0);
80     let _ = graph.add_node(1);
81     let _ = graph.add_node(2);
82     let _ = graph.add_node(3);
83     let _ = graph.add_node(4);
84     let destination = graph.add_node(5);
85     graph.extend_with_edges(&[
86         (0, 1, 16),
87         (0, 2, 13),
88         (1, 2, 10),
89         (1, 3, 12),
90         (2, 1, 4),
91         (2, 4, 14),
92         (3, 2, 9),
93         (3, 5, 20),
94         (4, 3, 7),
95         (4, 5, 4),
96     ]);
97     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
98     assert_eq!(23, max_flow);
99 
100     // Example taken from https://medium.com/@jithmisha/solving-the-maximum-flow-problem-with-ford-fulkerson-method-3fccc2883dc7
101     let mut graph = Graph::<u8, u8>::new();
102     let source = graph.add_node(0);
103     let _ = graph.add_node(1);
104     let _ = graph.add_node(2);
105     let _ = graph.add_node(3);
106     let _ = graph.add_node(4);
107     let destination = graph.add_node(5);
108     graph.extend_with_edges(&[
109         (0, 1, 10),
110         (0, 2, 10),
111         (1, 2, 2),
112         (1, 3, 4),
113         (1, 4, 8),
114         (2, 4, 9),
115         (3, 5, 10),
116         (4, 3, 6),
117         (4, 5, 10),
118     ]);
119     let (max_flow, _) = ford_fulkerson(&graph, source, destination);
120     assert_eq!(19, max_flow);
121 }
122