| 1 | <html><head><!-- |
|---|
| 2 | -- Copyright 2005 Aaron Windsor |
|---|
| 3 | -- |
|---|
| 4 | -- Use, modification and distribution is subject to the Boost Software |
|---|
| 5 | -- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
|---|
| 6 | -- http://www.boost.org/LICENSE_1_0.txt) |
|---|
| 7 | -- |
|---|
| 8 | -- Author: Aaron Windsor |
|---|
| 9 | --><title>Boost Graph Library: Maximum Cardinality Matching</title></head> |
|---|
| 10 | <body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"> |
|---|
| 11 | <img src="../../../boost.png" alt="C++ Boost" height="86" width="277"> |
|---|
| 12 | <br clear=""> |
|---|
| 13 | <h1> |
|---|
| 14 | <a name="sec:maximum_cardinality_matching">Maximum Cardinality Matching</a> |
|---|
| 15 | </h1> |
|---|
| 16 | <pre> |
|---|
| 17 | template <typename Graph, typename MateMap> |
|---|
| 18 | void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate); |
|---|
| 19 | |
|---|
| 20 | template <typename Graph, typename MateMap, typename VertexIndexMap> |
|---|
| 21 | void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm); |
|---|
| 22 | |
|---|
| 23 | template <typename Graph, typename MateMap> |
|---|
| 24 | bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate); |
|---|
| 25 | |
|---|
| 26 | template <typename Graph, typename MateMap, typename VertexIndexMap> |
|---|
| 27 | bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm); |
|---|
| 28 | </pre> |
|---|
| 29 | <p> |
|---|
| 30 | <a name="sec:articulation_points">A <i>matching</i> is a subset of the edges |
|---|
| 31 | of a graph such that no two edges share a common vertex. |
|---|
| 32 | Two different matchings in the same graph are illustrated below (edges in the |
|---|
| 33 | matching are colored blue.) The matching on the left is a <i>maximal matching</i>, |
|---|
| 34 | meaning that its size can't be increased by adding edges. The matching on the |
|---|
| 35 | right is a <i>maximum cardinality matching</i>, meaning that is has maximum size |
|---|
| 36 | over all matchings in the graph. |
|---|
| 37 | |
|---|
| 38 | </a></p><p></p><center> |
|---|
| 39 | <table border="0"> |
|---|
| 40 | <tr> |
|---|
| 41 | <td><a name="sec:articulation_points"><img src="figs/maximal-match.png"></a></td> |
|---|
| 42 | <td width="150"></td> |
|---|
| 43 | <td><a name="sec:articulation_points"><img src="figs/maximum-match.png"></a></td> |
|---|
| 44 | </tr> |
|---|
| 45 | </table> |
|---|
| 46 | </center> |
|---|
| 47 | |
|---|
| 48 | <p> |
|---|
| 49 | Both <tt>edmonds_maximum_cardinality_matching</tt> and |
|---|
| 50 | <tt>checked_edmonds_maximum_cardinality_matching</tt> find the |
|---|
| 51 | maximum cardinality matching in any undirected graph. The matching is returned in a |
|---|
| 52 | <tt>MateMap</tt>, which is a |
|---|
| 53 | <a href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a> |
|---|
| 54 | that maps vertices to vertices. In the mapping returned, each vertex is either mapped |
|---|
| 55 | to the vertex it's matched to, or to <tt>graph_traits<Graph>::null_vertex()</tt> if it |
|---|
| 56 | doesn't participate in the matching. If no <tt>VertexIndexMap</tt> is provided, both functions |
|---|
| 57 | assume that the <tt>VertexIndexMap</tt> is provided as an internal graph property accessible |
|---|
| 58 | by calling <tt>get(vertex_index,g)</tt>. The only difference between |
|---|
| 59 | <tt>edmonds_maximum_cardinality_matching</tt> and |
|---|
| 60 | <tt>checked_edmonds_maximum_cardinality_matching</tt> is that as a final step, |
|---|
| 61 | the latter algorithm runs a simple verification on the matching computed and |
|---|
| 62 | returns <tt>true</tt> if and only if the matching is indeed |
|---|
| 63 | a maximum cardinality matching. |
|---|
| 64 | |
|---|
| 65 | <p> |
|---|
| 66 | Given a matching M, any vertex that isn't covered by an edge in M is called <i>free</i>. Any |
|---|
| 67 | simple path containing exactly <i>2n + 1</i> edges that starts and ends at free vertices and contains |
|---|
| 68 | <i>n</i> edges from M is called an <i>alternating path</i>. Given an alternating path <i>p</i>, all matching and |
|---|
| 69 | non-matching edges on <i>p</i> can be swapped, resulting in a new matching that's larger than the |
|---|
| 70 | original matching by exactly one edge. This method of incrementally increasing the size of matching, along |
|---|
| 71 | with the following fact, forms the basis of Edmonds' matching algorithm: |
|---|
| 72 | |
|---|
| 73 | <blockquote> |
|---|
| 74 | <i>An alternating path through the matching M exists if and only if M is not a maximum cardinality matching.</i> |
|---|
| 75 | </blockquote> |
|---|
| 76 | |
|---|
| 77 | The difficult part is, of course, finding an augmenting path whenever one exists. |
|---|
| 78 | The algorithm we use for finding a maximum cardinality matching consists of three basic steps: |
|---|
| 79 | <ol> |
|---|
| 80 | <li>Create an initial matching. |
|---|
| 81 | <li>Repeatedly find an augmenting path and use it to increase the size of the matching until no augmenting path exists. |
|---|
| 82 | <li>Verify that the matching found is a maximum cardinality matching. |
|---|
| 83 | </ol> |
|---|
| 84 | |
|---|
| 85 | If you use <tt>checked_edmonds_maximum_cardinality_matching</tt> or |
|---|
| 86 | <tt>edmonds_maximum_cardinality_matching</tt>, all three of these |
|---|
| 87 | steps are chosen for you, but it's easy to plug in different algorithms for these three steps |
|---|
| 88 | using a generic matching function discussed below - in fact, both <tt>checked_edmonds_maximum_cardinality_matching</tt> |
|---|
| 89 | and <tt>edmonds_maximum_cardinality_matching</tt> are just inlined specializations of this function. |
|---|
| 90 | |
|---|
| 91 | <p> |
|---|
| 92 | When quoting time bounds for algorithms, we assume that <tt>VertexIndexMap</tt> is a property map |
|---|
| 93 | that allows for constant-time mapping between vertices and indices (which is easily achieved if, |
|---|
| 94 | for instance, the vertices are stored in contiguous memory.) We use <i>n</i> and <i>m</i> to represent the size |
|---|
| 95 | of the vertex and edge sets, respectively, of the input graph. |
|---|
| 96 | |
|---|
| 97 | <h4>Algorithms for Creating an Initial Matching</h4> |
|---|
| 98 | |
|---|
| 99 | <ul> |
|---|
| 100 | <li><b><tt>empty_matching</tt></b>: Takes time <i>O(n)</i> to initialize the empty matching. |
|---|
| 101 | <li><b><tt>greedy_matching</tt></b>: The matching obtained by iterating through the edges and adding an edge |
|---|
| 102 | if it doesn't conflict with the edges already in the matching. This matching is maximal, and is therefore |
|---|
| 103 | guaranteed to contain at least half of the edges that a maximum matching has. Takes time <i>O(m log n)</i>. |
|---|
| 104 | <li><b><tt>extra_greedy_matching</tt></b>: Sorts the edges in increasing order of the degree of the vertices |
|---|
| 105 | contained in each edge, then constructs a greedy matching from those edges. Also a maximal matching, and can |
|---|
| 106 | sometimes be much closer to the maximum cardinality matching than a simple <tt>greedy_matching</tt>. |
|---|
| 107 | Takes time <i>O(m log n)</i>, but the constants involved make this a slower algorithm than |
|---|
| 108 | <tt>greedy_matching</tt>. |
|---|
| 109 | </ul> |
|---|
| 110 | |
|---|
| 111 | <h4>Algorithms for Finding an Augmenting Path</h4> |
|---|
| 112 | |
|---|
| 113 | <ul> |
|---|
| 114 | <li><b><tt>edmonds_augmenting_path_finder</tt></b>: Finds an augmenting path in time <i>O(m alpha(m,n))</i>, |
|---|
| 115 | where <i>alpha(m,n)</i> is an inverse of the Ackerman function. <i>alpha(m,n)</i> is one of the slowest |
|---|
| 116 | growing functions that occurs naturally in computer science; essentially, <i>alpha(m,n)</i> ≤ 4 for any |
|---|
| 117 | graph that we'd ever hope to run this algorithm on. Since we arrive at a maximum cardinality matching after |
|---|
| 118 | augmenting <i>O(n)</i> matchings, the entire algorithm takes time <i>O(mn alpha(m,n))</i>. Edmonds' original |
|---|
| 119 | algorithm appeared in [<a href="bibliography.html#edmonds65">64</a>], but our implementation of |
|---|
| 120 | Edmonds' algorithm closely follows Tarjan's |
|---|
| 121 | description of the algorithm from [<a href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>]. |
|---|
| 122 | <li><b><tt>no_augmenting_path_finder</tt></b>: Can be used if no augmentation of the initial matching is desired. |
|---|
| 123 | </ul> |
|---|
| 124 | |
|---|
| 125 | <h4>Verification Algorithms</h4> |
|---|
| 126 | |
|---|
| 127 | <ul> |
|---|
| 128 | <li><b><tt>maximum_cardinality_matching_verifier</tt></b>: Returns true if and only if the matching found is a |
|---|
| 129 | maximum cardinality matching. Takes time <i>O(m alpha(m,n))</i>, which is on the order of a single iteration |
|---|
| 130 | of Edmonds' algorithm. |
|---|
| 131 | <li><b><tt>no_matching_verifier</tt></b>: Always returns true |
|---|
| 132 | </ul> |
|---|
| 133 | |
|---|
| 134 | Why is a verification algorithm needed? Edmonds' algorithm is fairly complex, and it's nearly |
|---|
| 135 | impossible for a human without a few days of spare time to figure out if the matching produced by |
|---|
| 136 | <tt>edmonds_matching</tt> on a graph with, say, 100 vertices and 500 edges is indeed a maximum cardinality |
|---|
| 137 | matching. A verification algorithm can do this mechanically, and it's much easier to verify by inspection |
|---|
| 138 | that the verification algorithm has been implemented correctly than it is to verify by inspection that |
|---|
| 139 | Edmonds' algorithm has been implemented correctly. |
|---|
| 140 | The Boost Graph library makes it incredibly simple to perform the subroutines needed by the verifier |
|---|
| 141 | (such as finding all the connected components of odd cardinality in a graph, or creating the induced graph |
|---|
| 142 | on all vertices with a certain label) in just a few lines of code. |
|---|
| 143 | |
|---|
| 144 | <p> |
|---|
| 145 | Understanding how the verifier works requires a few graph-theoretic facts. |
|---|
| 146 | Let <i>m(G)</i> be the size of a maximum cardinality matching in the graph <i>G</i>. |
|---|
| 147 | Denote by <i>o(G)</i> the number of connected components in <i>G</i> of odd cardinality, and for a set of |
|---|
| 148 | vertices <i>X</i>, denote by <i>G - X</i> the induced graph on the vertex set <i>V(G) - X</i>. Then the |
|---|
| 149 | Tutte-Berge Formula says that |
|---|
| 150 | <blockquote> |
|---|
| 151 | <i>2 * m(G) = min ( |V(G)| + |X| - o(G-X) )</i> |
|---|
| 152 | </blockquote> |
|---|
| 153 | Where the minimum is taken over all subsets <i>X</i> of the vertex set <i>V(G)</i>. A side effect of the |
|---|
| 154 | Edmonds Blossom-Shrinking algorithm is that it computes what is known as the Edmonds-Gallai decomposition |
|---|
| 155 | of a graph: it decomposes the graph into three disjoint sets of vertices, one of which achieves the minimum |
|---|
| 156 | in the Tutte-Berge Formula. |
|---|
| 157 | |
|---|
| 158 | An outline of our verification procedure is: |
|---|
| 159 | |
|---|
| 160 | Given a <tt>Graph g</tt> and <tt>MateMap mate</tt>, |
|---|
| 161 | <ol> |
|---|
| 162 | <li>Check to make sure that <tt>mate</tt> is a valid matching on <tt>g</tt>. |
|---|
| 163 | <li>Run <tt>edmonds_augmenting_path_finder</tt> once on <tt>g</tt> and <tt>mate</tt>. If it finds an augmenting |
|---|
| 164 | path, the matching isn't a maximum cardinality matching. Otherwise, we retrieve a copy of the <tt>vertex_state</tt> |
|---|
| 165 | map used by the <tt>edmonds_augmenting_path_finder</tt>. The Edmonds-Gallai decomposition tells us that the set |
|---|
| 166 | of vertices labeled <tt>V_ODD</tt> by the <tt>vertex_state</tt> map can be used as the set X to achieve the |
|---|
| 167 | minimum in the Tutte-Berge Formula. |
|---|
| 168 | <li>Count the number of vertices labeled <tt>V_ODD</tt>, store this in <tt>num_odd_vertices</tt>. |
|---|
| 169 | <li>Create a <a href="filtered_graph.html"><tt>filtered_graph</tt></a> |
|---|
| 170 | consisting of all vertices that aren't labeled <tt>V_ODD</tt>. Count the number of odd connected components |
|---|
| 171 | in this graph and store the result in <tt>num_odd_connected_components</tt>. |
|---|
| 172 | <li>Test to see if equality holds in the Tutte-Berge formula using |X| = <tt>num_odd_vertices</tt> and o(G-X) = <tt>num_odd_connected_components</tt>. Return true if it holds, false otherwise. |
|---|
| 173 | </ol> |
|---|
| 174 | |
|---|
| 175 | Assuming these steps are implemented correctly, the verifier will never return a false positive, |
|---|
| 176 | and will only return a false negative if <tt>edmonds_augmenting_path_finder</tt> doesn't compute the |
|---|
| 177 | <tt>vertex_state</tt> map correctly, in which case the <tt>edmonds_augmenting_path_finder</tt> |
|---|
| 178 | isn't working correctly. |
|---|
| 179 | |
|---|
| 180 | |
|---|
| 181 | <h4>Creating Your Own Matching Algorithms</h4> |
|---|
| 182 | |
|---|
| 183 | Creating a matching algorithm is as simple as plugging the algorithms described above into a generic |
|---|
| 184 | matching function, which has the following signature: |
|---|
| 185 | <pre> |
|---|
| 186 | template <typename Graph, |
|---|
| 187 | typename MateMap, |
|---|
| 188 | typename VertexIndexMap, |
|---|
| 189 | template <typename, typename, typename> class AugmentingPathFinder, |
|---|
| 190 | template <typename, typename> class InitialMatchingFinder, |
|---|
| 191 | template <typename, typename, typename> class MatchingVerifier> |
|---|
| 192 | bool matching(const Graph& g, MateMap mate, VertexIndexMap vm) |
|---|
| 193 | </pre> |
|---|
| 194 | The matching functions provided for you are just inlined specializations of this function: |
|---|
| 195 | <tt>edmonds_maximum_cardinality_matching</tt> uses <tt>edmonds_augmenting_path_finder</tt> |
|---|
| 196 | as the <tt>AugmentingPathFinder</tt>, <tt>extra_greedy_matching</tt> as the <tt>InitialMatchingFinder</tt>, |
|---|
| 197 | and <tt>no_matching_verifier</tt> as the <tt>MatchingVerifier</tt>. |
|---|
| 198 | <tt>checked_edmonds_maximum_cardinality_matching</tt> uses the same parameters except that |
|---|
| 199 | <tt>maximum_cardinality_matching_verifier</tt> is used for the <tt>MatchingVerifier</tt>. |
|---|
| 200 | |
|---|
| 201 | <p> |
|---|
| 202 | These aren't necessarily the best choices for any situation - for example, it's been claimed in the literature |
|---|
| 203 | that for sparse graphs, Edmonds' algorithm converges to the maximum cardinality matching more quickly if it |
|---|
| 204 | isn't supplied with an intitial matching. Such an algorithm can be easily assembled by calling <tt>matching</tt> with |
|---|
| 205 | <ul> |
|---|
| 206 | <li><tt>AugmentingPathFinder = edmonds_augmenting_path_finder</tt> |
|---|
| 207 | <li><tt>InitialMatchingFinder = empty_matching</tt> |
|---|
| 208 | </ul> |
|---|
| 209 | and choosing the <tt>MatchingVerifier</tt> depending on how careful you're feeling. |
|---|
| 210 | |
|---|
| 211 | <p> |
|---|
| 212 | Suppose instead that you want a relatively large matching quickly, but are not exactly interested in a maximum matching. |
|---|
| 213 | Both extra_greedy_matching and greedy_matching find maximal matchings, which means they're guaranteed to be at |
|---|
| 214 | least half the size of a maximum cardinality matching, so you could call <tt>matching</tt> with |
|---|
| 215 | <ul> |
|---|
| 216 | <li><tt>AugmentingPathFinder = no_augmenting_path_finder</tt> |
|---|
| 217 | <li><tt>InitialMatchingFinder = extra_greedy_matching</tt> |
|---|
| 218 | <li><tt>MatchingVerifier = maximum_cardinality_matching_verifier</tt> |
|---|
| 219 | </ul> |
|---|
| 220 | The resulting algorithm will find an extra greedy matching in time <i>O(m log n)</i> without looking for |
|---|
| 221 | augmenting paths. As a bonus, the return value of this function is true if and only if the extra greedy |
|---|
| 222 | matching happens to be a maximum cardinality matching. |
|---|
| 223 | |
|---|
| 224 | </p><h3>Where Defined</h3> |
|---|
| 225 | |
|---|
| 226 | <p> |
|---|
| 227 | <a href="../../../boost/graph/max_cardinality_matching.hpp"><tt>boost/graph/max_cardinality_matching.hpp</tt></a> |
|---|
| 228 | |
|---|
| 229 | |
|---|
| 230 | </p><h3>Parameters</h3> |
|---|
| 231 | |
|---|
| 232 | IN: <tt>const Graph& g</tt> |
|---|
| 233 | <blockquote> |
|---|
| 234 | An undirected graph. The graph type must be a model of |
|---|
| 235 | <a href="VertexAndEdgeListGraph.html">Vertex and Edge List Graph</a> and |
|---|
| 236 | <a href="IncidenceGraph.html">Incidence Graph</a>.<br> |
|---|
| 237 | </blockquote> |
|---|
| 238 | |
|---|
| 239 | IN: <tt>VertexIndexMap vm</tt> |
|---|
| 240 | <blockquote> |
|---|
| 241 | Must be a model of <a href="../../property_map/ReadablePropertyMap.html">ReadablePropertyMap</a>, mapping vertices to integer indices. |
|---|
| 242 | </blockquote> |
|---|
| 243 | |
|---|
| 244 | OUT: <tt>MateMap mate</tt> |
|---|
| 245 | <blockquote> |
|---|
| 246 | Must be a model of <a href="../../property_map/ReadWritePropertyMap.html">ReadWritePropertyMap</a>, mapping |
|---|
| 247 | vertices to vertices. For any vertex v in the graph, <tt>get(mate,v)</tt> will be the vertex that v is matched to, or |
|---|
| 248 | <tt>graph_traits<Graph>::null_vertex()</tt> if v isn't matched. |
|---|
| 249 | </blockquote> |
|---|
| 250 | |
|---|
| 251 | <h3>Complexity</h3> |
|---|
| 252 | |
|---|
| 253 | <p> |
|---|
| 254 | Let <i>m</i> and <i>n</i> be the number of edges and vertices in the input graph, respectively. Assuming the |
|---|
| 255 | <tt>VertexIndexMap</tt> supplied allows constant-time lookups, the time complexity for both |
|---|
| 256 | <tt>edmonds_matching</tt> and <tt>checked_edmonds_matching</tt> is <i>O(mn alpha(m,n))</i>. |
|---|
| 257 | <i>alpha(m,n)</i> is a slow growing function that is at most 4 for any feasible input. |
|---|
| 258 | </p><p> |
|---|
| 259 | |
|---|
| 260 | </p><h3>Example</h3> |
|---|
| 261 | |
|---|
| 262 | <p> The file <a href="../example/matching_example.cpp"><tt>example/matching_example.cpp</tt></a> |
|---|
| 263 | contains an example. |
|---|
| 264 | |
|---|
| 265 | <br> |
|---|
| 266 | </p><hr> |
|---|
| 267 | <table> |
|---|
| 268 | <tbody><tr valign="top"> |
|---|
| 269 | <td nowrap="nowrap">Copyright © 2005</td><td> |
|---|
| 270 | Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">aaron.windsor@gmail.com</a>)<br> |
|---|
| 271 | </td></tr></tbody></table> |
|---|
| 272 | |
|---|
| 273 | </body></html> |
|---|
