Function pathfinding::edmonds_karp_dense [−] [src]

pub fn edmonds_karp_dense<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,
    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 dense matrix 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.