1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/matching_test.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,380 @@
1.4 +//=======================================================================
1.5 +// Copyright (c) 2005 Aaron Windsor
1.6 +//
1.7 +// Distributed under the Boost Software License, Version 1.0.
1.8 +// (See accompanying file LICENSE_1_0.txt or copy at
1.9 +// http://www.boost.org/LICENSE_1_0.txt)
1.10 +//
1.11 +//=======================================================================
1.12 +
1.13 +/*
1.14 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.15 +*/
1.16 +
1.17 +#include <boost/graph/max_cardinality_matching.hpp>
1.18 +
1.19 +#include <iostream> // for std::cout
1.20 +#include <boost/vector_property_map.hpp>
1.21 +#include <boost/graph/adjacency_list.hpp>
1.22 +#include <boost/graph/adjacency_matrix.hpp>
1.23 +#include <boost/graph/random.hpp>
1.24 +#include <ctime>
1.25 +#include <boost/random.hpp>
1.26 +#include <boost/test/minimal.hpp>
1.27 +#ifdef __SYMBIAN32__
1.28 +#include "std_log_result.h"
1.29 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.30 +#endif
1.31 +using namespace boost;
1.32 +
1.33 +typedef adjacency_list<vecS,
1.34 + vecS,
1.35 + undirectedS,
1.36 + property<vertex_index_t, int> > undirected_graph;
1.37 +
1.38 +typedef adjacency_list<listS,
1.39 + listS,
1.40 + undirectedS,
1.41 + property<vertex_index_t, int> > undirected_list_graph;
1.42 +
1.43 +typedef adjacency_matrix<undirectedS,
1.44 + property<vertex_index_t,int> > undirected_adjacency_matrix_graph;
1.45 +
1.46 +
1.47 +template <typename Graph>
1.48 +struct vertex_index_installer
1.49 +{
1.50 + static void install(Graph& g) {}
1.51 +};
1.52 +
1.53 +
1.54 +template <>
1.55 +struct vertex_index_installer<undirected_list_graph>
1.56 +{
1.57 + static void install(undirected_list_graph& g)
1.58 + {
1.59 + typedef graph_traits<undirected_list_graph>::vertex_iterator vertex_iterator_t;
1.60 + typedef graph_traits<undirected_list_graph>::vertices_size_type v_size_t;
1.61 +
1.62 + vertex_iterator_t vi, vi_end;
1.63 + v_size_t i = 0;
1.64 + for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
1.65 + put(vertex_index, g, *vi, i);
1.66 + }
1.67 +};
1.68 +
1.69 +
1.70 +
1.71 +template <typename Graph>
1.72 +void complete_graph(Graph& g, int n)
1.73 +{
1.74 + //creates the complete graph on n vertices
1.75 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
1.76 +
1.77 + g = Graph(n);
1.78 + vertex_iterator_t vi, vi_end, wi;
1.79 + tie(vi,vi_end) = vertices(g);
1.80 + for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1.81 + {
1.82 + wi = vi;
1.83 + ++wi;
1.84 + for(; wi != vi_end; ++wi)
1.85 + add_edge(*vi,*wi,g);
1.86 + }
1.87 +}
1.88 +
1.89 +
1.90 +
1.91 +template <typename Graph>
1.92 +void gabows_graph(Graph& g, int n)
1.93 +{
1.94 + //creates a graph with 2n vertices, consisting of the complete graph
1.95 + //on n vertices plus n vertices of degree one, each adjacent to one
1.96 + //vertex in the complete graph. without any initial matching, this
1.97 + //graph forces edmonds' algorithm into worst-case behavior.
1.98 +
1.99 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
1.100 +
1.101 + g = Graph(2* n);
1.102 +
1.103 + vertex_iterator_t vi, vi_end, ui, ui_end, halfway;
1.104 +
1.105 + tie(ui,ui_end) = vertices(g);
1.106 +
1.107 + halfway = ui;
1.108 + for(int i = 0; i < n; ++i)
1.109 + ++halfway;
1.110 +
1.111 +
1.112 + while(ui != halfway)
1.113 + {
1.114 + vi = ui;
1.115 + ++vi;
1.116 + while (vi != halfway)
1.117 + {
1.118 + add_edge(*ui,*vi,g);
1.119 + ++vi;
1.120 + }
1.121 + ++ui;
1.122 + }
1.123 +
1.124 + tie(ui,ui_end) = vertices(g);
1.125 +
1.126 + while(halfway != ui_end)
1.127 + {
1.128 + add_edge(*ui, *halfway, g);
1.129 + ++ui;
1.130 + ++halfway;
1.131 + }
1.132 +
1.133 +}
1.134 +
1.135 +
1.136 +
1.137 +template <typename Graph>
1.138 +void matching_test(std::size_t num_v, const std::string& graph_name)
1.139 +{
1.140 + typedef typename property_map<Graph,vertex_index_t>::type vertex_index_map_t;
1.141 + typedef vector_property_map< typename graph_traits<Graph>::vertex_descriptor, vertex_index_map_t > mate_t;
1.142 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
1.143 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
1.144 + typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
1.145 +
1.146 + const std::size_t double_num_v = num_v * 2;
1.147 +
1.148 + bool all_tests_passed = true;
1.149 +
1.150 + //form the complete graph on 2*n vertices; the maximum cardinality matching, greedy matching,
1.151 + //and extra greedy matching should all be the same - a matching of size n.
1.152 +
1.153 + Graph g(double_num_v);
1.154 + complete_graph(g,double_num_v);
1.155 +
1.156 + vertex_index_installer<Graph>::install(g);
1.157 +
1.158 + mate_t edmonds_mate(double_num_v);
1.159 + mate_t greedy_mate(double_num_v);
1.160 + mate_t extra_greedy_mate(double_num_v);
1.161 +
1.162 + //find a maximum cardinality matching using edmonds' blossom-shrinking algorithm, starting
1.163 + //with an empty matching.
1.164 + bool edmonds_result =
1.165 + matching < Graph, mate_t, vertex_index_map_t,
1.166 + edmonds_augmenting_path_finder, empty_matching, maximum_cardinality_matching_verifier>
1.167 + (g,edmonds_mate, get(vertex_index,g));
1.168 +
1.169 + BOOST_CHECK (edmonds_result);
1.170 + if (!edmonds_result)
1.171 + {
1.172 + std::cout << "Verifier reporting a problem finding a perfect matching on" << std::endl
1.173 + << "the complete graph using " << graph_name << std::endl;
1.174 + all_tests_passed = false;
1.175 + }
1.176 +
1.177 + //find a greedy matching
1.178 + bool greedy_result =
1.179 + matching<Graph, mate_t, vertex_index_map_t,
1.180 + no_augmenting_path_finder, greedy_matching, maximum_cardinality_matching_verifier>
1.181 + (g,greedy_mate, get(vertex_index,g));
1.182 +
1.183 + BOOST_CHECK (greedy_result);
1.184 + if (!greedy_result)
1.185 + {
1.186 + std::cout << "Verifier reporting a problem finding a greedy matching on" << std::endl
1.187 + << "the complete graph using " << graph_name << std::endl;
1.188 + all_tests_passed = false;
1.189 + }
1.190 +
1.191 + //find an extra greedy matching
1.192 + bool extra_greedy_result =
1.193 + matching<Graph, mate_t, vertex_index_map_t,
1.194 + no_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
1.195 + (g,extra_greedy_mate,get(vertex_index,g));
1.196 +
1.197 + BOOST_CHECK (extra_greedy_result);
1.198 + if (!extra_greedy_result)
1.199 + {
1.200 + std::cout << "Verifier reporting a problem finding an extra greedy matching on" << std::endl
1.201 + << "the complete graph using " << graph_name << std::endl;
1.202 + all_tests_passed = false;
1.203 + }
1.204 +
1.205 + //as a sanity check, make sure that each of the matchings returned is a valid matching and has
1.206 + //1000 edges.
1.207 +
1.208 + bool edmonds_sanity_check =
1.209 + is_a_matching(g,edmonds_mate) && matching_size(g,edmonds_mate) == num_v;
1.210 +
1.211 + BOOST_CHECK (edmonds_sanity_check);
1.212 + if (edmonds_result && !edmonds_sanity_check)
1.213 + {
1.214 + std::cout << "Verifier okayed edmonds' algorithm on the complete graph, but" << std::endl
1.215 + << "the matching returned either wasn't a valid matching or wasn't" << std::endl
1.216 + << "actually a maximum cardinality matching." << std::endl;
1.217 + all_tests_passed = false;
1.218 + }
1.219 +
1.220 + bool greedy_sanity_check =
1.221 + is_a_matching(g,greedy_mate) && matching_size(g,greedy_mate) == num_v;
1.222 +
1.223 + BOOST_CHECK (greedy_sanity_check);
1.224 + if (greedy_result && !greedy_sanity_check)
1.225 + {
1.226 + std::cout << "Verifier okayed greedy algorithm on the complete graph, but" << std::endl
1.227 + << "the matching returned either wasn't a valid matching or wasn't" << std::endl
1.228 + << "actually a maximum cardinality matching." << std::endl;
1.229 + all_tests_passed = false;
1.230 + }
1.231 +
1.232 + bool extra_greedy_sanity_check =
1.233 + is_a_matching(g,extra_greedy_mate) && matching_size(g,extra_greedy_mate) == num_v;
1.234 +
1.235 + BOOST_CHECK (extra_greedy_sanity_check);
1.236 + if (extra_greedy_result && !extra_greedy_sanity_check)
1.237 + {
1.238 + std::cout << "Verifier okayed extra greedy algorithm on the complete graph, but" << std::endl
1.239 + << "the matching returned either wasn't a valid matching or wasn't" << std::endl
1.240 + << "actually a maximum cardinality matching." << std::endl;
1.241 + all_tests_passed = false;
1.242 + }
1.243 +
1.244 + //Now remove an edge from the edmonds_mate matching.
1.245 + vertex_iterator_t vi,vi_end;
1.246 + for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1.247 + if (edmonds_mate[*vi] != graph_traits<Graph>::null_vertex())
1.248 + break;
1.249 +
1.250 + edmonds_mate[edmonds_mate[*vi]] = graph_traits<Graph>::null_vertex();
1.251 + edmonds_mate[*vi] = graph_traits<Graph>::null_vertex();
1.252 +
1.253 + //...and run the matching verifier - it should tell us that the matching isn't
1.254 + //a maximum matching.
1.255 + bool modified_edmonds_verification_result =
1.256 + maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(g,edmonds_mate,get(vertex_index,g));
1.257 +
1.258 + BOOST_CHECK (!modified_edmonds_verification_result);
1.259 + if (modified_edmonds_verification_result)
1.260 + {
1.261 + std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
1.262 + all_tests_passed = false;
1.263 + }
1.264 +
1.265 + Graph h(double_num_v);
1.266 + gabows_graph(h,num_v);
1.267 +
1.268 + vertex_index_installer<Graph>::install(h);
1.269 +
1.270 + //gabow's graph always has a perfect matching. it's also a good example of why
1.271 + //one should initialize with the extra_greedy_matching in most cases.
1.272 +
1.273 + mate_t gabow_mate(double_num_v);
1.274 +
1.275 + bool gabows_graph_result = checked_edmonds_maximum_cardinality_matching(h,gabow_mate);
1.276 +
1.277 + BOOST_CHECK (gabows_graph_result);
1.278 + if (!gabows_graph_result)
1.279 + {
1.280 + std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
1.281 + << " Verifier reporting a maximum cardinality matching not found." << std::endl;
1.282 + all_tests_passed = false;
1.283 + }
1.284 +
1.285 + BOOST_CHECK (matching_size(h,gabow_mate) == num_v);
1.286 + if (gabows_graph_result && matching_size(h,gabow_mate) != num_v)
1.287 + {
1.288 + std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
1.289 + << " Verifier reported a maximum cardinality matching found," << std::endl
1.290 + << " but matching size is " << matching_size(h,gabow_mate)
1.291 + << " when it should be " << num_v << std::endl;
1.292 + all_tests_passed = false;
1.293 + }
1.294 +
1.295 + Graph j(double_num_v);
1.296 + vertex_index_installer<Graph>::install(j);
1.297 +
1.298 + typedef boost::mt19937 base_generator_type;
1.299 + base_generator_type generator(static_cast<unsigned int>(std::time(0)));
1.300 + boost::uniform_int<> distribution(0, double_num_v-1);
1.301 + boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution);
1.302 +
1.303 + std::size_t num_edges = 0;
1.304 + bool success;
1.305 +
1.306 + while (num_edges < 4*double_num_v)
1.307 + {
1.308 + vertex_descriptor_t u = random_vertex(j,rand_num);
1.309 + vertex_descriptor_t v = random_vertex(j,rand_num);
1.310 + if (u != v)
1.311 + {
1.312 + tie(tuples::ignore, success) = add_edge(u, v, j);
1.313 + if (success)
1.314 + num_edges++;
1.315 + }
1.316 + }
1.317 +
1.318 + mate_t random_mate(double_num_v);
1.319 + bool random_graph_result = checked_edmonds_maximum_cardinality_matching(j,random_mate);
1.320 +
1.321 + BOOST_CHECK(random_graph_result);
1.322 + if (!random_graph_result)
1.323 + {
1.324 + std::cout << "Matching in random graph not maximum for " << graph_name << std::endl;
1.325 + all_tests_passed = false;
1.326 + }
1.327 +
1.328 + //Now remove an edge from the random_mate matching.
1.329 + for(tie(vi,vi_end) = vertices(j); vi != vi_end; ++vi)
1.330 + if (random_mate[*vi] != graph_traits<Graph>::null_vertex())
1.331 + break;
1.332 +
1.333 + random_mate[random_mate[*vi]] = graph_traits<Graph>::null_vertex();
1.334 + random_mate[*vi] = graph_traits<Graph>::null_vertex();
1.335 +
1.336 + //...and run the matching verifier - it should tell us that the matching isn't
1.337 + //a maximum matching.
1.338 + bool modified_random_verification_result =
1.339 + maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(j,random_mate,get(vertex_index,j));
1.340 +
1.341 + BOOST_CHECK(!modified_random_verification_result);
1.342 + if (modified_random_verification_result)
1.343 + {
1.344 + std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
1.345 + all_tests_passed = false;
1.346 + }
1.347 +
1.348 + BOOST_CHECK(all_tests_passed);
1.349 + if (all_tests_passed)
1.350 + {
1.351 + std::cout << graph_name << " passed all tests for n = " << num_v << '.' << std::endl;
1.352 + }
1.353 +
1.354 +}
1.355 +
1.356 +
1.357 +
1.358 +
1.359 +int test_main(int argc, char* argv[])
1.360 +{
1.361 +
1.362 + matching_test<undirected_graph>(10, "adjacency_list (using vectors)");
1.363 + matching_test<undirected_list_graph>(10, "adjacency_list (using lists)");
1.364 + matching_test<undirected_adjacency_matrix_graph>(10, "adjacency_matrix");
1.365 +
1.366 + matching_test<undirected_graph>(50, "adjacency_list (using vectors)");
1.367 + matching_test<undirected_list_graph>(50, "adjacency_list (using lists)");
1.368 + matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix");
1.369 +
1.370 + matching_test<undirected_graph>(51, "adjacency_list (using vectors)");
1.371 + matching_test<undirected_list_graph>(51, "adjacency_list (using lists)");
1.372 + matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix");
1.373 +
1.374 +#ifdef __SYMBIAN32__
1.375 +std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.376 +
1.377 + testResultXml("matching_test");
1.378 + close_log_file();
1.379 +#endif
1.380 + return 0;
1.381 +}
1.382 +
1.383 +