Module pathfinding::directed::edmonds_karp

Compute the maximum flow that can go through a directed graph using the Edmonds Karp algorithm.

This module contains several functions helping compute the flow on a given graph, as well as a structure which allows iterative modifications of the network. When the network is modified, the flow is recomputed and tries to take advantage of computations already performed on unchanged or augmented edges.

Structs

• Common
  Common fields.
• DenseCapacity
  Dense capacity and flow data.
• SparseCapacity
  Sparse capacity and flow data.

Traits

• EdmondsKarp
  Representation of capacity and flow data.

Functions

• edmonds_karp
  Compute the maximum flow and the minimal cut of a directed graph using the Edmonds Karp algorithm.
• edmonds_karp_dense
  Helper for the edmonds_karp function using an adjacency matrix for dense graphs.
• edmonds_karp_sparse
  Helper for the edmonds_karp function using adjacency maps for sparse graphs.

Type Aliases

• EKFlows
  Type alias for Edmonds-Karp maximum flow result.
• Edge
  Type alias for representing an edge in a graph