...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

template <typename Graph, typename MateMap> void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate); template <typename Graph, typename MateMap, typename VertexIndexMap> void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm); template <typename Graph, typename MateMap> bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate); template <typename Graph, typename MateMap, typename VertexIndexMap> bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm);

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

Given a matching M, any vertex that isn't covered by an edge in M is called *free*. Any
simple path containing exactly *2n + 1* edges that starts and ends at free vertices and contains
*n* edges from M is called an *alternating path*. Given an alternating path *p*, all matching and
non-matching edges on *p* 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:

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:An alternating path through the matching M exists if and only if M is not a maximum cardinality matching.

- Create an initial matching.
- Repeatedly find an augmenting path and use it to increase the size of the matching until no augmenting path exists.
- Verify that the matching found is a maximum cardinality matching.

When quoting time bounds for algorithms, we assume that `VertexIndexMap` 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 *n* and *m* to represent the size
of the vertex and edge sets, respectively, of the input graph.

: Takes time`empty_matching`*O(n)*to initialize the empty matching.: 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`greedy_matching`*O(m log n)*.: 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`extra_greedy_matching``greedy_matching`. Takes time*O(m log n)*, but the constants involved make this a slower algorithm than`greedy_matching`.

: Finds an augmenting path in time`edmonds_augmenting_path_finder`*O(m alpha(m,n))*, where*alpha(m,n)*is an inverse of the Ackerman function.*alpha(m,n)*is one of the slowest growing functions that occurs naturally in computer science; essentially,*alpha(m,n)*≤ 4 for any graph that we'd ever hope to run this algorithm on. Since we arrive at a maximum cardinality matching after augmenting*O(n)*matchings, the entire algorithm takes time*O(mn alpha(m,n))*. Edmonds' original algorithm appeared in [64], but our implementation of Edmonds' algorithm closely follows Tarjan's description of the algorithm from [27].: Can be used if no augmentation of the initial matching is desired.`no_augmenting_path_finder`

: Returns true if and only if the matching found is a maximum cardinality matching. Takes time`maximum_cardinality_matching_verifier`*O(m alpha(m,n))*, which is on the order of a single iteration of Edmonds' algorithm.: Always returns true`no_matching_verifier`

Understanding how the verifier works requires a few graph-theoretic facts.
Let *m(G)* be the size of a maximum cardinality matching in the graph *G*.
Denote by *o(G)* the number of connected components in *G* of odd cardinality, and for a set of
vertices *X*, denote by *G - X* the induced graph on the vertex set *V(G) - X*. Then the
Tutte-Berge Formula says that

Where the minimum is taken over all subsets2 * m(G) = min ( |V(G)| + |X| - o(G-X) )

- Check to make sure that
`mate`is a valid matching on`g`. - Run
`edmonds_augmenting_path_finder`once on`g`and`mate`. If it finds an augmenting path, the matching isn't a maximum cardinality matching. Otherwise, we retrieve a copy of the`vertex_state`map used by the`edmonds_augmenting_path_finder`. The Edmonds-Gallai decomposition tells us that the set of vertices labeled`V_ODD`by the`vertex_state`map can be used as the set X to achieve the minimum in the Tutte-Berge Formula. - Count the number of vertices labeled
`V_ODD`, store this in`num_odd_vertices`. - Create a
`filtered_graph`consisting of all vertices that aren't labeled`V_ODD`. Count the number of odd connected components in this graph and store the result in`num_odd_connected_components`. - Test to see if equality holds in the Tutte-Berge formula using |X| =
`num_odd_vertices`and o(G-X) =`num_odd_connected_components`. Return true if it holds, false otherwise.

template <typename Graph, typename MateMap, typename VertexIndexMap, template <typename, typename, typename> class AugmentingPathFinder, template <typename, typename> class InitialMatchingFinder, template <typename, typename, typename> class MatchingVerifier> bool matching(const Graph& g, MateMap mate, VertexIndexMap vm)The matching functions provided for you are just inlined specializations of this function:

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 `matching` with

`AugmentingPathFinder = edmonds_augmenting_path_finder``InitialMatchingFinder = empty_matching`

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 `matching` with

`AugmentingPathFinder = no_augmenting_path_finder``InitialMatchingFinder = extra_greedy_matching``MatchingVerifier = maximum_cardinality_matching_verifier`

`boost/graph/max_cardinality_matching.hpp`

An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph.IN:

Must be a model of ReadablePropertyMap, mapping vertices to integer indices.OUT:

Must be a model of ReadWritePropertyMap, mapping vertices to vertices. For any vertex v in the graph,get(mate,v)will be the vertex that v is matched to, orgraph_traitsif v isn't matched.::null_vertex()

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

The file `example/matching_example.cpp`
contains an example.

Copyright © 2005 |
Aaron Windsor (aaron.windsor@gmail.com) |