pgr_maxCardinalityMatch¶
pgr_maxCardinalityMatch
— Calculates a maximum cardinality matching in a
graph.
Availability
Version 3.4.0
Use
cost
andreverse_cost
on the inner queryResults are ordered
Works for undirected graphs.
New signature
pgr_maxCardinalityMatch(text)
returns onlyedge
column.
Deprecated signature
pgr_maxCardinalityMatch(text,boolean)
directed => false
when used.
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:
Works for undirected graphs.
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.
Running time: \(O( E*V * \alpha(E,V))\)
\(\alpha(E,V)\) is the inverse of the Ackermann function.
Signatures¶
(edge)
- Example:
Using all edges.
SELECT * FROM pgr_maxCardinalityMatch(
'SELECT id, source, target, cost, reverse_cost FROM edges');
edge
------
1
5
6
13
14
16
17
18
(8 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
Inner Queries¶
Edges SQL¶
SQL query, which should return a set of rows with the following columns:
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
A positive value represents the existence of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
A positive value represents the existence of the edge ( |
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns¶
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the edge in the original query. |
See Also¶
Indices and tables