pgr_maxCardinalityMatch - pgRouting Manual (3.2)

Description

The main characteristics are:

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

• The graph can be directed or undirected .

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

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

Signatures

pgr_maxCardinalityMatch(Edges SQL [, directed])

RETURNS SET OF (seq, edge_id, source, target)
OR EMPTY SET

Example :

For an undirected graph

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

Parameters

Inner query

Edges SQL :

an SQL query, which should return a set of rows with the following columns:

Where:

ANY-INTEGER :

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC :

SMALLINT, INTEGER, BIGINT, REAL FLOAT

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