# pgr_maxCardinalityMatch¶

pgr_maxCardinalityMatch — Calculates a maximum cardinality matching in a graph.

Availability

• Version 3.3.3

• directed optional parameter ignored and removed from the documentation as the algorithm works only on undirected graphs

• 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))$$

## Signatures¶

pgr_maxCardinalityMatch(Edges SQL)
RETURNS SET OF (seq, edge_id, source, target)
OR EMPTY SET
Example:

Using all edges.

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 |    3 |     10 |     15
6 |    9 |     11 |     16
7 |   13 |     12 |     17
8 |   18 |     13 |     14
(8 rows)



## Parameters¶

Parameter

Type

Description

Edges SQL

TEXT

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

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-NUMERICAL

A positive value represents the existence of the edge (source, target).

coming

ANY-NUMERICAL

-1

A positive value represents the existence of the edge (target, source)

Where:

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

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.