Function petgraph::algo::ford_fulkerson::ford_fulkerson

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,

[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);