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 {
installvertex_index_installer43 static void install(Graph&) {}
44 };
45
46 template <> struct vertex_index_installer< undirected_list_graph >
47 {
installvertex_index_installer48 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(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
58 put(vertex_index, g, *vi, i);
59 }
60 };
61
complete_graph(Graph & g,int n)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
gabows_graph(Graph & g,int n)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 >
matching_test(std::size_t num_v,const std::string & graph_name)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 extra_greedy_mate(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 extra_greedy_result = 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 extra_greedy_sanity_check = 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(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(tuples::ignore, 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
main(int,char * [])376 int main(int, char*[])
377 {
378
379 matching_test< undirected_graph >(10, "adjacency_list (using vectors)");
380 matching_test< undirected_list_graph >(10, "adjacency_list (using lists)");
381 matching_test< undirected_adjacency_matrix_graph >(10, "adjacency_matrix");
382
383 matching_test< undirected_graph >(20, "adjacency_list (using vectors)");
384 matching_test< undirected_list_graph >(20, "adjacency_list (using lists)");
385 matching_test< undirected_adjacency_matrix_graph >(20, "adjacency_matrix");
386
387 matching_test< undirected_graph >(21, "adjacency_list (using vectors)");
388 matching_test< undirected_list_graph >(21, "adjacency_list (using lists)");
389 matching_test< undirected_adjacency_matrix_graph >(21, "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