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 { 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