pgr_maxCardinalityMatch - pgRouting Manual (3.3)

Description

The main characteristics are:

• Works for undirected graphs.

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

  • Calculates one possible maximum cardinality matching in a graph.

• Running time: \(O( E*V * \alpha(E,V))\)

  • \(\alpha(E,V)\) is the inverse of the Ackermann function .

Signatures

Example :

Using all edges.

SELECT * FROM pgr_maxCardinalityMatch(
  'SELECT id, source, target, cost AS going, reverse_cost AS coming
  FROM edges');
 seq  edge  source  target
-----+------+--------+--------
   1     6       1       3
   2    17       2       4
   3     1       5       6
   4    14       8       9
   5     3      10      15
   6     9      11      16
   7    13      12      17
   8    18      13      14
(8 rows)

Parameters

Inner Queries

Result Columns

See Also

• Flow - Family of functions

• https://www.boost.org/libs/graph/doc/maximum_matching.html

• https://en.wikipedia.org/wiki/Matching_%28graph_theory%29

• https://en.wikipedia.org/wiki/Ackermann_function

Indices and tables

• Index

• Search Page