ceph/src/boost/libs/graph/test/matching_test.cpp

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