# pgRouting Manual (3.6)

## pgr_maxCardinalityMatch

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

Boost Graph Inside

Availability

- Version 3.4.0

  - Use `cost` and `reverse_cost` on the inner query

  - Results are ordered

  - Works for undirected graphs.

  - New signature

    - `pgr_maxCardinalityMatch(text)` returns only `edge` 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

pgr_maxCardinalityMatch(Edges SQL)
Returns set of `(edge)`
OR EMPTY SET

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 | `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.
`cost` | ANY-NUMERICAL |  | A positive value represents the existence of the edge (`source`, `target`).
`reverse_cost` | 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
--- | --- | ---
`edge` | `BIGINT` | Identifier of the edge in the original query.

## See Also

- Flow - Family of functions

- Migration guide

- 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