pgr_maxCardinalityMatch  pgRouting Manual (3.3)
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