1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
..
****************************************************************************
pgRouting Manual
Copyright(c) pgRouting Contributors
This documentation is licensed under a Creative Commons Attribution-Share
Alike 3.0 License: https://creativecommons.org/licenses/by-sa/3.0/
****************************************************************************
|
* **Supported versions:**
`Latest <https://docs.pgrouting.org/latest/en/pgr_maxCardinalityMatch.html>`__
(`3.4 <https://docs.pgrouting.org/3.4/en/pgr_maxCardinalityMatch.html>`__)
`3.3 <https://docs.pgrouting.org/3.3/en/pgr_maxCardinalityMatch.html>`__
`3.2 <https://docs.pgrouting.org/3.2/en/pgr_maxCardinalityMatch.html>`__
`3.1 <https://docs.pgrouting.org/3.1/en/pgr_maxCardinalityMatch.html>`__
`3.0 <https://docs.pgrouting.org/3.0/en/pgr_maxCardinalityMatch.html>`__
* **Unsupported versions:**
`2.6 <https://docs.pgrouting.org/2.6/en/pgr_maxCardinalityMatch.html>`__
`2.5 <https://docs.pgrouting.org/2.5/en/pgr_maxCardinalityMatch.html>`__
`2.4 <https://docs.pgrouting.org/2.4/en/pgr_maximumCardinalityMatching.html>`__
`2.3 <https://docs.pgrouting.org/2.3/en/src/max_flow/doc/pgr_maximumCardinalityMatching.html>`__
pgr_maxCardinalityMatch
===============================================================================
``pgr_maxCardinalityMatch`` — Calculates a maximum cardinality matching in a
graph.
.. figure:: images/boost-inside.jpeg
:target: https://www.boost.org/libs/graph/doc/maximum_matching.html
Boost Graph Inside
.. Rubric:: 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: :math:`O( E*V * \alpha(E,V))`
* :math:`\alpha(E,V)` is the inverse of the `Ackermann function`_.
.. _Ackermann function: https://en.wikipedia.org/wiki/Ackermann_function
Signatures
-------------------------------------------------------------------------------
.. index::
single: MaximumCardinalityMatch
.. admonition:: \ \
:class: signatures
| pgr_maxCardinalityMatch(`Edges SQL`_)
| RETURNS SET OF |result-edge|
| OR EMPTY SET
:Example: Using all edges.
.. literalinclude:: doc-pgr_maxCardinalityMatch.queries
:start-after: -- q2
:end-before: -- q3
Parameters
-------------------------------------------------------------------------------
.. include:: pgRouting-concepts.rst
:start-after: only_edge_param_start
:end-before: only_edge_param_end
Inner Queries
-------------------------------------------------------------------------------
Edges SQL
...............................................................................
SQL query, which should return a set of rows with the following columns:
.. list-table::
:width: 81
:widths: 14 14 7 44
:header-rows: 1
* - 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
-------------------------------------------------------------------------------
* :doc:`flow-family`
* :doc:`migration`
* 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
.. rubric:: Indices and tables
* :ref:`genindex`
* :ref:`search`
|
