Function pathfinding::edmondskarp [−] [src]

pub fn edmondskarp<N, C, IC>(
    vertices: &[N], 
    source: &N, 
    sink: &N, 
    caps: IC
) -> (Vec<((N, N), C)>, C) where
    N: Eq + Hash + Clone,
    C: Zero + Bounded + Signed + PartialOrd + Copy,
    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.

  • 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.