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