pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

Boost Graph Inside

Availability

• Version 3.4.0

  • Use cost and reverse_cost on the inner query

  • Results are ordered

  • Works for undirected graphs.

  • New signature

    • pgr_maxCardinalityMatch(text) returns only edge column.

  • Deprecated signature

    • pgr_maxCardinalityMatch(text,boolean)

      • directed => false when used.

• 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 (edge)

OR EMPTY SET

Example:

Using all edges.

SELECT * FROM pgr_maxCardinalityMatch(
  'SELECT id, source, target, cost, reverse_cost FROM edges');
 edge
------
    1
    5
    6
   13
   14
   16
   17
   18
(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.
cost	ANY-NUMERICAL		A positive value represents the existence of the edge (source, target).
reverse_cost	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
edge	BIGINT	Identifier of the edge in the original query.

See Also

• Flow - Family of functions

• Migration guide

• 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