| //======================================================================= |
| // 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/utility.hpp> // for boost::tie |
| #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) |
| 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_state[mate[w_prime]] = graph::detail::V_EVEN; |
| out_edge_iterator_t ei, ei_end; |
| for( boost::tie(ei,ei_end) = out_edges(mate[w_prime], g); ei != ei_end; ++ei) |
| 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) |
| 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 (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); |
| 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 |