pgRouting Manual (2.3)

Applications of Maximum Flow

«  pgr_maxFlowBoykovKolmogorov - Proposed   ::   Contents   ::   pgr_maximumCardinalityMatching - Proposed  »

Applications of Maximum Flow

Maximum flow algorithms provide solutions to other graph problems.

Warning

These are proposed functions

  • They are not officially of the current release.
  • They likely will not be officially be part of the next release:
    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
    • Name might change.
    • Signature might change.
    • Functionality might change.
    • pgTap tests might be missing.
    • Might need c/c++ coding.
    • May lack documentation.
    • Documentation if any might need to be rewritten.
    • Documentation examples might need to be automatically generated.
    • Might need a lot of feedback from the comunity.
    • Might depend on a proposed function of pgRouting
    • Might depend on a deprecated function of pgRouting

Applications

Maximum cardinality matching

  • A matching or independent edge set in a graph is a set of edges without common vertices.
  • A maximum matching is a matching that contains the largest possible number of edges.
  • There may be many maximum matchings.
  • The graph can be directed or undirected.

The pgr_maximumCardinalityMatching - Proposed function can be used to calculate one such maximum matching.

Edge disjoint paths

In a undirected/directed graph, two paths are edge-disjoint(or edge-independant) if they do not have any internal edge in common.

While the number of maximum edge disjoint paths is fixed, there may be several different routes.

The pgr_edgeDisjointPaths - Proposed function returns the maximum number of paths and possible routes.

«  pgr_maxFlowBoykovKolmogorov - Proposed   ::   Contents   ::   pgr_maximumCardinalityMatching - Proposed  »