pgr_maxCardinalityMatch¶
pgr_maxCardinalityMatch
— Calculates a maximum cardinality matching in a
graph.

Boost Graph Inside¶
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 a directed graph
SELECT * FROM pgr_maxCardinalityMatch(
'SELECT id, source, target, cost AS going, reverse_cost AS coming
FROM edges');
seq | edge | source | target
-----+------+--------+--------
1 | 6 | 1 | 3
2 | 17 | 2 | 4
3 | 1 | 5 | 6
4 | 14 | 8 | 9
5 | 9 | 11 | 16
6 | 13 | 12 | 17
7 | 18 | 13 | 14
8 | 3 | 15 | 10
(8 rows)
Inner Queries¶
Edges SQL¶
SQL query, which should return a set of rows with the following columns:
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the edge. |
|
|
Identifier of the first end point vertex of the edge. |
|
|
Identifier of the second end point vertex of the edge. |
|
|
A positive value represents the existence of the edge
( |
|
|
A positive value represents the existence of the edge
( |
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC
SMALLINT, INTEGER, BIGINT, REAL FLOAT
Result Columns¶
Column |
Type |
Description |
---|---|---|
|
|
Sequential value starting from 1. |
|
|
Identifier of the edge in the original query. |
|
|
Identifier of the first end point of the edge. |
|
|
Identifier of the second end point of the edge. |
See Also¶
Indices and tables