pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

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))\)

Signatures

pgr_maxCardinalityMatch(Edges SQL [, directed])

RETURNS SET OF (seq, edge_id, source, target)
OR EMPTY SET
Example:For a directed graph
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 |    9 |     11 |     16
   6 |   13 |     12 |     17
   7 |   18 |     13 |     14
   8 |    3 |     15 |     10
(8 rows)

Inner Queries

Edges SQL

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

Column Type 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-NUMERIC A positive value represents the existence of the edge (source, target).
coming ANY-NUMERIC A positive value represents the existence of the edge (target, source).

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERIC: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.