# pgRouting Manual (3.3)

## pgr_maxCardinalityMatch

- Supported versions: Latest (3.1) 3.0

- Unsupported versions: 2.6 2.5 2.4 2.3

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

- Flow - Family of functions

- https://www.boost.org/libs/graph/doc/maximum_matching.html

- https://en.wikipedia.org/wiki/Matching_%28graph_theory%29

- https://en.wikipedia.org/wiki/Ackermann_function

Indices and tables

- Index

- Search Page