1//=======================================================================
2// Copyright (c) 2005 Aaron Windsor
3//
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)
7//
8//=======================================================================
9
10#ifndef BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
11#define BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
12
13#include <vector>
14#include <list>
15#include <deque>
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>
25
26
27namespace boost
28{
29 namespace graph { namespace detail {
30 enum { V_EVEN, V_ODD, V_UNREACHED };
31 } } // end namespace graph::detail
32
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)
36 {
37 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
38 typedef typename graph_traits<Graph>::vertex_descriptor
39 vertex_descriptor_t;
40 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
41
42 v_size_t size_of_matching = 0;
43 vertex_iterator_t vi, vi_end;
44
45 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
46 {
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)))
50 ++size_of_matching;
51 }
52 return size_of_matching;
53 }
54
55
56
57
58 template <typename Graph, typename MateMap>
59 inline typename graph_traits<Graph>::vertices_size_type
60 matching_size(const Graph& g, MateMap mate)
61 {
62 return matching_size(g, mate, get(vertex_index,g));
63 }
64
65
66
67
68 template <typename Graph, typename MateMap, typename VertexIndexMap>
69 bool is_a_matching(const Graph& g, MateMap mate, VertexIndexMap)
70 {
71 typedef typename graph_traits<Graph>::vertex_descriptor
72 vertex_descriptor_t;
73 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
74
75 vertex_iterator_t vi, vi_end;
76 for( boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
77 {
78 vertex_descriptor_t v = *vi;
79 if (get(mate,v) != graph_traits<Graph>::null_vertex()
80 && v != get(mate,get(mate,v)))
81 return false;
82 }
83 return true;
84 }
85
86
87
88
89 template <typename Graph, typename MateMap>
90 inline bool is_a_matching(const Graph& g, MateMap mate)
91 {
92 return is_a_matching(g, mate, get(vertex_index,g));
93 }
94
95
96
97
98 //***************************************************************************
99 //***************************************************************************
100 // Maximum Cardinality Matching Functors
101 //***************************************************************************
102 //***************************************************************************
103
104 template <typename Graph, typename MateMap,
105 typename VertexIndexMap = dummy_property_map>
106 struct no_augmenting_path_finder
107 {
108 no_augmenting_path_finder(const Graph&, MateMap, VertexIndexMap)
109 { }
110
111 inline bool augment_matching() { return false; }
112
113 template <typename PropertyMap>
114 void get_current_matching(PropertyMap) {}
115 };
116
117
118
119
120 template <typename Graph, typename MateMap, typename VertexIndexMap>
121 class edmonds_augmenting_path_finder
122 {
123 // This implementation of Edmonds' matching algorithm closely
124 // follows Tarjan's description of the algorithm in "Data
125 // Structures and Network Algorithms."
126
127 public:
128
129 //generates the type of an iterator property map from vertices to type X
130 template <typename X>
131 struct map_vertex_to_
132 {
133 typedef boost::iterator_property_map<typename std::vector<X>::iterator,
134 VertexIndexMap> type;
135 };
136
137 typedef typename graph_traits<Graph>::vertex_descriptor
138 vertex_descriptor_t;
139 typedef typename std::pair< vertex_descriptor_t, vertex_descriptor_t >
140 vertex_pair_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
146 out_edge_iterator_t;
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;
156
157
158
159
160 edmonds_augmenting_path_finder(const Graph& arg_g, MateMap arg_mate,
161 VertexIndexMap arg_vm) :
162 g(arg_g),
163 vm(arg_vm),
164 n_vertices(num_vertices(arg_g)),
165
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),
175
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),
185
186 ds(ds_rank_map, ds_parent_map)
187 {
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);
191 }
192
193
194
195
196 bool augment_matching()
197 {
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.
202
203 e_size_t timestamp = 0;
204 even_edges.clear();
205
206 vertex_iterator_t vi, vi_end;
207 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
208 {
209 vertex_descriptor_t u = *vi;
210
211 origin[u] = u;
212 pred[u] = u;
213 ancestor_of_v[u] = 0;
214 ancestor_of_w[u] = 0;
215 ds.make_set(u);
216
217 if (mate[u] == graph_traits<Graph>::null_vertex())
218 {
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)
222 {
223 if (target(*ei,g) != u)
224 {
225 even_edges.push_back( *ei );
226 }
227 }
228 }
229 else
230 vertex_state[u] = graph::detail::V_UNREACHED;
231 }
232
233 //end initializations
234
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;
239
240 while(!even_edges.empty() && !found_alternating_path)
241 {
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();
247
248 v = source(current_edge,g);
249 w = target(current_edge,g);
250
251 vertex_descriptor_t v_prime = origin[ds.find_set(v)];
252 vertex_descriptor_t w_prime = origin[ds.find_set(w)];
253
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)
258 {
259 std::swap(v_prime,w_prime);
260 std::swap(v,w);
261 }
262
263 if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
264 {
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)
270 {
271 if (target(*ei,g) != w_prime_mate)
272 {
273 even_edges.push_back(*ei);
274 }
275 }
276 pred[w_prime] = v;
277 }
278
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)
282 {
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();
289
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.
297
298 ++timestamp;
299
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()
303 )
304 )
305 {
306 ancestor_of_w[w_up] = timestamp;
307 ancestor_of_v[v_up] = timestamp;
308
309 if (w_free_ancestor == graph_traits<Graph>::null_vertex())
310 w_up = parent(x: w_up);
311 if (v_free_ancestor == graph_traits<Graph>::null_vertex())
312 v_up = parent(x: v_up);
313
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;
318
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;
326 }
327
328 if (nearest_common_ancestor == graph_traits<Graph>::null_vertex())
329 found_alternating_path = true; //to break out of the loop
330 else
331 {
332 //shrink the blossom
333 link_and_set_bridges(x: w_prime, stop_vertex: nearest_common_ancestor, the_bridge: std::make_pair(w,v));
334 link_and_set_bridges(x: v_prime, stop_vertex: nearest_common_ancestor, the_bridge: std::make_pair(v,w));
335 }
336 }
337 }
338
339 if (!found_alternating_path)
340 return false;
341
342 // retrieve the augmenting path and put it in aug_path
343 reversed_retrieve_augmenting_path(v, w: v_free_ancestor);
344 retrieve_augmenting_path(v: w, w: w_free_ancestor);
345
346 // augment the matching along aug_path
347 vertex_descriptor_t a,b;
348 while (!aug_path.empty())
349 {
350 a = aug_path.front();
351 aug_path.pop_front();
352 b = aug_path.front();
353 aug_path.pop_front();
354 mate[a] = b;
355 mate[b] = a;
356 }
357
358 return true;
359
360 }
361
362
363
364
365 template <typename PropertyMap>
366 void get_current_matching(PropertyMap pm)
367 {
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]);
371 }
372
373
374
375
376 template <typename PropertyMap>
377 void get_vertex_state_map(PropertyMap pm)
378 {
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)]]);
382 }
383
384
385
386
387 private:
388
389 vertex_descriptor_t parent(vertex_descriptor_t x)
390 {
391 if (vertex_state[x] == graph::detail::V_EVEN
392 && mate[x] != graph_traits<Graph>::null_vertex())
393 return mate[x];
394 else if (vertex_state[x] == graph::detail::V_ODD)
395 return origin[ds.find_set(pred[x])];
396 else
397 return x;
398 }
399
400
401
402
403 void link_and_set_bridges(vertex_descriptor_t x,
404 vertex_descriptor_t stop_vertex,
405 vertex_pair_t the_bridge)
406 {
407 for(vertex_descriptor_t v = x; v != stop_vertex; v = parent(x: v))
408 {
409 ds.union_set(v, stop_vertex);
410 origin[ds.find_set(stop_vertex)] = stop_vertex;
411
412 if (vertex_state[v] == graph::detail::V_ODD)
413 {
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)
417 {
418 if (target(*oei,g) != v)
419 {
420 even_edges.push_back(*oei);
421 }
422 }
423 }
424 }
425 }
426
427
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:
433 //
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)
439 //
440 // These next two mutually recursive functions implement this definition.
441
442 void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w)
443 {
444 if (v == w)
445 aug_path.push_back(v);
446 else if (vertex_state[v] == graph::detail::V_EVEN)
447 {
448 aug_path.push_back(v);
449 aug_path.push_back(mate[v]);
450 retrieve_augmenting_path(v: pred[mate[v]], w);
451 }
452 else //vertex_state[v] == graph::detail::V_ODD
453 {
454 aug_path.push_back(v);
455 reversed_retrieve_augmenting_path(v: bridge[v].first, w: mate[v]);
456 retrieve_augmenting_path(v: bridge[v].second, w);
457 }
458 }
459
460
461 void reversed_retrieve_augmenting_path(vertex_descriptor_t v,
462 vertex_descriptor_t w)
463 {
464
465 if (v == w)
466 aug_path.push_back(v);
467 else if (vertex_state[v] == graph::detail::V_EVEN)
468 {
469 reversed_retrieve_augmenting_path(v: pred[mate[v]], w);
470 aug_path.push_back(mate[v]);
471 aug_path.push_back(v);
472 }
473 else //vertex_state[v] == graph::detail::V_ODD
474 {
475 reversed_retrieve_augmenting_path(v: bridge[v].second, w);
476 retrieve_augmenting_path(v: bridge[v].first, w: mate[v]);
477 aug_path.push_back(v);
478 }
479 }
480
481
482
483
484 //private data members
485
486 const Graph& g;
487 VertexIndexMap vm;
488 v_size_t n_vertices;
489
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;
500
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;
511
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;
515
516 };
517
518
519
520
521 //***************************************************************************
522 //***************************************************************************
523 // Initial Matching Functors
524 //***************************************************************************
525 //***************************************************************************
526
527 template <typename Graph, typename MateMap>
528 struct greedy_matching
529 {
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;
534
535 static void find_matching(const Graph& g, MateMap mate)
536 {
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());
540
541 edge_iterator_t ei, ei_end;
542 for( boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
543 {
544 edge_descriptor_t e = *ei;
545 vertex_descriptor_t u = source(e,g);
546 vertex_descriptor_t v = target(e,g);
547
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
551 {
552 put(mate,u,v);
553 put(mate,v,u);
554 }
555 }
556 }
557 };
558
559
560
561
562 template <typename Graph, typename MateMap>
563 struct extra_greedy_matching
564 {
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.
573
574 typedef typename graph_traits< Graph >::vertex_descriptor
575 vertex_descriptor_t;
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;
580
581 struct select_first
582 {
583 inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
584 {return p.first;}
585 };
586
587 struct select_second
588 {
589 inline static vertex_descriptor_t select_vertex(const vertex_pair_t p)
590 {return p.second;}
591 };
592
593 template <class PairSelector>
594 class less_than_by_degree
595 {
596 public:
597 less_than_by_degree(const Graph& g): m_g(g) {}
598 bool operator() (const vertex_pair_t x, const vertex_pair_t y)
599 {
600 return
601 out_degree(PairSelector::select_vertex(x), m_g)
602 < out_degree(PairSelector::select_vertex(y), m_g);
603 }
604 private:
605 const Graph& m_g;
606 };
607
608
609 static void find_matching(const Graph& g, MateMap mate)
610 {
611 typedef std::vector<std::pair<vertex_descriptor_t, vertex_descriptor_t> >
612 directed_edges_vector_t;
613
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());
618
619 edge_iterator_t ei, ei_end;
620 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
621 {
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));
628 }
629
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));
636
637 //construct the extra greedy matching
638 for(typename directed_edges_vector_t::const_iterator itr = edge_list.begin(); itr != edge_list.end(); ++itr)
639 {
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
642 {
643 put(mate, itr->first, itr->second);
644 put(mate, itr->second, itr->first);
645 }
646 }
647 }
648 };
649
650
651
652
653 template <typename Graph, typename MateMap>
654 struct empty_matching
655 {
656 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
657
658 static void find_matching(const Graph& g, MateMap mate)
659 {
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());
663 }
664 };
665
666
667
668
669 //***************************************************************************
670 //***************************************************************************
671 // Matching Verifiers
672 //***************************************************************************
673 //***************************************************************************
674
675 namespace detail
676 {
677
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.
683 {
684 public:
685 odd_components_counter(SizeType& c_count):
686 m_count(c_count)
687 {
688 m_count = 0;
689 }
690
691 template <class Vertex, class Graph>
692 void start_vertex(Vertex, Graph&)
693 {
694 m_parity = false;
695 }
696
697 template <class Vertex, class Graph>
698 void discover_vertex(Vertex, Graph&)
699 {
700 m_parity = !m_parity;
701 m_parity ? ++m_count : --m_count;
702 }
703
704 protected:
705 SizeType& m_count;
706
707 private:
708 bool m_parity;
709
710 };
711
712 }//namespace detail
713
714
715
716
717 template <typename Graph, typename MateMap,
718 typename VertexIndexMap = dummy_property_map>
719 struct no_matching_verifier
720 {
721 inline static bool
722 verify_matching(const Graph&, MateMap, VertexIndexMap)
723 { return true;}
724 };
725
726
727
728
729 template <typename Graph, typename MateMap, typename VertexIndexMap>
730 struct maximum_cardinality_matching_verifier
731 {
732
733 template <typename X>
734 struct map_vertex_to_
735 {
736 typedef boost::iterator_property_map<typename std::vector<X>::iterator,
737 VertexIndexMap> type;
738 };
739
740 typedef typename graph_traits<Graph>::vertex_descriptor
741 vertex_descriptor_t;
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;
747
748
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) { }
754
755 non_odd_vertex(VertexStateMap* arg_vertex_state)
756 : vertex_state(arg_vertex_state) { }
757
758 template <typename Vertex>
759 bool operator()(const Vertex& v) const
760 {
761 BOOST_ASSERT(vertex_state);
762 return get(*vertex_state, v) != graph::detail::V_ODD;
763 }
764
765 VertexStateMap* vertex_state;
766 };
767
768
769 static bool verify_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
770 {
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
777 //
778 // 2 * M(G) = min ( |V(G)| + |U| + o(G - U) )
779 //
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.
786
787 //first, make sure it's a valid matching
788 if (!is_a_matching(g,mate,vm))
789 return false;
790
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
797 //that results.
798 edmonds_augmenting_path_finder<Graph,MateMap,VertexIndexMap>
799 augmentor(g,mate,vm);
800 if (augmentor.augment_matching())
801 return false;
802
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);
806
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)
812 ++num_odd_vertices;
813
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);
818
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));
822
823 if (2 * matching_size(g,mate,vm) == num_vertices(g) + num_odd_vertices - num_odd_components)
824 return true;
825 else
826 return false;
827 }
828 };
829
830
831
832
833 template <typename Graph,
834 typename MateMap,
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)
840 {
841
842 InitialMatchingFinder<Graph,MateMap>::find_matching(g,mate);
843
844 AugmentingPathFinder<Graph,MateMap,VertexIndexMap> augmentor(g,mate,vm);
845 bool not_maximum_yet = true;
846 while(not_maximum_yet)
847 {
848 not_maximum_yet = augmentor.augment_matching();
849 }
850 augmentor.get_current_matching(mate);
851
852 return MatchingVerifier<Graph,MateMap,VertexIndexMap>::verify_matching(g,mate,vm);
853
854 }
855
856
857
858
859 template <typename Graph, typename MateMap, typename VertexIndexMap>
860 inline bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
861 {
862 return matching
863 < Graph, MateMap, VertexIndexMap,
864 edmonds_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
865 (g, mate, vm);
866 }
867
868
869
870
871 template <typename Graph, typename MateMap>
872 inline bool checked_edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate)
873 {
874 return checked_edmonds_maximum_cardinality_matching(g, mate, get(vertex_index,g));
875 }
876
877
878
879
880 template <typename Graph, typename MateMap, typename VertexIndexMap>
881 inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
882 {
883 matching < Graph, MateMap, VertexIndexMap,
884 edmonds_augmenting_path_finder, extra_greedy_matching, no_matching_verifier>
885 (g, mate, vm);
886 }
887
888
889
890
891 template <typename Graph, typename MateMap>
892 inline void edmonds_maximum_cardinality_matching(const Graph& g, MateMap mate)
893 {
894 edmonds_maximum_cardinality_matching(g, mate, get(vertex_index,g));
895 }
896
897}//namespace boost
898
899#endif //BOOST_GRAPH_MAXIMUM_CARDINALITY_MATCHING_HPP
900

source code of boost/boost/graph/max_cardinality_matching.hpp