boost/graph/max_cardinality_matching.hpp
//======================================================================= // Copyright (c) 2005 Aaron Windsor // // Distributed under 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) // //======================================================================= #ifndef BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP #define BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP #include <vector> #include <list> #include <deque> #include <algorithm> // for std::sort and std::stable_sort #include <utility> // for std::pair #include <boost/property_map/property_map.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/pending/disjoint_sets.hpp> #include <boost/assert.hpp> namespace boost { namespace graph { namespace detail { enum VERTEX_STATE { V_EVEN, V_ODD, V_UNREACHED }; } } // end namespace graph::detail template < typename Graph, typename MateMap, typename VertexIndexMap > typename graph_traits< Graph >::vertices_size_type matching_size( const Graph& g, MateMap mate, VertexIndexMap vm) { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertices_size_type v_size_t; v_size_t size_of_matching = 0; vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { vertex_descriptor_t v = *vi; if (get(mate, v) != graph_traits< Graph >::null_vertex() && get(vm, v) < get(vm, get(mate, v))) ++size_of_matching; } return size_of_matching; } template < typename Graph, typename MateMap > inline typename graph_traits< Graph >::vertices_size_type matching_size( const Graph& g, MateMap mate) { return matching_size(g, mate, get(vertex_index, g)); } template < typename Graph, typename MateMap, typename VertexIndexMap > bool is_a_matching(const Graph& g, MateMap mate, VertexIndexMap) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { vertex_descriptor_t v = *vi; if (get(mate, v) != graph_traits< Graph >::null_vertex() && v != get(mate, get(mate, v))) return false; } return true; } template < typename Graph, typename MateMap > inline bool is_a_matching(const Graph& g, MateMap mate) { return is_a_matching(g, mate, get(vertex_index, g)); } //*************************************************************************** //*************************************************************************** // Maximum Cardinality Matching Functors //*************************************************************************** //*************************************************************************** template < typename Graph, typename MateMap, typename VertexIndexMap = dummy_property_map > struct no_augmenting_path_finder { no_augmenting_path_finder(const Graph&, MateMap, VertexIndexMap) {} inline bool augment_matching() { return false; } template < typename PropertyMap > void get_current_matching(PropertyMap) {} }; template < typename Graph, typename MateMap, typename VertexIndexMap > class edmonds_augmenting_path_finder { // This implementation of Edmonds' matching algorithm closely // follows Tarjan's description of the algorithm in "Data // Structures and Network Algorithms." public: // generates the type of an iterator property map from vertices to type X template < typename X > struct map_vertex_to_ { typedef boost::iterator_property_map< typename std::vector< X >::iterator, VertexIndexMap > type; }; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename std::pair< vertex_descriptor_t, vertex_descriptor_t > vertex_pair_t; typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t; typedef typename graph_traits< Graph >::vertices_size_type v_size_t; typedef typename graph_traits< Graph >::edges_size_type e_size_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::out_edge_iterator out_edge_iterator_t; typedef typename std::deque< vertex_descriptor_t > vertex_list_t; typedef typename std::vector< edge_descriptor_t > edge_list_t; typedef typename map_vertex_to_< vertex_descriptor_t >::type vertex_to_vertex_map_t; typedef typename map_vertex_to_< int >::type vertex_to_int_map_t; typedef typename map_vertex_to_< vertex_pair_t >::type vertex_to_vertex_pair_map_t; typedef typename map_vertex_to_< v_size_t >::type vertex_to_vsize_map_t; typedef typename map_vertex_to_< e_size_t >::type vertex_to_esize_map_t; edmonds_augmenting_path_finder( const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm) : g(arg_g) , vm(arg_vm) , n_vertices(num_vertices(arg_g)) , mate_vector(n_vertices) , ancestor_of_v_vector(n_vertices) , ancestor_of_w_vector(n_vertices) , vertex_state_vector(n_vertices) , origin_vector(n_vertices) , pred_vector(n_vertices) , bridge_vector(n_vertices) , ds_parent_vector(n_vertices) , ds_rank_vector(n_vertices) , mate(mate_vector.begin(), vm) , ancestor_of_v(ancestor_of_v_vector.begin(), vm) , ancestor_of_w(ancestor_of_w_vector.begin(), vm) , vertex_state(vertex_state_vector.begin(), vm) , origin(origin_vector.begin(), vm) , pred(pred_vector.begin(), vm) , bridge(bridge_vector.begin(), vm) , ds_parent_map(ds_parent_vector.begin(), vm) , ds_rank_map(ds_rank_vector.begin(), vm) , ds(ds_rank_map, ds_parent_map) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) mate[*vi] = get(arg_mate, *vi); } bool augment_matching() { // As an optimization, some of these values can be saved from one // iteration to the next instead of being re-initialized each // iteration, allowing for "lazy blossom expansion." This is not // currently implemented. e_size_t timestamp = 0; even_edges.clear(); vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { vertex_descriptor_t u = *vi; origin[u] = u; pred[u] = u; ancestor_of_v[u] = 0; ancestor_of_w[u] = 0; ds.make_set(u); if (mate[u] == graph_traits< Graph >::null_vertex()) { vertex_state[u] = graph::detail::V_EVEN; out_edge_iterator_t ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { if (target(*ei, g) != u) { even_edges.push_back(*ei); } } } else vertex_state[u] = graph::detail::V_UNREACHED; } // end initializations vertex_descriptor_t v, w, w_free_ancestor, v_free_ancestor; w_free_ancestor = graph_traits< Graph >::null_vertex(); v_free_ancestor = graph_traits< Graph >::null_vertex(); bool found_alternating_path = false; while (!even_edges.empty() && !found_alternating_path) { // since we push even edges onto the back of the list as // they're discovered, taking them off the back will search // for augmenting paths depth-first. edge_descriptor_t current_edge = even_edges.back(); even_edges.pop_back(); v = source(current_edge, g); w = target(current_edge, g); vertex_descriptor_t v_prime = origin[ds.find_set(v)]; vertex_descriptor_t w_prime = origin[ds.find_set(w)]; // because of the way we put all of the edges on the queue, // v_prime should be labeled V_EVEN; the following is a // little paranoid but it could happen... if (vertex_state[v_prime] != graph::detail::V_EVEN) { std::swap(v_prime, w_prime); std::swap(v, w); } if (vertex_state[w_prime] == graph::detail::V_UNREACHED) { vertex_state[w_prime] = graph::detail::V_ODD; vertex_descriptor_t w_prime_mate = mate[w_prime]; vertex_state[w_prime_mate] = graph::detail::V_EVEN; out_edge_iterator_t ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(w_prime_mate, g); ei != ei_end; ++ei) { if (target(*ei, g) != w_prime_mate) { even_edges.push_back(*ei); } } pred[w_prime] = v; } // w_prime == v_prime can happen below if we get an edge that has // been shrunk into a blossom else if (vertex_state[w_prime] == graph::detail::V_EVEN && w_prime != v_prime) { vertex_descriptor_t w_up = w_prime; vertex_descriptor_t v_up = v_prime; vertex_descriptor_t nearest_common_ancestor = graph_traits< Graph >::null_vertex(); w_free_ancestor = graph_traits< Graph >::null_vertex(); v_free_ancestor = graph_traits< Graph >::null_vertex(); // We now need to distinguish between the case that // w_prime and v_prime share an ancestor under the // "parent" relation, in which case we've found a // blossom and should shrink it, or the case that // w_prime and v_prime both have distinct ancestors that // are free, in which case we've found an alternating // path between those two ancestors. ++timestamp; while (nearest_common_ancestor == graph_traits< Graph >::null_vertex() && (v_free_ancestor == graph_traits< Graph >::null_vertex() || w_free_ancestor == graph_traits< Graph >::null_vertex())) { ancestor_of_w[w_up] = timestamp; ancestor_of_v[v_up] = timestamp; if (w_free_ancestor == graph_traits< Graph >::null_vertex()) w_up = parent(w_up); if (v_free_ancestor == graph_traits< Graph >::null_vertex()) v_up = parent(v_up); if (mate[v_up] == graph_traits< Graph >::null_vertex()) v_free_ancestor = v_up; if (mate[w_up] == graph_traits< Graph >::null_vertex()) w_free_ancestor = w_up; if (ancestor_of_w[v_up] == timestamp) nearest_common_ancestor = v_up; else if (ancestor_of_v[w_up] == timestamp) nearest_common_ancestor = w_up; else if (v_free_ancestor == w_free_ancestor && v_free_ancestor != graph_traits< Graph >::null_vertex()) nearest_common_ancestor = v_up; } if (nearest_common_ancestor == graph_traits< Graph >::null_vertex()) found_alternating_path = true; // to break out of the loop else { // shrink the blossom link_and_set_bridges( w_prime, nearest_common_ancestor, std::make_pair(w, v)); link_and_set_bridges( v_prime, nearest_common_ancestor, std::make_pair(v, w)); } } } if (!found_alternating_path) return false; // retrieve the augmenting path and put it in aug_path reversed_retrieve_augmenting_path(v, v_free_ancestor); retrieve_augmenting_path(w, w_free_ancestor); // augment the matching along aug_path vertex_descriptor_t a, b; while (!aug_path.empty()) { a = aug_path.front(); aug_path.pop_front(); b = aug_path.front(); aug_path.pop_front(); mate[a] = b; mate[b] = a; } return true; } template < typename PropertyMap > void get_current_matching(PropertyMap pm) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(pm, *vi, mate[*vi]); } template < typename PropertyMap > void get_vertex_state_map(PropertyMap pm) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(pm, *vi, vertex_state[origin[ds.find_set(*vi)]]); } private: vertex_descriptor_t parent(vertex_descriptor_t x) { if (vertex_state[x] == graph::detail::V_EVEN && mate[x] != graph_traits< Graph >::null_vertex()) return mate[x]; else if (vertex_state[x] == graph::detail::V_ODD) return origin[ds.find_set(pred[x])]; else return x; } void link_and_set_bridges(vertex_descriptor_t x, vertex_descriptor_t stop_vertex, vertex_pair_t the_bridge) { for (vertex_descriptor_t v = x; v != stop_vertex; v = parent(v)) { ds.union_set(v, stop_vertex); origin[ds.find_set(stop_vertex)] = stop_vertex; if (vertex_state[v] == graph::detail::V_ODD) { bridge[v] = the_bridge; out_edge_iterator_t oei, oei_end; for (boost::tie(oei, oei_end) = out_edges(v, g); oei != oei_end; ++oei) { if (target(*oei, g) != v) { even_edges.push_back(*oei); } } } } } // Since none of the STL containers support both constant-time // concatenation and reversal, the process of expanding an // augmenting path once we know one exists is a little more // complicated than it has to be. If we know the path is from v to // w, then the augmenting path is recursively defined as: // // path(v,w) = [v], if v = w // = concat([v, mate[v]], path(pred[mate[v]], w), // if v != w and vertex_state[v] == graph::detail::V_EVEN // = concat([v], reverse(path(x,mate[v])), path(y,w)), // if v != w, vertex_state[v] == graph::detail::V_ODD, and // bridge[v] = (x,y) // // These next two mutually recursive functions implement this definition. void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w) { if (v == w) aug_path.push_back(v); else if (vertex_state[v] == graph::detail::V_EVEN) { aug_path.push_back(v); aug_path.push_back(mate[v]); retrieve_augmenting_path(pred[mate[v]], w); } else // vertex_state[v] == graph::detail::V_ODD { aug_path.push_back(v); reversed_retrieve_augmenting_path(bridge[v].first, mate[v]); retrieve_augmenting_path(bridge[v].second, w); } } void reversed_retrieve_augmenting_path( vertex_descriptor_t v, vertex_descriptor_t w) { if (v == w) aug_path.push_back(v); else if (vertex_state[v] == graph::detail::V_EVEN) { reversed_retrieve_augmenting_path(pred[mate[v]], w); aug_path.push_back(mate[v]); aug_path.push_back(v); } else // vertex_state[v] == graph::detail::V_ODD { reversed_retrieve_augmenting_path(bridge[v].second, w); retrieve_augmenting_path(bridge[v].first, mate[v]); aug_path.push_back(v); } } // private data members const Graph& g; VertexIndexMap vm; v_size_t n_vertices; // storage for the property maps below std::vector< vertex_descriptor_t > mate_vector; std::vector< e_size_t > ancestor_of_v_vector; std::vector< e_size_t > ancestor_of_w_vector; std::vector< int > vertex_state_vector; std::vector< vertex_descriptor_t > origin_vector; std::vector< vertex_descriptor_t > pred_vector; std::vector< vertex_pair_t > bridge_vector; std::vector< vertex_descriptor_t > ds_parent_vector; std::vector< v_size_t > ds_rank_vector; // iterator property maps vertex_to_vertex_map_t mate; vertex_to_esize_map_t ancestor_of_v; vertex_to_esize_map_t ancestor_of_w; vertex_to_int_map_t vertex_state; vertex_to_vertex_map_t origin; vertex_to_vertex_map_t pred; vertex_to_vertex_pair_map_t bridge; vertex_to_vertex_map_t ds_parent_map; vertex_to_vsize_map_t ds_rank_map; vertex_list_t aug_path; edge_list_t even_edges; disjoint_sets< vertex_to_vsize_map_t, vertex_to_vertex_map_t > ds; }; //*************************************************************************** //*************************************************************************** // Initial Matching Functors //*************************************************************************** //*************************************************************************** template < typename Graph, typename MateMap > struct greedy_matching { typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t; typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t; static void find_matching(const Graph& g, MateMap mate) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(mate, *vi, graph_traits< Graph >::null_vertex()); edge_iterator_t ei, ei_end; for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { edge_descriptor_t e = *ei; vertex_descriptor_t u = source(e, g); vertex_descriptor_t v = target(e, g); if (u != v && get(mate, u) == get(mate, v)) // only way equality can hold is if // mate[u] == mate[v] == null_vertex { put(mate, u, v); put(mate, v, u); } } } }; template < typename Graph, typename MateMap > struct extra_greedy_matching { // The "extra greedy matching" is formed by repeating the // following procedure as many times as possible: Choose the // unmatched vertex v of minimum non-zero degree. Choose the // neighbor w of v which is unmatched and has minimum degree over // all of v's neighbors. Add (u,v) to the matching. Ties for // either choice are broken arbitrarily. This procedure takes time // O(m log n), where m is the number of edges in the graph and n // is the number of vertices. typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t; typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t; typedef std::pair< vertex_descriptor_t, vertex_descriptor_t > vertex_pair_t; struct select_first { inline static vertex_descriptor_t select_vertex(const vertex_pair_t p) { return p.first; } }; struct select_second { inline static vertex_descriptor_t select_vertex(const vertex_pair_t p) { return p.second; } }; template < class PairSelector > class less_than_by_degree { public: less_than_by_degree(const Graph& g) : m_g(g) {} bool operator()(const vertex_pair_t x, const vertex_pair_t y) { return out_degree(PairSelector::select_vertex(x), m_g) < out_degree(PairSelector::select_vertex(y), m_g); } private: const Graph& m_g; }; static void find_matching(const Graph& g, MateMap mate) { typedef std::vector< std::pair< vertex_descriptor_t, vertex_descriptor_t > > directed_edges_vector_t; directed_edges_vector_t edge_list; vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(mate, *vi, graph_traits< Graph >::null_vertex()); edge_iterator_t ei, ei_end; for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { edge_descriptor_t e = *ei; vertex_descriptor_t u = source(e, g); vertex_descriptor_t v = target(e, g); if (u == v) continue; edge_list.push_back(std::make_pair(u, v)); edge_list.push_back(std::make_pair(v, u)); } // sort the edges by the degree of the target, then (using a // stable sort) by degree of the source std::sort(edge_list.begin(), edge_list.end(), less_than_by_degree< select_second >(g)); std::stable_sort(edge_list.begin(), edge_list.end(), less_than_by_degree< select_first >(g)); // construct the extra greedy matching for (typename directed_edges_vector_t::const_iterator itr = edge_list.begin(); itr != edge_list.end(); ++itr) { if (get(mate, itr->first) == get(mate, itr->second)) // only way equality can hold is if mate[itr->first] == // mate[itr->second] == null_vertex { put(mate, itr->first, itr->second); put(mate, itr->second, itr->first); } } } }; template < typename Graph, typename MateMap > struct empty_matching { typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; static void find_matching(const Graph& g, MateMap mate) { vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) put(mate, *vi, graph_traits< Graph >::null_vertex()); } }; //*************************************************************************** //*************************************************************************** // Matching Verifiers //*************************************************************************** //*************************************************************************** namespace detail { template < typename SizeType > class odd_components_counter : public dfs_visitor<> // This depth-first search visitor will count the number of connected // components with an odd number of vertices. It's used by // maximum_matching_verifier. { public: odd_components_counter(SizeType& c_count) : m_count(c_count) { m_count = 0; } template < class Vertex, class Graph > void start_vertex(Vertex, Graph&) { m_parity = false; } template < class Vertex, class Graph > void discover_vertex(Vertex, Graph&) { m_parity = !m_parity; m_parity ? ++m_count : --m_count; } protected: SizeType& m_count; private: bool m_parity; }; } // namespace detail template < typename Graph, typename MateMap, typename VertexIndexMap = dummy_property_map > struct no_matching_verifier { inline static bool verify_matching(const Graph&, MateMap, VertexIndexMap) { return true; } }; template < typename Graph, typename MateMap, typename VertexIndexMap > struct maximum_cardinality_matching_verifier { template < typename X > struct map_vertex_to_ { typedef boost::iterator_property_map< typename std::vector< X >::iterator, VertexIndexMap > type; }; typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; typedef typename graph_traits< Graph >::vertices_size_type v_size_t; typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; typedef typename map_vertex_to_< int >::type vertex_to_int_map_t; typedef typename map_vertex_to_< vertex_descriptor_t >::type vertex_to_vertex_map_t; template < typename VertexStateMap > struct non_odd_vertex { // this predicate is used to create a filtered graph that // excludes vertices labeled "graph::detail::V_ODD" non_odd_vertex() : vertex_state(0) {} non_odd_vertex(VertexStateMap* arg_vertex_state) : vertex_state(arg_vertex_state) { } template < typename Vertex > bool operator()(const Vertex& v) const { BOOST_ASSERT(vertex_state); return get(*vertex_state, v) != graph::detail::V_ODD; } VertexStateMap* vertex_state; }; static bool verify_matching(const Graph& g, MateMap mate, VertexIndexMap vm) { // For any graph G, let o(G) be the number of connected // components in G of odd size. For a subset S of G's vertex set // V(G), let (G - S) represent the subgraph of G induced by // removing all vertices in S from G. Let M(G) be the size of the // maximum cardinality matching in G. Then the Tutte-Berge // formula guarantees that // // 2 * M(G) = min ( |V(G)| + |U| + o(G - U) ) // // where the minimum is taken over all subsets U of // V(G). Edmonds' algorithm finds a set U that achieves the // minimum in the above formula, namely the vertices labeled //"ODD." This function runs one iteration of Edmonds' algorithm // to find U, then verifies that the size of the matching given // by mate satisfies the Tutte-Berge formula. // first, make sure it's a valid matching if (!is_a_matching(g, mate, vm)) return false; // We'll try to augment the matching once. This serves two // purposes: first, if we find some augmenting path, the matching // is obviously non-maximum. Second, running edmonds' algorithm // on a graph with no augmenting path will create the // Edmonds-Gallai decomposition that we need as a certificate of // maximality - we can get it by looking at the vertex_state map // that results. edmonds_augmenting_path_finder< Graph, MateMap, VertexIndexMap > augmentor(g, mate, vm); if (augmentor.augment_matching()) return false; std::vector< int > vertex_state_vector(num_vertices(g)); vertex_to_int_map_t vertex_state(vertex_state_vector.begin(), vm); augmentor.get_vertex_state_map(vertex_state); // count the number of graph::detail::V_ODD vertices v_size_t num_odd_vertices = 0; vertex_iterator_t vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) if (vertex_state[*vi] == graph::detail::V_ODD) ++num_odd_vertices; // count the number of connected components with odd cardinality // in the graph without graph::detail::V_ODD vertices non_odd_vertex< vertex_to_int_map_t > filter(&vertex_state); filtered_graph< Graph, keep_all, non_odd_vertex< vertex_to_int_map_t > > fg(g, keep_all(), filter); v_size_t num_odd_components; detail::odd_components_counter< v_size_t > occ(num_odd_components); depth_first_search(fg, visitor(occ).vertex_index_map(vm)); if (2 * matching_size(g, mate, vm) == num_vertices(g) + num_odd_vertices - num_odd_components) return true; else return false; } }; 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) { InitialMatchingFinder< Graph, MateMap >::find_matching(g, mate); AugmentingPathFinder< Graph, MateMap, VertexIndexMap > augmentor( g, mate, vm); bool not_maximum_yet = true; while (not_maximum_yet) { not_maximum_yet = augmentor.augment_matching(); } augmentor.get_current_matching(mate); return MatchingVerifier< Graph, MateMap, VertexIndexMap >::verify_matching( g, mate, vm); } template < typename Graph, typename MateMap, typename VertexIndexMap > inline bool checked_edmonds_maximum_cardinality_matching( const Graph& g, MateMap mate, VertexIndexMap vm) { return matching< Graph, MateMap, VertexIndexMap, edmonds_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier >(g, mate, vm); } template < typename Graph, typename MateMap > inline bool checked_edmonds_maximum_cardinality_matching( const Graph& g, MateMap mate) { return checked_edmonds_maximum_cardinality_matching( g, mate, get(vertex_index, g)); } template < typename Graph, typename MateMap, typename VertexIndexMap > inline void edmonds_maximum_cardinality_matching( const Graph& g, MateMap mate, VertexIndexMap vm) { matching< Graph, MateMap, VertexIndexMap, edmonds_augmenting_path_finder, extra_greedy_matching, no_matching_verifier >(g, mate, vm); } template < typename Graph, typename MateMap > inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate) { edmonds_maximum_cardinality_matching(g, mate, get(vertex_index, g)); } } // namespace boost #endif // BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP