ceph/src/boost/libs/graph/doc/maximum_matching.html

   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 &lt;typename Graph, typename MateMap&gt;
  18 void edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate);
  19
  20 template &lt;typename Graph, typename MateMap, typename VertexIndexMap&gt;
  21 void edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate, VertexIndexMap vm);
  22
  23 template &lt;typename Graph, typename MateMap&gt;
  24 bool checked_edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate);
  25
  26 template &lt;typename Graph, typename MateMap, typename VertexIndexMap&gt;
  27 bool checked_edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate, VertexIndexMap vm);
  28 </pre>
  29 <p>
  30 <a name="sec:matching">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="fig:maximal_matching"><img src="figs/maximal-match.png"></a></td>
  42 <td width="150"></td>
  43 <td><a name="fig:maximum_matching"><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/doc/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&lt;Graph&gt;::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> &le; 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 &lt;typename Graph,
 187           typename MateMap,
 188           typename VertexIndexMap,
 189           template &lt;typename, typename, typename&gt; class AugmentingPathFinder,
 190           template &lt;typename, typename&gt; class InitialMatchingFinder,
 191           template &lt;typename, typename, typename&gt; class MatchingVerifier&gt;
 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&amp; 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/doc/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/doc/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>