pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

_images/boost-inside.jpeg

Boost Graph Inside

Availability

  • Official on v3.0.0
  • Renamed on v2.5.0
  • Experimental on v2.3.0
    • pgr_maximumCardinalityMatching

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

Summary

pgr_MaximumCardinalityMatching(edges_sql)
pgr_MaximumCardinalityMatching(edges_sql, directed)

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

Using defaults

pgr_MaximumCardinalityMatching(edges_sql)
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 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
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

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.