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