Function pathfinding::edmonds_karp_matrix [−] [src]

pub fn edmonds_karp_matrix<C>(
    source: usize, 
    sink: usize, 
    capacities: &SquareMatrix<C>
) -> EKFlows<usize, C> where
    C: Zero + Signed + Bounded + PartialOrd + Copy, 

Compute the maximum flow that can go through a directed graph using the Edmonds Karp algorithm. The graph is described via an adjacency matrix.

A maximum flow going from source to sink will be computed, and the various flow values along with the total will be returned.

  • source is the source node (the origin of the flow).
  • sink is the sink node (the target of the flow).
  • capacities is a matrix describing the capacities. capacities[i][j] represents the non-negative capacity from i to j.

Note that the capacity type C must be signed as the algorithm has to deal with negative residual capacities.

Panics

This function will panic if the capacities matrix is not a square matrix.