pgr_maxCardinalityMatch
pgr_maxCardinalityMatch
— Calculates a maximum cardinality matching in a graph.
Availability
 Version 3.0.0
 Version 2.5.0
 Renamed from
pgr_maximumCardinalityMatching
 Proposed function
 Version 2.3.0
 New Experimental function
Support
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
pgr_maxCardinalityMatch(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:  an SQL query, which should return a set of rows with the following columns: 
Column 
Type 
Description 
id 
ANYINTEGER 
Identifier of the edge. 
source 
ANYINTEGER 
Identifier of the first end point vertex of the edge. 
target 
ANYINTEGER 
Identifier of the second end point vertex of the edge. 
going 
ANYNUMERIC 
A positive value represents the existence of the edge (source , target ). 
coming 
ANYNUMERIC 
A positive value represents the existence of the edge (target , source ). 
Where:
ANYINTEGER:  SMALLINT, INTEGER, BIGINT 
ANYNUMERIC:  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. 
source 
BIGINT 
Identifier of the first end point of the edge. 
target 
BIGINT 
Identifier of the second end point of the edge. 
See Also
Indices and tables