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