pgr_maxCardinalityMatch - Proposed

Synopsis

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

Warning

Experimental functions

  • They are not officially of the current release.
  • They likely will not be officially be part of the next release:
    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
    • Name might change.
    • Signature might change.
    • Functionality might change.
    • pgTap tests might be missing.
    • Might need c/c++ coding.
    • May lack documentation.
    • Documentation if any might need to be rewritten.
    • Documentation examples might need to be automatically generated.
    • Might need a lot of feedback from the comunity.
    • Might depend on a proposed function of pgRouting
    • Might depend on a deprecated function of pgRouting
_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) - Proposed
pgr_MaximumCardinalityMatching(edges_sql, directed) - Proposed

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)

Description of the Signatures

Description of the SQL query

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, DOUBLE PRECISION

Description of the parameters of the signatures

Column Type Description
edges_sql TEXT SQL query as described above.
directed BOOLEAN (optional) Determines the type of the graph. Default TRUE.

Description of the Result

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.