[ceph.git] / ceph / src / boost / libs / graph / doc / maximum_matching.html

<html><head><!--
     Copyright 2005 Aaron Windsor
    
     Use, modification and distribution is subject to the Boost Software
     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
    
      Author: Aaron Windsor
  --><title>Boost Graph Library: Maximum Cardinality Matching</title></head>
<body alink="#ff0000" bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b">
<img src="../../../boost.png" alt="C++ Boost" height="86" width="277">
<br clear="">
<h1>
<a name="sec:maximum_cardinality_matching">Maximum Cardinality Matching</a>
</h1>
<pre>
template &lt;typename Graph, typename MateMap&gt;
void edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate);

template &lt;typename Graph, typename MateMap, typename VertexIndexMap&gt;
void edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate, VertexIndexMap vm);

template &lt;typename Graph, typename MateMap&gt;
bool checked_edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate);

template &lt;typename Graph, typename MateMap, typename VertexIndexMap&gt;
bool checked_edmonds_maximum_cardinality_matching(const Graph&amp; g, MateMap mate, VertexIndexMap vm);
</pre>
<p>
<a name="sec:matching">A <i>matching</i> is a subset of the edges
of a graph such that no two edges share a common vertex.
Two different matchings in the same graph are illustrated below (edges in the
matching are colored blue.) The matching on the left is a <i>maximal matching</i>, 
meaning that its size can't be increased by adding edges. The matching on the 
right is a <i>maximum cardinality matching</i>, meaning that is has maximum size 
over all matchings in the graph.

</a></p><p></p><center>
<table border="0">
<tr>
<td><a name="fig:maximal_matching"><img src="figs/maximal-match.png"></a></td>
<td width="150"></td>
<td><a name="fig:maximum_matching"><img src="figs/maximum-match.png"></a></td>
</tr>
</table>
</center>

<p>
Both <tt>edmonds_maximum_cardinality_matching</tt> and 
<tt>checked_edmonds_maximum_cardinality_matching</tt> find the
maximum cardinality matching in any undirected graph. The matching is returned in a
<tt>MateMap</tt>, which is a 
<a href="../../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a> 
that maps vertices to vertices. In the mapping returned, each vertex is either mapped
to the vertex it's matched to, or to <tt>graph_traits&lt;Graph&gt;::null_vertex()</tt> if it
doesn't participate in the matching. If no <tt>VertexIndexMap</tt> is provided, both functions
assume that the <tt>VertexIndexMap</tt> is provided as an internal graph property accessible
by calling <tt>get(vertex_index,g)</tt>. The only difference between 
<tt>edmonds_maximum_cardinality_matching</tt> and 
<tt>checked_edmonds_maximum_cardinality_matching</tt> is that as a final step, 
the latter algorithm runs a simple verification on the matching computed and 
returns <tt>true</tt> if and only if the matching is indeed
a maximum cardinality matching.

<p>
Given a matching M, any vertex that isn't covered by an edge in M is called <i>free</i>. Any
simple path containing exactly <i>2n + 1</i> edges that starts and ends at free vertices and contains 
<i>n</i> edges from M is called an <i>alternating path</i>. Given an alternating path <i>p</i>, all matching and 
non-matching edges on <i>p</i> can be swapped, resulting in a new matching that's larger than the
original matching by exactly one edge. This method of incrementally increasing the size of matching, along 
with the following fact, forms the basis of Edmonds' matching algorithm:

<blockquote>
<i>An alternating path through the matching M exists if and only if M is not a maximum cardinality matching.</i>
</blockquote>

The difficult part is, of course, finding an augmenting path whenever one exists.
The algorithm we use for finding a maximum cardinality matching consists of three basic steps:
<ol>
<li>Create an initial matching.
<li>Repeatedly find an augmenting path and use it to increase the size of the matching until no augmenting path exists.
<li>Verify that the matching found is a maximum cardinality matching.
</ol>

If you use <tt>checked_edmonds_maximum_cardinality_matching</tt> or 
<tt>edmonds_maximum_cardinality_matching</tt>, all three of these
steps are chosen for you, but it's easy to plug in different algorithms for these three steps
using a generic matching function discussed below - in fact, both <tt>checked_edmonds_maximum_cardinality_matching</tt> 
and <tt>edmonds_maximum_cardinality_matching</tt> are just inlined specializations of this function. 

<p>
When quoting time bounds for algorithms, we assume that <tt>VertexIndexMap</tt> is a property map 
that allows for constant-time mapping between vertices and indices (which is easily achieved if, 
for instance, the vertices are stored in contiguous memory.) We use <i>n</i> and <i>m</i> to represent the size 
of the vertex and edge sets, respectively, of the input graph.

<h4>Algorithms for Creating an Initial Matching</h4>

<ul>
<li><b><tt>empty_matching</tt></b>: Takes time <i>O(n)</i> to initialize the empty matching.
<li><b><tt>greedy_matching</tt></b>: The matching obtained by iterating through the edges and adding an edge
if it doesn't conflict with the edges already in the matching. This matching is maximal, and is therefore
guaranteed to contain at least half of the edges that a maximum matching has. Takes time <i>O(m log n)</i>.
<li><b><tt>extra_greedy_matching</tt></b>: Sorts the edges in increasing order of the degree of the vertices
contained in each edge, then constructs a greedy matching from those edges. Also a maximal matching, and can
sometimes be much closer to the maximum cardinality matching than a simple <tt>greedy_matching</tt>. 
Takes time <i>O(m log n)</i>, but the constants involved make this a slower algorithm than 
<tt>greedy_matching</tt>.
</ul>

<h4>Algorithms for Finding an Augmenting Path</h4>

<ul>
<li><b><tt>edmonds_augmenting_path_finder</tt></b>: Finds an augmenting path in time <i>O(m alpha(m,n))</i>, 
where <i>alpha(m,n)</i> is an inverse of the Ackerman function. <i>alpha(m,n)</i> is one of the slowest 
growing functions that occurs naturally in computer science; essentially, <i>alpha(m,n)</i> &le; 4 for any 
graph that we'd ever hope to run this algorithm on. Since we arrive at a maximum cardinality matching after 
augmenting <i>O(n)</i> matchings, the entire algorithm takes time <i>O(mn alpha(m,n))</i>. Edmonds' original
algorithm appeared in [<a href="bibliography.html#edmonds65">64</a>], but our implementation of 
Edmonds' algorithm closely follows Tarjan's 
description of the algorithm from [<a href="bibliography.html#tarjan83:_data_struct_network_algo">27</a>].
<li><b><tt>no_augmenting_path_finder</tt></b>: Can be used if no augmentation of the initial matching is desired.
</ul>

<h4>Verification Algorithms</h4>

<ul>
<li><b><tt>maximum_cardinality_matching_verifier</tt></b>: Returns true if and only if the matching found is a 
maximum cardinality matching. Takes time <i>O(m alpha(m,n))</i>, which is on the order of a single iteration 
of Edmonds' algorithm.
<li><b><tt>no_matching_verifier</tt></b>: Always returns true
</ul>

Why is a verification algorithm needed? Edmonds' algorithm is fairly complex, and it's nearly 
impossible for a human without a few days of spare time to figure out if the matching produced by 
<tt>edmonds_matching</tt> on a graph with, say, 100 vertices and 500 edges is indeed a maximum cardinality 
matching. A verification algorithm can do this mechanically, and it's much easier to verify by inspection 
that the verification algorithm has been implemented correctly than it is to verify by inspection that 
Edmonds' algorithm has been implemented correctly. 
The Boost Graph library makes it incredibly simple to perform the subroutines needed by the verifier 
(such as finding all the connected components of odd cardinality in a graph, or creating the induced graph 
on all vertices with a certain label) in just a few lines of code.

<p>
Understanding how the verifier works requires a few graph-theoretic facts. 
Let <i>m(G)</i> be the size of a maximum cardinality matching in the graph <i>G</i>.
Denote by <i>o(G)</i> the number of connected components in <i>G</i> of odd cardinality, and for a set of 
vertices <i>X</i>, denote by <i>G - X</i> the induced graph on the vertex set <i>V(G) - X</i>. Then the 
Tutte-Berge Formula says that
<blockquote>
<i>2 * m(G) = min ( |V(G)| + |X| - o(G-X) )</i>
</blockquote>
Where the minimum is taken over all subsets <i>X</i> of the vertex set <i>V(G)</i>. A side effect of the 
Edmonds Blossom-Shrinking algorithm is that it computes what is known as the Edmonds-Gallai decomposition 
of a graph: it decomposes the graph into three disjoint sets of vertices, one of which achieves the minimum 
in the Tutte-Berge Formula.

An outline of our verification procedure is:

Given a <tt>Graph g</tt> and <tt>MateMap mate</tt>,
<ol>
<li>Check to make sure that <tt>mate</tt> is a valid matching on <tt>g</tt>.
<li>Run <tt>edmonds_augmenting_path_finder</tt> once on <tt>g</tt> and <tt>mate</tt>. If it finds an augmenting
path, the matching isn't a maximum cardinality matching. Otherwise, we retrieve a copy of the <tt>vertex_state</tt>
map used by the <tt>edmonds_augmenting_path_finder</tt>. The Edmonds-Gallai decomposition tells us that the set
of vertices labeled <tt>V_ODD</tt> by the <tt>vertex_state</tt> map can be used as the set X to achieve the 
minimum in the Tutte-Berge Formula.
<li>Count the number of vertices labeled <tt>V_ODD</tt>, store this in <tt>num_odd_vertices</tt>.
<li>Create a <a href="filtered_graph.html"><tt>filtered_graph</tt></a>
consisting of all vertices that aren't labeled <tt>V_ODD</tt>. Count the number of odd connected components
in this graph and store the result in <tt>num_odd_connected_components</tt>.
<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.
</ol>

Assuming these steps are implemented correctly, the verifier will never return a false positive,
and will only return a false negative if <tt>edmonds_augmenting_path_finder</tt> doesn't compute the
<tt>vertex_state</tt> map correctly, in which case the <tt>edmonds_augmenting_path_finder</tt>
isn't working correctly. 


<h4>Creating Your Own Matching Algorithms</h4>

Creating a matching algorithm is as simple as plugging the algorithms described above into a generic
matching function, which has the following signature:
<pre>
template &lt;typename Graph, 
	  typename MateMap,
	  typename VertexIndexMap,
	  template &lt;typename, typename, typename&gt; class AugmentingPathFinder, 
	  template &lt;typename, typename&gt; class InitialMatchingFinder,
	  template &lt;typename, typename, typename&gt; class MatchingVerifier&gt;
  bool matching(const Graph& g, MateMap mate, VertexIndexMap vm)
</pre>
The matching functions provided for you are just inlined specializations of this function:
<tt>edmonds_maximum_cardinality_matching</tt> uses <tt>edmonds_augmenting_path_finder</tt> 
as the <tt>AugmentingPathFinder</tt>, <tt>extra_greedy_matching</tt> as the <tt>InitialMatchingFinder</tt>, 
and <tt>no_matching_verifier</tt> as the <tt>MatchingVerifier</tt>. 
<tt>checked_edmonds_maximum_cardinality_matching</tt> uses the same parameters except that
<tt>maximum_cardinality_matching_verifier</tt> is used for the <tt>MatchingVerifier</tt>.

<p>
These aren't necessarily the best choices for any situation - for example, it's been claimed in the literature
that for sparse graphs, Edmonds' algorithm converges to the maximum cardinality matching more quickly if it 
isn't supplied with an intitial matching. Such an algorithm can be easily assembled by calling <tt>matching</tt> with
<ul>
<li><tt>AugmentingPathFinder = edmonds_augmenting_path_finder</tt>
<li><tt>InitialMatchingFinder = empty_matching</tt>
</ul>
and choosing the <tt>MatchingVerifier</tt> depending on how careful you're feeling.

<p>
Suppose instead that you want a relatively large matching quickly, but are not exactly interested in a maximum matching. 
Both extra_greedy_matching and greedy_matching find maximal matchings, which means they're guaranteed to be at 
least half the size of a maximum cardinality matching, so you could call <tt>matching</tt> with
<ul>
<li><tt>AugmentingPathFinder = no_augmenting_path_finder</tt>
<li><tt>InitialMatchingFinder = extra_greedy_matching</tt>
<li><tt>MatchingVerifier = maximum_cardinality_matching_verifier</tt>
</ul>
The resulting algorithm will find an extra greedy matching in time <i>O(m log n)</i> without looking for 
augmenting paths. As a bonus, the return value of this function is true if and only if the extra greedy 
matching happens to be a maximum cardinality matching.

</p><h3>Where Defined</h3>

<p>
<a href="../../../boost/graph/max_cardinality_matching.hpp"><tt>boost/graph/max_cardinality_matching.hpp</tt></a>


</p><h3>Parameters</h3>

IN: <tt>const Graph&amp; g</tt>
<blockquote>
An undirected graph. The graph type must be a model of 
<a href="VertexAndEdgeListGraph.html">Vertex and Edge List Graph</a> and
<a href="IncidenceGraph.html">Incidence Graph</a>.<br>
</blockquote>

IN: <tt>VertexIndexMap vm</tt>
<blockquote>
Must be a model of <a href="../../property_map/doc/ReadablePropertyMap.html">ReadablePropertyMap</a>, mapping vertices to integer indices.
</blockquote>

OUT: <tt>MateMap mate</tt>
<blockquote>
Must be a model of <a href="../../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>, mapping
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
<tt>graph_traits<Graph>::null_vertex()</tt> if v isn't matched.
</blockquote>

<h3>Complexity</h3>

<p>
Let <i>m</i> and <i>n</i> be the number of edges and vertices in the input graph, respectively. Assuming the 
<tt>VertexIndexMap</tt> supplied allows constant-time lookups, the time complexity for both 
<tt>edmonds_matching</tt> and <tt>checked_edmonds_matching</tt> is <i>O(mn alpha(m,n))</i>. 
<i>alpha(m,n)</i> is a slow growing function that is at most 4 for any feasible input.
</p><p>

</p><h3>Example</h3>

<p> The file <a href="../example/matching_example.cpp"><tt>example/matching_example.cpp</tt></a>
contains an example.

<br>
</p><hr>
<table>
<tbody><tr valign="top">
Commit	Line	Data
7c673cae FG	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: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<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/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