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