]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(w_up); | |
311 | if (v_free_ancestor == graph_traits<Graph>::null_vertex()) | |
312 | v_up = parent(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(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)); | |
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, v_free_ancestor); | |
344 | retrieve_augmenting_path(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(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(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(bridge[v].first, mate[v]); | |
456 | retrieve_augmenting_path(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(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(bridge[v].second, w); | |
476 | retrieve_augmenting_path(bridge[v].first, 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 |