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

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 (seq, edge_id, source, target)
OR EMPTY SET


Signatures¶

Minimal signature¶

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


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

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 (seq, edge_id, source, target) OR EMPTY SET


The complete signature calculates one possible maximum cardinality matching.

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

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.