pgr_maxCardinalityMatch¶
pgr_maxCardinalityMatch
— Calculates a maximum cardinality matching in a graph.
Availability
Version 3.0.0
Official function
Version 2.5.0
Renamed from
pgr_maximumCardinalityMatching
Proposed function
Version 2.3.0
New Experimental function
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))\)
\(\alpha(E,V)\) is the inverse of the Ackermann function.
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 

SQL query as described above. 

directed 


Determines the type of the graph.
 When 
Inner query¶
 Edges SQL
an SQL query, which should return a set of rows with the following columns:
Column 
Type 
Description 

id 

Identifier of the edge. 
source 

Identifier of the first end point vertex of the edge. 
target 

Identifier of the second end point vertex of the edge. 
going 

A positive value represents the existence of the edge ( 
coming 

A positive value represents the existence of the edge ( 
Where:
 ANYINTEGER
SMALLINT, INTEGER, BIGINT
 ANYNUMERIC
SMALLINT, INTEGER, BIGINT, REAL FLOAT
Result Columns¶
Column 
Type 
Description 

seq 

Sequential value starting from 1. 
edge 

Identifier of the edge in the original query. 
source 

Identifier of the first end point of the edge. 
target 

Identifier of the second end point of the edge. 
See Also¶
Indices and tables