# pgr_maximumCardinalityMatching - Proposed¶

## Name¶

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

Warning

These are proposed 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

## Synopsis¶

Calculates a maximum cardinality matching in a directed/undirected graph.

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

## Characteristics:¶

- The main characterics are:
- 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.

- Calculates

## Signature Summary¶

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

## Signatures¶

### Minimal signature¶

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

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

Example: |
---|

```
SELECT * FROM pgr_maximumCardinalityMatching(
'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table'
);
seq | edge_id | 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 (id, edge_id, source, target) OR EMPTY SET
```

The complete signature calculates one possible maximum cardinality matching.

Example: |
---|

```
SELECT * FROM pgr_maximumCardinalityMatching(
'SELECT id, source, target, cost AS going, reverse_cost AS coming FROM edge_table',
directed := false
);
seq | edge_id | 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_id |
BIGINT |
Identifier of the edge in the original query(edges_sql). |

source |
BIGINT |
Identifier of the first end point vertex of the edge. |

target |
BIGINT |
Identifier of the second end point vertex of the edge. |