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 | #include <boost/config.hpp> |
11 | |
12 | #ifdef BOOST_MSVC |
13 | // Without disabling this we get hard errors about initialialized pointers: |
14 | #pragma warning(disable : 4703) |
15 | #endif |
16 | |
17 | #include <boost/graph/max_cardinality_matching.hpp> |
18 | |
19 | #include <iostream> // for std::cout |
20 | #include <boost/property_map/vector_property_map.hpp> |
21 | #include <boost/graph/adjacency_list.hpp> |
22 | #include <boost/graph/adjacency_matrix.hpp> |
23 | #include <boost/graph/random.hpp> |
24 | #include <ctime> |
25 | #include <boost/random.hpp> |
26 | #include <boost/core/lightweight_test.hpp> |
27 | |
28 | using namespace boost; |
29 | |
30 | typedef adjacency_list< vecS, vecS, undirectedS, |
31 | property< vertex_index_t, int > > |
32 | undirected_graph; |
33 | |
34 | typedef adjacency_list< listS, listS, undirectedS, |
35 | property< vertex_index_t, int > > |
36 | undirected_list_graph; |
37 | |
38 | typedef adjacency_matrix< undirectedS, property< vertex_index_t, int > > |
39 | undirected_adjacency_matrix_graph; |
40 | |
41 | template < typename Graph > struct vertex_index_installer |
42 | { |
43 | static void install(Graph&) {} |
44 | }; |
45 | |
46 | template <> struct vertex_index_installer< undirected_list_graph > |
47 | { |
48 | static void install(undirected_list_graph& g) |
49 | { |
50 | typedef graph_traits< undirected_list_graph >::vertex_iterator |
51 | vertex_iterator_t; |
52 | typedef graph_traits< undirected_list_graph >::vertices_size_type |
53 | v_size_t; |
54 | |
55 | vertex_iterator_t vi, vi_end; |
56 | v_size_t i = 0; |
57 | for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi, ++i) |
58 | put(p: vertex_index, g, key: *vi, value: i); |
59 | } |
60 | }; |
61 | |
62 | template < typename Graph > void complete_graph(Graph& g, int n) |
63 | { |
64 | // creates the complete graph on n vertices |
65 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; |
66 | |
67 | g = Graph(n); |
68 | vertex_iterator_t vi, vi_end, wi; |
69 | boost::tie(vi, vi_end) = vertices(g); |
70 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
71 | { |
72 | wi = vi; |
73 | ++wi; |
74 | for (; wi != vi_end; ++wi) |
75 | add_edge(*vi, *wi, g); |
76 | } |
77 | } |
78 | |
79 | template < typename Graph > void gabows_graph(Graph& g, int n) |
80 | { |
81 | // creates a graph with 2n vertices, consisting of the complete graph |
82 | // on n vertices plus n vertices of degree one, each adjacent to one |
83 | // vertex in the complete graph. without any initial matching, this |
84 | // graph forces edmonds' algorithm into worst-case behavior. |
85 | |
86 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; |
87 | |
88 | g = Graph(2 * n); |
89 | |
90 | vertex_iterator_t vi, vi_end, ui, ui_end, halfway; |
91 | |
92 | boost::tie(ui, ui_end) = vertices(g); |
93 | |
94 | halfway = ui; |
95 | for (int i = 0; i < n; ++i) |
96 | ++halfway; |
97 | |
98 | while (ui != halfway) |
99 | { |
100 | vi = ui; |
101 | ++vi; |
102 | while (vi != halfway) |
103 | { |
104 | add_edge(*ui, *vi, g); |
105 | ++vi; |
106 | } |
107 | ++ui; |
108 | } |
109 | |
110 | boost::tie(ui, ui_end) = vertices(g); |
111 | |
112 | while (halfway != ui_end) |
113 | { |
114 | add_edge(*ui, *halfway, g); |
115 | ++ui; |
116 | ++halfway; |
117 | } |
118 | } |
119 | |
120 | template < typename Graph > |
121 | void matching_test(std::size_t num_v, const std::string& graph_name) |
122 | { |
123 | typedef |
124 | typename property_map< Graph, vertex_index_t >::type vertex_index_map_t; |
125 | typedef vector_property_map< |
126 | typename graph_traits< Graph >::vertex_descriptor, vertex_index_map_t > |
127 | mate_t; |
128 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t; |
129 | typedef |
130 | typename graph_traits< Graph >::vertex_descriptor vertex_descriptor_t; |
131 | |
132 | const std::size_t double_num_v = num_v * 2; |
133 | |
134 | bool all_tests_passed = true; |
135 | |
136 | // form the complete graph on 2*n vertices; the maximum cardinality |
137 | // matching, greedy matching, and extra greedy matching should all be the |
138 | // same - a matching of size n. |
139 | |
140 | Graph g(double_num_v); |
141 | complete_graph(g, double_num_v); |
142 | |
143 | vertex_index_installer< Graph >::install(g); |
144 | |
145 | mate_t edmonds_mate(double_num_v); |
146 | mate_t greedy_mate(double_num_v); |
147 | mate_t (double_num_v); |
148 | |
149 | // find a maximum cardinality matching using edmonds' blossom-shrinking |
150 | // algorithm, starting with an empty matching. |
151 | bool edmonds_result = matching< Graph, mate_t, vertex_index_map_t, |
152 | edmonds_augmenting_path_finder, empty_matching, |
153 | maximum_cardinality_matching_verifier >( |
154 | g, edmonds_mate, get(vertex_index, g)); |
155 | |
156 | BOOST_TEST(edmonds_result); |
157 | if (!edmonds_result) |
158 | { |
159 | std::cout |
160 | << "Verifier reporting a problem finding a perfect matching on" |
161 | << std::endl |
162 | << "the complete graph using " << graph_name << std::endl; |
163 | all_tests_passed = false; |
164 | } |
165 | |
166 | // find a greedy matching |
167 | bool greedy_result = matching< Graph, mate_t, vertex_index_map_t, |
168 | no_augmenting_path_finder, greedy_matching, |
169 | maximum_cardinality_matching_verifier >( |
170 | g, greedy_mate, get(vertex_index, g)); |
171 | |
172 | BOOST_TEST(greedy_result); |
173 | if (!greedy_result) |
174 | { |
175 | std::cout << "Verifier reporting a problem finding a greedy matching on" |
176 | << std::endl |
177 | << "the complete graph using " << graph_name << std::endl; |
178 | all_tests_passed = false; |
179 | } |
180 | |
181 | // find an extra greedy matching |
182 | bool = matching< Graph, mate_t, vertex_index_map_t, |
183 | no_augmenting_path_finder, extra_greedy_matching, |
184 | maximum_cardinality_matching_verifier >( |
185 | g, extra_greedy_mate, get(vertex_index, g)); |
186 | |
187 | BOOST_TEST(extra_greedy_result); |
188 | if (!extra_greedy_result) |
189 | { |
190 | std::cout << "Verifier reporting a problem finding an extra greedy " |
191 | "matching on" |
192 | << std::endl |
193 | << "the complete graph using " << graph_name << std::endl; |
194 | all_tests_passed = false; |
195 | } |
196 | |
197 | // as a sanity check, make sure that each of the matchings returned is a |
198 | // valid matching and has 1000 edges. |
199 | |
200 | bool edmonds_sanity_check = is_a_matching(g, edmonds_mate) |
201 | && matching_size(g, edmonds_mate) == num_v; |
202 | |
203 | BOOST_TEST(edmonds_sanity_check); |
204 | if (edmonds_result && !edmonds_sanity_check) |
205 | { |
206 | std::cout |
207 | << "Verifier okayed edmonds' algorithm on the complete graph, but" |
208 | << std::endl |
209 | << "the matching returned either wasn't a valid matching or wasn't" |
210 | << std::endl |
211 | << "actually a maximum cardinality matching." << std::endl; |
212 | all_tests_passed = false; |
213 | } |
214 | |
215 | bool greedy_sanity_check = is_a_matching(g, greedy_mate) |
216 | && matching_size(g, greedy_mate) == num_v; |
217 | |
218 | BOOST_TEST(greedy_sanity_check); |
219 | if (greedy_result && !greedy_sanity_check) |
220 | { |
221 | std::cout |
222 | << "Verifier okayed greedy algorithm on the complete graph, but" |
223 | << std::endl |
224 | << "the matching returned either wasn't a valid matching or wasn't" |
225 | << std::endl |
226 | << "actually a maximum cardinality matching." << std::endl; |
227 | all_tests_passed = false; |
228 | } |
229 | |
230 | bool = is_a_matching(g, extra_greedy_mate) |
231 | && matching_size(g, extra_greedy_mate) == num_v; |
232 | |
233 | BOOST_TEST(extra_greedy_sanity_check); |
234 | if (extra_greedy_result && !extra_greedy_sanity_check) |
235 | { |
236 | std::cout |
237 | << "Verifier okayed extra greedy algorithm on the complete graph, " |
238 | "but" |
239 | << std::endl |
240 | << "the matching returned either wasn't a valid matching or wasn't" |
241 | << std::endl |
242 | << "actually a maximum cardinality matching." << std::endl; |
243 | all_tests_passed = false; |
244 | } |
245 | |
246 | // Now remove an edge from the edmonds_mate matching. |
247 | vertex_iterator_t vi, vi_end; |
248 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
249 | if (edmonds_mate[*vi] != graph_traits< Graph >::null_vertex()) |
250 | break; |
251 | |
252 | edmonds_mate[edmonds_mate[*vi]] = graph_traits< Graph >::null_vertex(); |
253 | edmonds_mate[*vi] = graph_traits< Graph >::null_vertex(); |
254 | |
255 | //...and run the matching verifier - it should tell us that the matching |
256 | // isn't a maximum matching. |
257 | bool modified_edmonds_verification_result |
258 | = maximum_cardinality_matching_verifier< Graph, mate_t, |
259 | vertex_index_map_t >::verify_matching(g, edmonds_mate, |
260 | get(vertex_index, g)); |
261 | |
262 | BOOST_TEST(!modified_edmonds_verification_result); |
263 | if (modified_edmonds_verification_result) |
264 | { |
265 | std::cout << "Verifier was fooled into thinking that a non-maximum " |
266 | "matching was maximum" |
267 | << std::endl; |
268 | all_tests_passed = false; |
269 | } |
270 | |
271 | Graph h(double_num_v); |
272 | gabows_graph(h, num_v); |
273 | |
274 | vertex_index_installer< Graph >::install(h); |
275 | |
276 | // gabow's graph always has a perfect matching. it's also a good example of |
277 | // why one should initialize with the extra_greedy_matching in most cases. |
278 | |
279 | mate_t gabow_mate(double_num_v); |
280 | |
281 | bool gabows_graph_result |
282 | = checked_edmonds_maximum_cardinality_matching(h, gabow_mate); |
283 | |
284 | BOOST_TEST(gabows_graph_result); |
285 | if (!gabows_graph_result) |
286 | { |
287 | std::cout |
288 | << "Problem on Gabow's Graph with " << graph_name << ":" |
289 | << std::endl |
290 | << " Verifier reporting a maximum cardinality matching not found." |
291 | << std::endl; |
292 | all_tests_passed = false; |
293 | } |
294 | |
295 | BOOST_TEST(matching_size(h, gabow_mate) == num_v); |
296 | if (gabows_graph_result && matching_size(h, gabow_mate) != num_v) |
297 | { |
298 | std::cout |
299 | << "Problem on Gabow's Graph with " << graph_name << ":" |
300 | << std::endl |
301 | << " Verifier reported a maximum cardinality matching found," |
302 | << std::endl |
303 | << " but matching size is " << matching_size(h, gabow_mate) |
304 | << " when it should be " << num_v << std::endl; |
305 | all_tests_passed = false; |
306 | } |
307 | |
308 | Graph j(double_num_v); |
309 | vertex_index_installer< Graph >::install(j); |
310 | |
311 | typedef boost::mt19937 base_generator_type; |
312 | base_generator_type generator(static_cast< unsigned int >(std::time(timer: 0))); |
313 | boost::uniform_int<> distribution(0, double_num_v - 1); |
314 | boost::variate_generator< base_generator_type&, boost::uniform_int<> > |
315 | rand_num(generator, distribution); |
316 | |
317 | std::size_t num_edges = 0; |
318 | bool success; |
319 | |
320 | while (num_edges < 4 * double_num_v) |
321 | { |
322 | vertex_descriptor_t u = random_vertex(j, rand_num); |
323 | vertex_descriptor_t v = random_vertex(j, rand_num); |
324 | if (u != v) |
325 | { |
326 | boost::tie(t0&: tuples::ignore, t1&: success) = add_edge(u, v, j); |
327 | if (success) |
328 | num_edges++; |
329 | } |
330 | } |
331 | |
332 | mate_t random_mate(double_num_v); |
333 | bool random_graph_result |
334 | = checked_edmonds_maximum_cardinality_matching(j, random_mate); |
335 | |
336 | BOOST_TEST(random_graph_result); |
337 | if (!random_graph_result) |
338 | { |
339 | std::cout << "Matching in random graph not maximum for " << graph_name |
340 | << std::endl; |
341 | all_tests_passed = false; |
342 | } |
343 | |
344 | // Now remove an edge from the random_mate matching. |
345 | for (boost::tie(vi, vi_end) = vertices(j); vi != vi_end; ++vi) |
346 | if (random_mate[*vi] != graph_traits< Graph >::null_vertex()) |
347 | break; |
348 | |
349 | random_mate[random_mate[*vi]] = graph_traits< Graph >::null_vertex(); |
350 | random_mate[*vi] = graph_traits< Graph >::null_vertex(); |
351 | |
352 | //...and run the matching verifier - it should tell us that the matching |
353 | // isn't a maximum matching. |
354 | bool modified_random_verification_result |
355 | = maximum_cardinality_matching_verifier< Graph, mate_t, |
356 | vertex_index_map_t >::verify_matching(j, random_mate, |
357 | get(vertex_index, j)); |
358 | |
359 | BOOST_TEST(!modified_random_verification_result); |
360 | if (modified_random_verification_result) |
361 | { |
362 | std::cout << "Verifier was fooled into thinking that a non-maximum " |
363 | "matching was maximum" |
364 | << std::endl; |
365 | all_tests_passed = false; |
366 | } |
367 | |
368 | BOOST_TEST(all_tests_passed); |
369 | if (all_tests_passed) |
370 | { |
371 | std::cout << graph_name << " passed all tests for n = " << num_v << '.' |
372 | << std::endl; |
373 | } |
374 | } |
375 | |
376 | int main(int, char*[]) |
377 | { |
378 | |
379 | matching_test< undirected_graph >(num_v: 10, graph_name: "adjacency_list (using vectors)" ); |
380 | matching_test< undirected_list_graph >(num_v: 10, graph_name: "adjacency_list (using lists)" ); |
381 | matching_test< undirected_adjacency_matrix_graph >(num_v: 10, graph_name: "adjacency_matrix" ); |
382 | |
383 | matching_test< undirected_graph >(num_v: 20, graph_name: "adjacency_list (using vectors)" ); |
384 | matching_test< undirected_list_graph >(num_v: 20, graph_name: "adjacency_list (using lists)" ); |
385 | matching_test< undirected_adjacency_matrix_graph >(num_v: 20, graph_name: "adjacency_matrix" ); |
386 | |
387 | matching_test< undirected_graph >(num_v: 21, graph_name: "adjacency_list (using vectors)" ); |
388 | matching_test< undirected_list_graph >(num_v: 21, graph_name: "adjacency_list (using lists)" ); |
389 | matching_test< undirected_adjacency_matrix_graph >(num_v: 21, graph_name: "adjacency_matrix" ); |
390 | |
391 | #if 0 |
392 | matching_test<undirected_graph>(50, "adjacency_list (using vectors)" ); |
393 | matching_test<undirected_list_graph>(50, "adjacency_list (using lists)" ); |
394 | matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix" ); |
395 | |
396 | matching_test<undirected_graph>(51, "adjacency_list (using vectors)" ); |
397 | matching_test<undirected_list_graph>(51, "adjacency_list (using lists)" ); |
398 | matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix" ); |
399 | #endif |
400 | |
401 | return boost::report_errors(); |
402 | } |
403 | |