pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

Boost Graph Inside

Availability

• Version 3.3.3

  • directed optional parameter ignored and removed from the documentation as the algorithm works only on undirected graphs

• Version 3.0.0

  • Official function

• Version 2.5.0

  • Renamed from pgr_maximumCardinalityMatching

  • Proposed function

• Version 2.3.0

  • New Experimental function

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

pgr_maxCardinalityMatch(Edges SQL)

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

OR EMPTY SET

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

Parameter	Type	Description
Edges SQL	TEXT	Edges SQL as described below.

Inner Queries

Edges SQL

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

Column	Type	Default	Description
id	ANY-INTEGER		Identifier of the edge.
source	ANY-INTEGER		Identifier of the first end point vertex of the edge.
target	ANY-INTEGER		Identifier of the second end point vertex of the edge.
going	ANY-NUMERICAL		A positive value represents the existence of the edge (source, target).
coming	ANY-NUMERICAL	-1	A positive value represents the existence of the edge (target, source)

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Column	Type	Description
seq	INT	Sequential value starting from 1.
edge	BIGINT	Identifier of the edge in the original query.
source	BIGINT	Identifier of the first end point of the edge.
target	BIGINT	Identifier of the second end point of the edge.

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