pgr_maxCardinalityMatch

Synopsis

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

_images/boost-inside.jpeg

Boost Graph Inside

Availability:

  • Renamed 2.5.0, Previous name pgr_maximumCardinalityMatching
  • New in 2.3.0

Characteristics

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

Signature Summary

pgr_MaximumCardinalityMatching(edges_sql)
pgr_MaximumCardinalityMatching(edges_sql, directed)

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

Minimal Use

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

The minimal use calculates one possible maximum cardinality matching on a directed graph.

Example:
SELECT * FROM pgr_maxCardinalityMatch(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table'
);
 seq | edge | source | target
-----+------+--------+--------
   1 |    1 |      1 |      2
   2 |    3 |      4 |      3
   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)

Complete signature

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

The complete signature calculates one possible maximum cardinality matching.

Example:
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

Parameter Type Default Description
edges_sql TEXT   SQL query as described above.
directed BOOLEAN true Determines the type of the graph. - When true Graph is considered Directed - When false the graph is considered as Undirected.

Inner query

edges_sql

edges_sql:an 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(edges_sql).
source BIGINT Identifier of the first end point of the edge.
target BIGINT Identifier of the second end point of the edge.