1 //=======================================================================
2 // Copyright (c) 2005 Aaron Windsor
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
10 #ifndef BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
11 #define BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
16 #include <algorithm> // for std::sort and std::stable_sort
17 #include <utility> // for std::pair
18 #include <boost/property_map/property_map.hpp>
19 #include <boost/graph/graph_traits.hpp>
20 #include <boost/graph/visitors.hpp>
21 #include <boost/graph/depth_first_search.hpp>
22 #include <boost/graph/filtered_graph.hpp>
23 #include <boost/pending/disjoint_sets.hpp>
24 #include <boost/assert.hpp>
29 namespace graph { namespace detail {
30 enum { V_EVEN, V_ODD, V_UNREACHED };
31 } } // end namespace graph::detail
33 template <typename Graph, typename MateMap, typename VertexIndexMap>
34 typename graph_traits<Graph>::vertices_size_type
35 matching_size(const Graph& g, MateMap mate, VertexIndexMap vm)
37 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
38 typedef typename graph_traits<Graph>::vertex_descriptor
40 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
42 v_size_t size_of_matching = 0;
43 vertex_iterator_t vi, vi_end;
45 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
47 vertex_descriptor_t v = *vi;
48 if (get(mate,v) != graph_traits<Graph>::null_vertex()
49 && get(vm,v) < get(vm,get(mate,v)))
52 return size_of_matching;
58 template <typename Graph, typename MateMap>
59 inline typename graph_traits<Graph>::vertices_size_type
60 matching_size(const Graph& g, MateMap mate)
62 return matching_size(g, mate, get(vertex_index,g));
68 template <typename Graph, typename MateMap, typename VertexIndexMap>
69 bool is_a_matching(const Graph& g, MateMap mate, VertexIndexMap)
71 typedef typename graph_traits<Graph>::vertex_descriptor
73 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
75 vertex_iterator_t vi, vi_end;
76 for( boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
78 vertex_descriptor_t v = *vi;
79 if (get(mate,v) != graph_traits<Graph>::null_vertex()
80 && v != get(mate,get(mate,v)))
89 template <typename Graph, typename MateMap>
90 inline bool is_a_matching(const Graph& g, MateMap mate)
92 return is_a_matching(g, mate, get(vertex_index,g));
98 //***************************************************************************
99 //***************************************************************************
100 // Maximum Cardinality Matching Functors
101 //***************************************************************************
102 //***************************************************************************
104 template <typename Graph, typename MateMap,
105 typename VertexIndexMap = dummy_property_map>
106 struct no_augmenting_path_finder
108 no_augmenting_path_finder(const Graph&, MateMap, VertexIndexMap)
111 inline bool augment_matching() { return false; }
113 template <typename PropertyMap>
114 void get_current_matching(PropertyMap) {}
120 template <typename Graph, typename MateMap, typename VertexIndexMap>
121 class edmonds_augmenting_path_finder
123 // This implementation of Edmonds' matching algorithm closely
124 // follows Tarjan's description of the algorithm in "Data
125 // Structures and Network Algorithms."
129 //generates the type of an iterator property map from vertices to type X
130 template <typename X>
131 struct map_vertex_to_
133 typedef boost::iterator_property_map<typename std::vector<X>::iterator,
134 VertexIndexMap> type;
137 typedef typename graph_traits<Graph>::vertex_descriptor
139 typedef typename std::pair< vertex_descriptor_t, vertex_descriptor_t >
141 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor_t;
142 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
143 typedef typename graph_traits<Graph>::edges_size_type e_size_t;
144 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
145 typedef typename graph_traits<Graph>::out_edge_iterator
147 typedef typename std::deque<vertex_descriptor_t> vertex_list_t;
148 typedef typename std::vector<edge_descriptor_t> edge_list_t;
149 typedef typename map_vertex_to_<vertex_descriptor_t>::type
150 vertex_to_vertex_map_t;
151 typedef typename map_vertex_to_<int>::type vertex_to_int_map_t;
152 typedef typename map_vertex_to_<vertex_pair_t>::type
153 vertex_to_vertex_pair_map_t;
154 typedef typename map_vertex_to_<v_size_t>::type vertex_to_vsize_map_t;
155 typedef typename map_vertex_to_<e_size_t>::type vertex_to_esize_map_t;
160 edmonds_augmenting_path_finder(const Graph& arg_g, MateMap arg_mate,
161 VertexIndexMap arg_vm) :
164 n_vertices(num_vertices(arg_g)),
166 mate_vector(n_vertices),
167 ancestor_of_v_vector(n_vertices),
168 ancestor_of_w_vector(n_vertices),
169 vertex_state_vector(n_vertices),
170 origin_vector(n_vertices),
171 pred_vector(n_vertices),
172 bridge_vector(n_vertices),
173 ds_parent_vector(n_vertices),
174 ds_rank_vector(n_vertices),
176 mate(mate_vector.begin(), vm),
177 ancestor_of_v(ancestor_of_v_vector.begin(), vm),
178 ancestor_of_w(ancestor_of_w_vector.begin(), vm),
179 vertex_state(vertex_state_vector.begin(), vm),
180 origin(origin_vector.begin(), vm),
181 pred(pred_vector.begin(), vm),
182 bridge(bridge_vector.begin(), vm),
183 ds_parent_map(ds_parent_vector.begin(), vm),
184 ds_rank_map(ds_rank_vector.begin(), vm),
186 ds(ds_rank_map, ds_parent_map)
188 vertex_iterator_t vi, vi_end;
189 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
190 mate[*vi] = get(arg_mate, *vi);
196 bool augment_matching()
198 //As an optimization, some of these values can be saved from one
199 //iteration to the next instead of being re-initialized each
200 //iteration, allowing for "lazy blossom expansion." This is not
201 //currently implemented.
203 e_size_t timestamp = 0;
206 vertex_iterator_t vi, vi_end;
207 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
209 vertex_descriptor_t u = *vi;
213 ancestor_of_v[u] = 0;
214 ancestor_of_w[u] = 0;
217 if (mate[u] == graph_traits<Graph>::null_vertex())
219 vertex_state[u] = graph::detail::V_EVEN;
220 out_edge_iterator_t ei, ei_end;
221 for(boost::tie(ei,ei_end) = out_edges(u,g); ei != ei_end; ++ei)
223 if (target(*ei,g) != u)
225 even_edges.push_back( *ei );
230 vertex_state[u] = graph::detail::V_UNREACHED;
233 //end initializations
235 vertex_descriptor_t v,w,w_free_ancestor,v_free_ancestor;
236 w_free_ancestor = graph_traits<Graph>::null_vertex();
237 v_free_ancestor = graph_traits<Graph>::null_vertex();
238 bool found_alternating_path = false;
240 while(!even_edges.empty() && !found_alternating_path)
242 // since we push even edges onto the back of the list as
243 // they're discovered, taking them off the back will search
244 // for augmenting paths depth-first.
245 edge_descriptor_t current_edge = even_edges.back();
246 even_edges.pop_back();
248 v = source(current_edge,g);
249 w = target(current_edge,g);
251 vertex_descriptor_t v_prime = origin[ds.find_set(v)];
252 vertex_descriptor_t w_prime = origin[ds.find_set(w)];
254 // because of the way we put all of the edges on the queue,
255 // v_prime should be labeled V_EVEN; the following is a
256 // little paranoid but it could happen...
257 if (vertex_state[v_prime] != graph::detail::V_EVEN)
259 std::swap(v_prime,w_prime);
263 if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
265 vertex_state[w_prime] = graph::detail::V_ODD;
266 vertex_descriptor_t w_prime_mate = mate[w_prime];
267 vertex_state[w_prime_mate] = graph::detail::V_EVEN;
268 out_edge_iterator_t ei, ei_end;
269 for( boost::tie(ei,ei_end) = out_edges(w_prime_mate, g); ei != ei_end; ++ei)
271 if (target(*ei,g) != w_prime_mate)
273 even_edges.push_back(*ei);
279 //w_prime == v_prime can happen below if we get an edge that has been
280 //shrunk into a blossom
281 else if (vertex_state[w_prime] == graph::detail::V_EVEN && w_prime != v_prime)
283 vertex_descriptor_t w_up = w_prime;
284 vertex_descriptor_t v_up = v_prime;
285 vertex_descriptor_t nearest_common_ancestor
286 = graph_traits<Graph>::null_vertex();
287 w_free_ancestor = graph_traits<Graph>::null_vertex();
288 v_free_ancestor = graph_traits<Graph>::null_vertex();
290 // We now need to distinguish between the case that
291 // w_prime and v_prime share an ancestor under the
292 // "parent" relation, in which case we've found a
293 // blossom and should shrink it, or the case that
294 // w_prime and v_prime both have distinct ancestors that
295 // are free, in which case we've found an alternating
296 // path between those two ancestors.
300 while (nearest_common_ancestor == graph_traits<Graph>::null_vertex() &&
301 (v_free_ancestor == graph_traits<Graph>::null_vertex() ||
302 w_free_ancestor == graph_traits<Graph>::null_vertex()
306 ancestor_of_w[w_up] = timestamp;
307 ancestor_of_v[v_up] = timestamp;
309 if (w_free_ancestor == graph_traits<Graph>::null_vertex())
311 if (v_free_ancestor == graph_traits<Graph>::null_vertex())
314 if (mate[v_up] == graph_traits<Graph>::null_vertex())
315 v_free_ancestor = v_up;
316 if (mate[w_up] == graph_traits<Graph>::null_vertex())
317 w_free_ancestor = w_up;
319 if (ancestor_of_w[v_up] == timestamp)
320 nearest_common_ancestor = v_up;
321 else if (ancestor_of_v[w_up] == timestamp)
322 nearest_common_ancestor = w_up;
323 else if (v_free_ancestor == w_free_ancestor &&
324 v_free_ancestor != graph_traits<Graph>::null_vertex())
325 nearest_common_ancestor = v_up;
328 if (nearest_common_ancestor == graph_traits<Graph>::null_vertex())
329 found_alternating_path = true; //to break out of the loop
333 link_and_set_bridges(w_prime, nearest_common_ancestor, std::make_pair(w,v));
334 link_and_set_bridges(v_prime, nearest_common_ancestor, std::make_pair(v,w));
339 if (!found_alternating_path)
342 // retrieve the augmenting path and put it in aug_path
343 reversed_retrieve_augmenting_path(v, v_free_ancestor);
344 retrieve_augmenting_path(w, w_free_ancestor);
346 // augment the matching along aug_path
347 vertex_descriptor_t a,b;
348 while (!aug_path.empty())
350 a = aug_path.front();
351 aug_path.pop_front();
352 b = aug_path.front();
353 aug_path.pop_front();
365 template <typename PropertyMap>
366 void get_current_matching(PropertyMap pm)
368 vertex_iterator_t vi,vi_end;
369 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
370 put(pm, *vi, mate[*vi]);
376 template <typename PropertyMap>
377 void get_vertex_state_map(PropertyMap pm)
379 vertex_iterator_t vi,vi_end;
380 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
381 put(pm, *vi, vertex_state[origin[ds.find_set(*vi)]]);
389 vertex_descriptor_t parent(vertex_descriptor_t x)
391 if (vertex_state[x] == graph::detail::V_EVEN
392 && mate[x] != graph_traits<Graph>::null_vertex())
394 else if (vertex_state[x] == graph::detail::V_ODD)
395 return origin[ds.find_set(pred[x])];
403 void link_and_set_bridges(vertex_descriptor_t x,
404 vertex_descriptor_t stop_vertex,
405 vertex_pair_t the_bridge)
407 for(vertex_descriptor_t v = x; v != stop_vertex; v = parent(v))
409 ds.union_set(v, stop_vertex);
410 origin[ds.find_set(stop_vertex)] = stop_vertex;
412 if (vertex_state[v] == graph::detail::V_ODD)
414 bridge[v] = the_bridge;
415 out_edge_iterator_t oei, oei_end;
416 for(boost::tie(oei, oei_end) = out_edges(v,g); oei != oei_end; ++oei)
418 if (target(*oei,g) != v)
420 even_edges.push_back(*oei);
428 // Since none of the STL containers support both constant-time
429 // concatenation and reversal, the process of expanding an
430 // augmenting path once we know one exists is a little more
431 // complicated than it has to be. If we know the path is from v to
432 // w, then the augmenting path is recursively defined as:
434 // path(v,w) = [v], if v = w
435 // = concat([v, mate[v]], path(pred[mate[v]], w),
436 // if v != w and vertex_state[v] == graph::detail::V_EVEN
437 // = concat([v], reverse(path(x,mate[v])), path(y,w)),
438 // if v != w, vertex_state[v] == graph::detail::V_ODD, and bridge[v] = (x,y)
440 // These next two mutually recursive functions implement this definition.
442 void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w)
445 aug_path.push_back(v);
446 else if (vertex_state[v] == graph::detail::V_EVEN)
448 aug_path.push_back(v);
449 aug_path.push_back(mate[v]);
450 retrieve_augmenting_path(pred[mate[v]], w);
452 else //vertex_state[v] == graph::detail::V_ODD
454 aug_path.push_back(v);
455 reversed_retrieve_augmenting_path(bridge[v].first, mate[v]);
456 retrieve_augmenting_path(bridge[v].second, w);
461 void reversed_retrieve_augmenting_path(vertex_descriptor_t v,
462 vertex_descriptor_t w)
466 aug_path.push_back(v);
467 else if (vertex_state[v] == graph::detail::V_EVEN)
469 reversed_retrieve_augmenting_path(pred[mate[v]], w);
470 aug_path.push_back(mate[v]);
471 aug_path.push_back(v);
473 else //vertex_state[v] == graph::detail::V_ODD
475 reversed_retrieve_augmenting_path(bridge[v].second, w);
476 retrieve_augmenting_path(bridge[v].first, mate[v]);
477 aug_path.push_back(v);
484 //private data members
490 //storage for the property maps below
491 std::vector<vertex_descriptor_t> mate_vector;
492 std::vector<e_size_t> ancestor_of_v_vector;
493 std::vector<e_size_t> ancestor_of_w_vector;
494 std::vector<int> vertex_state_vector;
495 std::vector<vertex_descriptor_t> origin_vector;
496 std::vector<vertex_descriptor_t> pred_vector;
497 std::vector<vertex_pair_t> bridge_vector;
498 std::vector<vertex_descriptor_t> ds_parent_vector;
499 std::vector<v_size_t> ds_rank_vector;
501 //iterator property maps
502 vertex_to_vertex_map_t mate;
503 vertex_to_esize_map_t ancestor_of_v;
504 vertex_to_esize_map_t ancestor_of_w;
505 vertex_to_int_map_t vertex_state;
506 vertex_to_vertex_map_t origin;
507 vertex_to_vertex_map_t pred;
508 vertex_to_vertex_pair_map_t bridge;
509 vertex_to_vertex_map_t ds_parent_map;
510 vertex_to_vsize_map_t ds_rank_map;
512 vertex_list_t aug_path;
513 edge_list_t even_edges;
514 disjoint_sets< vertex_to_vsize_map_t, vertex_to_vertex_map_t > ds;
521 //***************************************************************************
522 //***************************************************************************
523 // Initial Matching Functors
524 //***************************************************************************
525 //***************************************************************************
527 template <typename Graph, typename MateMap>
528 struct greedy_matching
530 typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t;
531 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
532 typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t;
533 typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
535 static void find_matching(const Graph& g, MateMap mate)
537 vertex_iterator_t vi, vi_end;
538 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
539 put(mate, *vi, graph_traits<Graph>::null_vertex());
541 edge_iterator_t ei, ei_end;
542 for( boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
544 edge_descriptor_t e = *ei;
545 vertex_descriptor_t u = source(e,g);
546 vertex_descriptor_t v = target(e,g);
548 if (u != v && get(mate,u) == get(mate,v))
549 //only way equality can hold is if
550 // mate[u] == mate[v] == null_vertex
562 template <typename Graph, typename MateMap>
563 struct extra_greedy_matching
565 // The "extra greedy matching" is formed by repeating the
566 // following procedure as many times as possible: Choose the
567 // unmatched vertex v of minimum non-zero degree. Choose the
568 // neighbor w of v which is unmatched and has minimum degree over
569 // all of v's neighbors. Add (u,v) to the matching. Ties for
570 // either choice are broken arbitrarily. This procedure takes time
571 // O(m log n), where m is the number of edges in the graph and n
572 // is the number of vertices.
574 typedef typename graph_traits< Graph >::vertex_descriptor
576 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
577 typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor_t;
578 typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
579 typedef std::pair<vertex_descriptor_t, vertex_descriptor_t> vertex_pair_t;
583 inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
589 inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
593 template <class PairSelector>
594 class less_than_by_degree
597 less_than_by_degree(const Graph& g): m_g(g) {}
598 bool operator() (const vertex_pair_t x, const vertex_pair_t y)
601 out_degree(PairSelector::select_vertex(x), m_g)
602 < out_degree(PairSelector::select_vertex(y), m_g);
609 static void find_matching(const Graph& g, MateMap mate)
611 typedef std::vector<std::pair<vertex_descriptor_t, vertex_descriptor_t> >
612 directed_edges_vector_t;
614 directed_edges_vector_t edge_list;
615 vertex_iterator_t vi, vi_end;
616 for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
617 put(mate, *vi, graph_traits<Graph>::null_vertex());
619 edge_iterator_t ei, ei_end;
620 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
622 edge_descriptor_t e = *ei;
623 vertex_descriptor_t u = source(e,g);
624 vertex_descriptor_t v = target(e,g);
625 if (u == v) continue;
626 edge_list.push_back(std::make_pair(u,v));
627 edge_list.push_back(std::make_pair(v,u));
630 //sort the edges by the degree of the target, then (using a
631 //stable sort) by degree of the source
632 std::sort(edge_list.begin(), edge_list.end(),
633 less_than_by_degree<select_second>(g));
634 std::stable_sort(edge_list.begin(), edge_list.end(),
635 less_than_by_degree<select_first>(g));
637 //construct the extra greedy matching
638 for(typename directed_edges_vector_t::const_iterator itr = edge_list.begin(); itr != edge_list.end(); ++itr)
640 if (get(mate,itr->first) == get(mate,itr->second))
641 //only way equality can hold is if mate[itr->first] == mate[itr->second] == null_vertex
643 put(mate, itr->first, itr->second);
644 put(mate, itr->second, itr->first);
653 template <typename Graph, typename MateMap>
654 struct empty_matching
656 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
658 static void find_matching(const Graph& g, MateMap mate)
660 vertex_iterator_t vi, vi_end;
661 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
662 put(mate, *vi, graph_traits<Graph>::null_vertex());
669 //***************************************************************************
670 //***************************************************************************
671 // Matching Verifiers
672 //***************************************************************************
673 //***************************************************************************
678 template <typename SizeType>
679 class odd_components_counter : public dfs_visitor<>
680 // This depth-first search visitor will count the number of connected
681 // components with an odd number of vertices. It's used by
682 // maximum_matching_verifier.
685 odd_components_counter(SizeType& c_count):
691 template <class Vertex, class Graph>
692 void start_vertex(Vertex, Graph&)
697 template <class Vertex, class Graph>
698 void discover_vertex(Vertex, Graph&)
700 m_parity = !m_parity;
701 m_parity ? ++m_count : --m_count;
717 template <typename Graph, typename MateMap,
718 typename VertexIndexMap = dummy_property_map>
719 struct no_matching_verifier
722 verify_matching(const Graph&, MateMap, VertexIndexMap)
729 template <typename Graph, typename MateMap, typename VertexIndexMap>
730 struct maximum_cardinality_matching_verifier
733 template <typename X>
734 struct map_vertex_to_
736 typedef boost::iterator_property_map<typename std::vector<X>::iterator,
737 VertexIndexMap> type;
740 typedef typename graph_traits<Graph>::vertex_descriptor
742 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
743 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
744 typedef typename map_vertex_to_<int>::type vertex_to_int_map_t;
745 typedef typename map_vertex_to_<vertex_descriptor_t>::type
746 vertex_to_vertex_map_t;
749 template <typename VertexStateMap>
750 struct non_odd_vertex {
751 //this predicate is used to create a filtered graph that
752 //excludes vertices labeled "graph::detail::V_ODD"
753 non_odd_vertex() : vertex_state(0) { }
755 non_odd_vertex(VertexStateMap* arg_vertex_state)
756 : vertex_state(arg_vertex_state) { }
758 template <typename Vertex>
759 bool operator()(const Vertex& v) const
761 BOOST_ASSERT(vertex_state);
762 return get(*vertex_state, v) != graph::detail::V_ODD;
765 VertexStateMap* vertex_state;
769 static bool verify_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
771 //For any graph G, let o(G) be the number of connected
772 //components in G of odd size. For a subset S of G's vertex set
773 //V(G), let (G - S) represent the subgraph of G induced by
774 //removing all vertices in S from G. Let M(G) be the size of the
775 //maximum cardinality matching in G. Then the Tutte-Berge
776 //formula guarantees that
778 // 2 * M(G) = min ( |V(G)| + |U| + o(G - U) )
780 //where the minimum is taken over all subsets U of
781 //V(G). Edmonds' algorithm finds a set U that achieves the
782 //minimum in the above formula, namely the vertices labeled
783 //"ODD." This function runs one iteration of Edmonds' algorithm
784 //to find U, then verifies that the size of the matching given
785 //by mate satisfies the Tutte-Berge formula.
787 //first, make sure it's a valid matching
788 if (!is_a_matching(g,mate,vm))
791 //We'll try to augment the matching once. This serves two
792 //purposes: first, if we find some augmenting path, the matching
793 //is obviously non-maximum. Second, running edmonds' algorithm
794 //on a graph with no augmenting path will create the
795 //Edmonds-Gallai decomposition that we need as a certificate of
796 //maximality - we can get it by looking at the vertex_state map
798 edmonds_augmenting_path_finder<Graph,MateMap,VertexIndexMap>
799 augmentor(g,mate,vm);
800 if (augmentor.augment_matching())
803 std::vector<int> vertex_state_vector(num_vertices(g));
804 vertex_to_int_map_t vertex_state(vertex_state_vector.begin(), vm);
805 augmentor.get_vertex_state_map(vertex_state);
807 //count the number of graph::detail::V_ODD vertices
808 v_size_t num_odd_vertices = 0;
809 vertex_iterator_t vi, vi_end;
810 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
811 if (vertex_state[*vi] == graph::detail::V_ODD)
814 //count the number of connected components with odd cardinality
815 //in the graph without graph::detail::V_ODD vertices
816 non_odd_vertex<vertex_to_int_map_t> filter(&vertex_state);
817 filtered_graph<Graph, keep_all, non_odd_vertex<vertex_to_int_map_t> > fg(g, keep_all(), filter);
819 v_size_t num_odd_components;
820 detail::odd_components_counter<v_size_t> occ(num_odd_components);
821 depth_first_search(fg, visitor(occ).vertex_index_map(vm));
823 if (2 * matching_size(g,mate,vm) == num_vertices(g) + num_odd_vertices - num_odd_components)
833 template <typename Graph,
835 typename VertexIndexMap,
836 template <typename, typename, typename> class AugmentingPathFinder,
837 template <typename, typename> class InitialMatchingFinder,
838 template <typename, typename, typename> class MatchingVerifier>
839 bool matching(const Graph& g, MateMap mate, VertexIndexMap vm)
842 InitialMatchingFinder<Graph,MateMap>::find_matching(g,mate);
844 AugmentingPathFinder<Graph,MateMap,VertexIndexMap> augmentor(g,mate,vm);
845 bool not_maximum_yet = true;
846 while(not_maximum_yet)
848 not_maximum_yet = augmentor.augment_matching();
850 augmentor.get_current_matching(mate);
852 return MatchingVerifier<Graph,MateMap,VertexIndexMap>::verify_matching(g,mate,vm);
859 template <typename Graph, typename MateMap, typename VertexIndexMap>
860 inline bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
863 < Graph, MateMap, VertexIndexMap,
864 edmonds_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
871 template <typename Graph, typename MateMap>
872 inline bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate)
874 return checked_edmonds_maximum_cardinality_matching(g, mate, get(vertex_index,g));
880 template <typename Graph, typename MateMap, typename VertexIndexMap>
881 inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
883 matching < Graph, MateMap, VertexIndexMap,
884 edmonds_augmenting_path_finder, extra_greedy_matching, no_matching_verifier>
891 template <typename Graph, typename MateMap>
892 inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate)
894 edmonds_maximum_cardinality_matching(g, mate, get(vertex_index,g));
899 #endif //BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP