Function petgraph::algo::ford_fulkerson::ford_fulkerson
source · pub fn ford_fulkerson<N>(
network: N,
source: N::NodeId,
destination: N::NodeId,
) -> (N::EdgeWeight, Vec<N::EdgeWeight>)where
N: NodeCount + EdgeCount + IntoEdgesDirected + EdgeIndexable + NodeIndexable + DataMap + Visitable,
N::EdgeWeight: Sub<Output = N::EdgeWeight> + PositiveMeasure,
Expand description
[Generic] Ford-Fulkerson algorithm.
Computes the maximum flow of a weighted directed graph.
If it terminates, it returns the maximum flow and also the computed edge flows.
§Example
use petgraph::Graph;
use petgraph::algo::ford_fulkerson;
// Example from CLRS book
let mut graph = Graph::<u8, u8>::new();
let source = graph.add_node(0);
let _ = graph.add_node(1);
let _ = graph.add_node(2);
let _ = graph.add_node(3);
let _ = graph.add_node(4);
let destination = graph.add_node(5);
graph.extend_with_edges(&[
(0, 1, 16),
(0, 2, 13),
(1, 2, 10),
(1, 3, 12),
(2, 1, 4),
(2, 4, 14),
(3, 2, 9),
(3, 5, 20),
(4, 3, 7),
(4, 5, 4),
]);
let (max_flow, _) = ford_fulkerson(&graph, source, destination);
assert_eq!(23, max_flow);