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 in the Edmonds-Karp variation.
Computes the maximum flow from source to destination in a weighted directed graph.
§Arguments
network: a wieghted directed graph.source: a stream source node.destination: a stream sink node.
§Returns
Returns a tuple of two values:
N::EdgeWeight: computed maximum flow;Vec<N::EdgeWeight>: the flow of each edge. The vector is indexed by the graph’s edge indices.
§Complexity
- Time complexity: O(|V||E|²).
- Auxiliary space: O(|V| + |E|).
where |V| is the number of nodes and |E| is the number of edges.
§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);