Function pathfinding::edmonds_karp_sparse
[−]
[src]
pub fn edmonds_karp_sparse<N, C, IC>(
vertices: &[N],
source: &N,
sink: &N,
caps: IC
) -> EKFlows<N, C> where
N: Eq + Hash + Clone,
C: Zero + Bounded + Signed + PartialOrd + Clone + Eq,
IC: IntoIterator<Item = ((N, N), C)>,
Compute the maximum flow that can go through a directed graph using the Edmonds Karp algorithm.
A maximum flow going from source
to sink
will be computed, and the various
flow values along with the total will be returned. A sparse representation will be
used to represent the edges.
vertices
is the collection of vertices in the graph.source
is the source node (the origin of the flow).sink
is the sink node (the target of the flow).caps
is an iterator-like object describing the positive capacities between the nodes.
Note that the capacity type C must be signed as the algorithm has to deal with negative residual capacities.
By creating an EdmondsKarp
structure, it is possible to adjust the capacities
after computing the maximum flow and rerun the algorithm without starting from
scratch.
Panics
This function panics if source
or sink
is not found in vertices
.