# 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

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.

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.

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.