# pgr_maxCardinalityMatch¶

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

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 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.