pgr_maximumCardinalityMatching - Proposed¶

Name¶

pgr_maximumCardinalityMatching — Calculates a maximum cardinality matching in a graph.

Warning

These are proposed 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

Boost Graph Inside

Synopsis¶

Calculates a maximum cardinality matching in a directed/undirected graph.

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.

Characteristics:¶

The main characterics are:

Calculates one possible maximum cardinality matching in a graph.
The graph can be directed or undirected.
Running time: \(O( E*V * \alpha(E,V))\)
\(\alpha(E,V)\) is the inverse of the Ackermann function.

Signature Summary¶

pgr_MaximumCardinalityMatching(edges_sql)
pgr_MaximumCardinalityMatching(edges_sql, directed)

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

Signatures¶

Minimal signature¶

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

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

Example:

SELECT * FROM pgr_maximumCardinalityMatching(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table'
);
 seq | edge_id | 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 (id, edge_id, source, target) OR EMPTY SET

The complete signature calculates one possible maximum cardinality matching.

Example:

SELECT * FROM pgr_maximumCardinalityMatching(
    'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
    directed := false
);
 seq | edge_id | 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

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_id	`BIGINT`	Identifier of the edge in the original query(edges_sql).
source	`BIGINT`	Identifier of the first end point vertex of the edge.
target	`BIGINT`	Identifier of the second end point vertex of the edge.

pgRouting Manual (2.3)

pgr_maximumCardinalityMatching - Proposed