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 |
ANY-INTEGER |
Identifier of the edge. |
source |
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
target |
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
going |
ANY-NUMERIC |
A positive value represents the existence of the edge (source , target ). |
coming |
ANY-NUMERIC |
A positive value represents the existence of the edge (target , source ). |
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
ANY-NUMERIC: | 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