# pgRouting Manual (2.5)

## pgr_maxCardinalityMatch - Proposed

## Synopsis

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

Warning

Experimental functions

- They are not officially of the current release.
- They likely will not be officially be part of the next release:
  - The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
  - Name might change.
  - Signature might change.
  - Functionality might change.
  - pgTap tests might be missing.
  - Might need c/c++ coding.
  - May lack documentation.
  - Documentation if any might need to be rewritten.
  - Documentation examples might need to be automatically generated.
  - Might need a lot of feedback from the comunity.
  - Might depend on a proposed function of pgRouting
  - Might depend on a deprecated function of pgRouting

Boost Graph Inside

Availability:

- Renamed 2.5.0, Previous name pgr_maximumCardinalityMatching
- New in 2.3.0

Characteristics

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

## Signature Summary

    pgr_MaximumCardinalityMatching(edges_sql) - Proposed
    pgr_MaximumCardinalityMatching(edges_sql, directed) - Proposed

    RETURNS SET OF (seq, edge_id, source, target)
        OR EMPTY SET

### Minimal Use

    pgr_MaximumCardinalityMatching(edges_sql)
    RETURNS SET OF (seq, edge_id, source, target) OR EMPTY SET

The minimal use calculates one possible maximum cardinality matching on a directed graph.

Example: |

    SELECT * FROM pgr_maxCardinalityMatch(
        'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table'
    );
     seq | edge | source | target
    -----+------+--------+--------
       1 |    1 |      1 |      2
       2 |    3 |      4 |      3
       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)

### Complete signature

    pgr_MaximumCardinalityMatching(edges_sql, directed)
    RETURNS SET OF (seq, edge_id, source, target) OR EMPTY SET

The complete signature calculates one possible maximum cardinality matching.

Example: |

    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)

## Description of the Signatures

### Description of the SQL 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, DOUBLE PRECISION

### Description of the parameters of the signatures

Column | Type | Description
--- | --- | ---
edges_sql | `TEXT` | SQL query as described above.
directed | `BOOLEAN` | (optional) Determines the type of the graph. Default TRUE.

### Description of the Result

Column | Type | Description
--- | --- | ---
seq | `INT` | Sequential value starting from 1.
edge | `BIGINT` | Identifier of the edge in the original query(edges_sql).
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
- http://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