Applications of Maximum Flow¶
- pgr_maximumCardinalityMatching - Proposed - Calculates a maximum cardinality matching in a graph.
- pgr_edgeDisjointPaths - Proposed - Calculates edge disjoint paths between two groups of vertices.
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.