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 | |
27 | namespace 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 |
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 | ; |
576 | typedef typename graph_traits< Graph >::vertex_iterator ; |
577 | typedef typename graph_traits< Graph >::edge_descriptor ; |
578 | typedef typename graph_traits< Graph >::edge_iterator ; |
579 | typedef std::pair<vertex_descriptor_t, vertex_descriptor_t> ; |
580 | |
581 | struct |
582 | { |
583 | inline static vertex_descriptor_t (const vertex_pair_t p) |
584 | {return p.first;} |
585 | }; |
586 | |
587 | struct |
588 | { |
589 | inline static vertex_descriptor_t (const vertex_pair_t p) |
590 | {return p.second;} |
591 | }; |
592 | |
593 | template <class PairSelector> |
594 | class |
595 | { |
596 | public: |
597 | (const Graph& g): m_g(g) {} |
598 | bool (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& ; |
606 | }; |
607 | |
608 | |
609 | static void (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 | |