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

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #include <boost/config.hpp>
  11
  12 #include <iostream>
  13 #include <vector>
  14 #include <set>
  15 #include <utility>
  16 #include <algorithm>
  17
  18 #define VERBOSE 0
  19
  20 #include <boost/utility.hpp>
  21 #include <boost/graph/graph_utility.hpp>
  22 #include <boost/graph/random.hpp>
  23 #include <boost/pending/indirect_cmp.hpp>
  24
  25 #include <boost/random/mersenne_twister.hpp>
  26
  27
  28 enum vertex_id_t { vertex_id = 500 };
  29 enum edge_id_t { edge_id = 501 };
  30 namespace boost {
  31   BOOST_INSTALL_PROPERTY(vertex, id);
  32   BOOST_INSTALL_PROPERTY(edge, id);
  33 }
  34
  35
  36 #include "graph_type.hpp" // this provides a typedef for Graph
  37
  38 using namespace boost;
  39
  40 /*
  41   This program tests models of the MutableGraph concept.
  42  */
  43
  44 using std::cout;
  45 using std::endl;
  46 using std::cerr;
  47 using std::find;
  48
  49
  50 template <class Graph, class Vertex, class ID>
  51 bool check_vertex_cleared(Graph& g, Vertex v, ID id)
  52 {
  53   typename graph_traits<Graph>::vertex_iterator vi, viend;
  54   for (boost::tie(vi,viend) = vertices(g); vi != viend; ++vi) {
  55     typename graph_traits<Graph>::adjacency_iterator ai, aiend, found;
  56     boost::tie(ai, aiend) = adjacent_vertices(*vi, g);
  57     boost::indirect_cmp<ID, std::equal_to<std::size_t> > cmp(id);
  58
  59 #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) && defined(__SGI_STL_PORT)
  60     // seeing internal compiler errors when using std::find_if()
  61     found = aiend;
  62     for ( ; ai != aiend; ++ai)
  63       if (cmp(*ai, v)) {
  64         found = ai;
  65         break;
  66       }
  67 #elif defined(BOOST_NO_CXX98_BINDERS)
  68     found = std::find_if(ai, aiend, std::bind(cmp,v,std::placeholders::_1));
  69 #else
  70     found = std::find_if(ai, aiend, std::bind1st(cmp,v));
  71 #endif
  72
  73     if ( found != aiend ) {
  74 #if VERBOSE
  75       std::cerr << "should not have found vertex " << id[*found] << std::endl;
  76 #endif
  77       return false;
  78     }
  79   }
  80   return true;
  81 }
  82
  83 template <class Graph, class Edge, class EdgeID>
  84 bool check_edge_added(Graph& g, Edge e,
  85                       typename graph_traits<Graph>::vertex_descriptor a,
  86                       typename graph_traits<Graph>::vertex_descriptor b,
  87                       EdgeID edge_id, std::size_t correct_id,
  88                       bool inserted)
  89 {
  90   if (! (source(e, g) == a)) {
  91 #if VERBOSE
  92     cerr << "    Failed, vertex a not source of e."<< endl;
  93 #endif
  94     return false;
  95   } else if (! (target(e, g) == b)) {
  96 #if VERBOSE
  97     cerr << "    Failed, vertex b not source of e."<< endl;
  98 #endif
  99     return false;
 100   } else if (! is_adjacent(g, a, b)) {
 101 #if VERBOSE
 102     cerr << "    Failed, not adj."<< endl;
 103 #endif
 104     return false;
 105   } else if (! in_edge_set(g,e)) {
 106 #if VERBOSE
 107     cerr << "    Failed, not in edge set."<< endl;
 108 #endif
 109     return false;
 110   } else if (inserted && edge_id[e] != correct_id) {
 111 #if VERBOSE
 112     cerr << "    Failed, invalid edge property."<< endl;
 113 #endif
 114     return false;
 115   } else if (!inserted && edge_id[e] != edge_id[edge(a, b, g).first]) {
 116 #if VERBOSE
 117     cerr << "    Failed, invalid edge property."<< endl;
 118 #endif
 119     return false;
 120   } else if (num_edges(g) != count_edges(g)) {
 121 #if VERBOSE
 122     cerr << "    Failed, invalid number of edges."<< endl;
 123 #endif
 124     return false;
 125   }
 126   return true;
 127 }
 128
 129
 130 template <class Graph>
 131 std::size_t count_edges(Graph& g)
 132 {
 133   std::size_t e = 0;
 134   typename boost::graph_traits<Graph>::edge_iterator ei,ei_end;
 135   for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
 136     ++e;
 137   return e;
 138 }
 139
 140
 141 int main(int, char* [])
 142 {
 143   int ret = 0;
 144   std::size_t N = 5, E = 0;
 145   std::size_t old_N;
 146
 147   typedef ::Graph Graph;
 148   Graph g;
 149   typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
 150   typedef boost::graph_traits<Graph>::edge_descriptor Edge;
 151
 152   int i, j;
 153   std::size_t current_vertex_id = 0;
 154   std::size_t current_edge_id = 0;
 155
 156   bool is_failed = false;
 157
 158   property_map<Graph, vertex_id_t>::type vertex_id_map = get(vertex_id, g);
 159
 160   property_map<Graph, edge_id_t>::type edge_id_map = get(edge_id, g);
 161
 162   for (std::size_t k = 0; k < N; ++k)
 163     add_vertex(current_vertex_id++, g);
 164
 165   // also need to test EdgeIterator graph constructor -JGS
 166   mt19937 gen;
 167
 168   for (j=0; j < 10; ++j) {
 169
 170     // add_edge
 171 #if VERBOSE
 172     cerr << "Testing add_edge ..." << endl;
 173 #endif
 174     for (i=0; i < 6; ++i) {
 175       Vertex a, b;
 176       a = random_vertex(g, gen);
 177       do {
 178         b = random_vertex(g, gen);
 179       } while ( a == b ); // don't do self edges
 180 #if VERBOSE
 181       cerr << "add_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] <<")" << endl;
 182 #endif
 183       Edge e;
 184       bool inserted;
 185       boost::tie(e, inserted) = add_edge(a, b, current_edge_id++, g);
 186 #if VERBOSE
 187       std::cout << "inserted: " << inserted << std::endl;
 188       std::cout << "source(e,g)" << source(e,g) << endl;
 189       std::cout << "target(e,g)" << target(e,g) << endl;
 190       std::cout << "edge_id[e] = " << edge_id_map[e] << std::endl;
 191       print_edges2(g, vertex_id_map, edge_id_map);
 192       print_graph(g, vertex_id_map);
 193       std::cout << "finished printing" << std::endl;
 194       //      print_in_edges(g, vertex_id_map);
 195 #endif
 196       if (! check_edge_added(g, e, a, b, edge_id_map,
 197                              current_edge_id - 1, inserted)) {
 198         ret = -1;
 199         break;
 200       }
 201       ++E;
 202     }
 203
 204     // remove_edge(u, v, g)
 205 #if VERBOSE
 206     cerr << "Testing remove_edge(u, v, g) ..." << endl; is_failed = false;
 207 #endif
 208     for (i = 0; i < 2; ++i) {
 209 #if VERBOSE
 210       print_edges(g, vertex_id_map);
 211 #endif
 212       Vertex a, b;
 213
 214       Edge e = random_edge(g, gen);
 215       boost::tie(a,b) = boost::incident(e, g);
 216       --E;
 217 #if VERBOSE
 218       cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
 219 #endif
 220       remove_edge(a, b, g);
 221 #if VERBOSE
 222       print_graph(g, vertex_id_map);
 223       //      print_in_edges(g, vertex_id_map);
 224       print_edges(g, vertex_id_map);
 225 #endif
 226       is_failed = is_failed || is_adjacent(g, a, b) || in_edge_set(g, a, b)
 227         || num_edges(g) != count_edges(g);
 228       if (is_failed)
 229         break;
 230     }
 231     if ( is_failed ) {
 232       ret = -1;
 233 #if VERBOSE
 234       cerr << "    Failed."<< endl;
 235 #endif
 236     } else {
 237 #if VERBOSE
 238       cerr << "           Passed."<< endl;
 239 #endif
 240     }
 241
 242     // remove_edge(e, g)
 243 #if VERBOSE
 244     cerr << "Testing remove_edge(e, g) ..." << endl; is_failed = false;
 245 #endif
 246     for (i = 0; i < 2; ++i) {
 247 #if VERBOSE
 248       print_edges(g, vertex_id_map);
 249 #endif
 250       Vertex a, b;
 251       Edge e = random_edge(g, gen);
 252       boost::tie(a,b) = boost::incident(e, g);
 253       --E;
 254 #if VERBOSE
 255       cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl;
 256 #endif
 257       graph_traits<Graph>::edges_size_type old_E = num_edges(g);
 258       remove_edge(e, g);
 259
 260 #if VERBOSE
 261       print_graph(g, vertex_id_map);
 262       //      print_in_edges(g, vertex_id_map);
 263       print_edges(g, vertex_id_map);
 264 #endif
 265
 266       is_failed = is_failed || old_E != num_edges(g) + 1
 267         || num_edges(g) != count_edges(g);
 268       if (is_failed)
 269         break;
 270     }
 271     if ( is_failed ) {
 272       ret = -1;
 273 #if VERBOSE
 274       cerr << "    Failed."<< endl;
 275 #endif
 276     } else {
 277 #if VERBOSE
 278       cerr << "           Passed."<< endl;
 279 #endif
 280     }
 281
 282     // add_vertex
 283 #if VERBOSE
 284     cerr << "Testing add_vertex ..." << endl; is_failed = false;
 285 #endif
 286     old_N = num_vertices(g);
 287     graph_traits<Graph>::vertex_descriptor vid = add_vertex(g),
 288       vidp1 = add_vertex(g);
 289     vertex_id_map[vid] = current_vertex_id++;
 290     vertex_id_map[vidp1] = current_vertex_id++;
 291
 292 #if VERBOSE
 293     print_vertices(g,vertex_id_map);
 294     print_graph(g,vertex_id_map);
 295     //    print_in_edges(g,vertex_id_map);
 296     print_edges(g,vertex_id_map);
 297 #endif
 298     // make sure the two added vertices are in the graph's vertex set
 299     {
 300       if (!in_vertex_set(g, vid)) {
 301 #if VERBOSE
 302         cerr << "   Failed, " << vertex_id_map[vid] << " not in vertices(g)" << endl;
 303 #endif
 304         ret = -1;
 305         break;
 306       }
 307       if (!in_vertex_set(g, vidp1)) {
 308 #if VERBOSE
 309         cerr << "   Failed, " << vertex_id_map[vidp1] << " not in vertices(g)" << endl;
 310 #endif
 311         ret = -1;
 312         break;
 313       }
 314     }
 315
 316     // make sure the vertices do not have any out edges yet
 317     {
 318       graph_traits<Graph>::out_edge_iterator e, e_end;
 319       boost::tie(e,e_end) = out_edges(vid,g);
 320       if (e != e_end) {
 321 #if VERBOSE
 322         cerr << "   Failed, " << vertex_id_map[vid]
 323              << " should not have any out-edges yet" << endl;
 324 #endif
 325         ret = -1;
 326         break;
 327       }
 328       boost::tie(e,e_end) = out_edges(vidp1,g);
 329       if (e != e_end) {
 330 #if VERBOSE
 331         cerr << "   Failed, " << vertex_id_map[vidp1]
 332              << " should not have any out-edges yet" << endl;
 333 #endif
 334         ret = -1;
 335         break;
 336       }
 337     }
 338
 339     // make sure the vertices do not yet appear in any of the edges
 340     {
 341       graph_traits<Graph>::edge_iterator e, e_end;
 342       for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) {
 343         if (source(*e,g) == vid || target(*e,g) == vid) {
 344 #if VERBOSE
 345           cerr << "   Failed, " << vertex_id_map[vid]
 346                << " should not have any edges" << endl;
 347 #endif
 348           ret = -1;
 349           break;
 350         }
 351         if (source(*e,g) == vidp1 || target(*e,g) == vidp1) {
 352 #if VERBOSE
 353           cerr << "   Failed, " << vertex_id_map[vidp1]
 354                << " should not have any edges" << endl;
 355 #endif
 356           ret = -1;
 357           break;
 358         }
 359       }
 360     }
 361     // Make sure num_vertices(g) has been updated
 362     N = num_vertices(g);
 363     if ( (N - 2) != old_N ) {
 364       ret = -1;
 365 #if VERBOSE
 366       cerr << "    Failed. N = " << N
 367            << " but should be " << old_N + 2 << endl;
 368 #endif
 369       break;
 370     } else {
 371 #if VERBOSE
 372       cerr << "           Passed."<< endl;
 373 #endif
 374     }
 375     // add_edge again
 376 #if VERBOSE
 377     cerr << "Testing add_edge after add_vertex ..." << endl; is_failed = false;
 378 #endif
 379
 380     for (i=0; i<2; ++i) {
 381       Vertex a = random_vertex(g, gen), b = random_vertex(g, gen);
 382       while ( a == vid ) a = random_vertex(g, gen);
 383       while ( b == vidp1 ) b = random_vertex(g, gen);
 384       Edge e;
 385       bool inserted;
 386 #if VERBOSE
 387       cerr << "add_edge(" << vertex_id_map[vid] << "," << vertex_id_map[a] <<")" << endl;
 388 #endif
 389       boost::tie(e,inserted) = add_edge(vid, a, EdgeID(current_edge_id++), g);
 390
 391       if (! check_edge_added(g, e, vid, a, edge_id_map, current_edge_id - 1,
 392                              inserted)) {
 393         ret = -1;
 394         break;
 395       }
 396
 397 #if VERBOSE
 398       cerr << "add_edge(" << vertex_id_map[b] << "," << vertex_id_map[vidp1] <<")" << endl;
 399 #endif
 400       // add_edge without plugin
 401       boost::tie(e,inserted) = add_edge(b, vidp1, g);
 402       if (inserted)
 403         edge_id_map[e] = current_edge_id;
 404       ++current_edge_id;
 405
 406       if (! check_edge_added(g, e, b, vidp1, edge_id_map,
 407                              current_edge_id - 1, inserted)) {
 408         ret = -1;
 409         break;
 410       }
 411     }
 412
 413     // clear_vertex
 414     Vertex c = random_vertex(g, gen);
 415 #if VERBOSE
 416     cerr << "Testing clear vertex ..." << endl; is_failed = false;
 417     print_graph(g, vertex_id_map);
 418     //    print_in_edges(g, vertex_id_map);
 419     cerr << "clearing vertex " << vertex_id_map[c] << endl;
 420 #endif
 421     clear_vertex(c, g);
 422 #if VERBOSE
 423     print_graph(g, vertex_id_map);
 424     //    print_in_edges(g, vertex_id_map);
 425     print_edges(g, vertex_id_map);
 426 #endif
 427     if (check_vertex_cleared(g, c, vertex_id_map) && num_edges(g) == count_edges(g)) {
 428 #if VERBOSE
 429       cerr << " Passed."<< endl;
 430 #endif
 431     } else {
 432 #if VERBOSE
 433       cerr << "**** Failed" << endl;
 434 #endif
 435       ret = -1;
 436       break;
 437     }
 438
 439 #if VERBOSE
 440     cerr << "Testing remove vertex ..." << endl; is_failed = false;
 441     cerr << "removing vertex " << vertex_id_map[c] << endl;
 442 #endif
 443
 444     old_N = num_vertices(g);
 445     remove_vertex(c, g);
 446 #if VERBOSE
 447     print_graph(g,vertex_id_map);
 448     //    print_in_edges(g,vertex_id_map);
 449     print_edges(g, vertex_id_map);
 450 #endif
 451     // can't check in_vertex_set here because the vertex_descriptor c
 452     // is no longer valid, we'll just make sure the vertex set has
 453     // one fewer vertex
 454     {
 455       graph_traits<Graph>::vertex_iterator v, v_end;
 456       boost::tie(v, v_end) = vertices(g);
 457       for (N = 0; v != v_end; ++v) ++N; // N = std::distance(v, v_end);
 458       if (N != old_N - 1) {
 459         ret = -1;
 460 #if VERBOSE
 461         cerr << "    Failed. N = " << N
 462              << " but should be " << old_N - 1 << endl;
 463 #endif
 464       }
 465     }
 466
 467     N = num_vertices(g);
 468     if (N != old_N - 1) {
 469       ret = -1;
 470 #if VERBOSE
 471       cerr << "    Failed. N = " << N
 472            << " but should be " << old_N - 1 << endl;
 473 #endif
 474     } else {
 475 #if VERBOSE
 476       cerr << "           Passed."<< endl;
 477 #endif
 478     }
 479   }
 480   if (ret == 0)
 481     std::cout << "tests passed" << std::endl;
 482
 483   return ret;
 484 }