ceph/src/boost/libs/graph_parallel/test/algorithm_performance.cpp

   1 // Copyright 2004 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Nick Edmonds
   8 //           Andrew Lumsdaine
   9
  10 // #define PBGL_ACCOUNTING
  11
  12 #include <boost/graph/use_mpi.hpp>
  13
  14 #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
  15 #include <boost/graph/distributed/adjacency_list.hpp>
  16
  17 #include <boost/graph/distributed/mpi_process_group.hpp>
  18
  19 #include <boost/test/minimal.hpp>
  20 #include <boost/random.hpp>
  21 #include <boost/property_map/parallel/distributed_property_map.hpp>
  22 #include <boost/graph/distributed/graphviz.hpp>
  23 #include <boost/graph/iteration_macros.hpp>
  24 #include <boost/graph/properties.hpp>
  25
  26 #include <boost/graph/rmat_graph_generator.hpp>
  27 #include <boost/graph/small_world_generator.hpp>
  28 #include <boost/graph/erdos_renyi_generator.hpp>
  29
  30 #include <boost/graph/distributed/connected_components.hpp>
  31 #include <boost/graph/distributed/connected_components_parallel_search.hpp>
  32 #include <boost/graph/distributed/betweenness_centrality.hpp>
  33 #include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
  34
  35 #include <time.h>
  36 #include <sys/time.h>
  37
  38 #include <iostream>
  39 #include <iomanip>
  40 #include <vector>
  41 #include <stdint.h>
  42
  43 // Edge distribution tags select a generator
  44 struct rmat_edge_distribution_tag { };
  45 struct rmat_unique_edge_distribution_tag { };
  46
  47 using namespace boost;
  48 using boost::graph::distributed::mpi_process_group;
  49
  50 /****************************************************************************
  51  * Timing
  52  ****************************************************************************/
  53 #ifndef PBGL_ACCOUNTING
  54
  55 typedef double time_type;
  56
  57 inline time_type get_time()
  58 {
  59   timeval tp;
  60   gettimeofday(&tp, 0);
  61   return tp.tv_sec + tp.tv_usec / 1000000.0;
  62 }
  63
  64 std::string print_time(time_type t)
  65 {
  66   std::ostringstream out;
  67   out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
  68   return out.str();
  69 }
  70
  71 #endif // PBGL_ACCOUNTING
  72
  73 /****************************************************************************
  74  * Edge weight generator iterator                                           *
  75  ****************************************************************************/
  76 template<typename F, typename RandomGenerator>
  77 class generator_iterator
  78 {
  79 public:
  80   typedef std::input_iterator_tag iterator_category;
  81   typedef typename F::result_type value_type;
  82   typedef const value_type&       reference;
  83   typedef const value_type*       pointer;
  84   typedef void                    difference_type;
  85
  86   explicit
  87   generator_iterator(RandomGenerator& gen, const F& f = F())
  88     : f(f), gen(&gen)
  89   {
  90     value = this->f(gen);
  91   }
  92
  93   reference operator*() const  { return value; }
  94   pointer   operator->() const { return &value; }
  95
  96   generator_iterator& operator++()
  97   {
  98     value = f(*gen);
  99     return *this;
 100   }
 101
 102   generator_iterator operator++(int)
 103   {
 104     generator_iterator temp(*this);
 105     ++(*this);
 106     return temp;
 107   }
 108
 109   bool operator==(const generator_iterator& other) const
 110   { return f == other.f; }
 111
 112   bool operator!=(const generator_iterator& other) const
 113   { return !(*this == other); }
 114
 115 private:
 116   F f;
 117   RandomGenerator* gen;
 118   value_type value;
 119 };
 120
 121 template<typename F, typename RandomGenerator>
 122 inline generator_iterator<F, RandomGenerator>
 123 make_generator_iterator( RandomGenerator& gen, const F& f)
 124 { return generator_iterator<F, RandomGenerator>(gen, f); }
 125
 126 /****************************************************************************
 127  * Edge Property                                                            *
 128  ****************************************************************************/
 129 typedef int weight_type;
 130
 131 struct WeightedEdge {
 132   WeightedEdge(weight_type weight = 0) : weight(weight) { }
 133
 134   weight_type weight;
 135
 136   template<typename Archiver>
 137   void serialize(Archiver& ar, const unsigned int /*version*/)
 138   {
 139     ar & weight;
 140   }
 141 };
 142
 143 /****************************************************************************
 144  * Algorithm Tests                                                          *
 145  ****************************************************************************/
 146 template <typename Graph>
 147 void test_directed_sequential_algorithms(const Graph& g)
 148 { }
 149
 150 template <typename Graph>
 151 void test_undirected_sequential_algorithms(const Graph& g)
 152 {
 153   std::vector<unsigned int> componentS(num_vertices(g));
 154   typedef iterator_property_map<
 155       std::vector<unsigned int>::iterator,
 156       typename property_map<Graph, vertex_index_t>::type>
 157     ComponentMap;
 158   ComponentMap component(componentS.begin(), get(vertex_index, g));
 159
 160   time_type start = get_time();
 161   unsigned int num_components = connected_components(g, component);
 162   time_type end = get_time();
 163
 164   std::cerr << "    Sequential connected Components time = "
 165             << print_time(end - start) << " seconds.\n"
 166             << "    " << num_components << " components identified\n";
 167 }
 168
 169 template <typename Graph, typename EdgeWeightMap>
 170 void test_directed_csr_only_algorithms(const Graph& g, EdgeWeightMap weight,
 171                                        typename graph_traits<Graph>::vertices_size_type num_sources,
 172                                        typename property_traits<EdgeWeightMap>::value_type C)
 173 {
 174   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 175   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
 176   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
 177   typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
 178
 179   typedef typename boost::graph::parallel::process_group_type<Graph>::type
 180     process_group_type;
 181
 182   process_group_type pg = process_group(g);
 183   typename process_group_type::process_id_type id = process_id(pg);
 184   typename process_group_type::process_size_type p = num_processes(pg);
 185
 186   vertices_size_type n = num_vertices(g);
 187   n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>());
 188
 189   edges_size_type m = num_edges(g);
 190   m = boost::parallel::all_reduce(pg, m, std::plus<edges_size_type>());
 191
 192   //
 193   // Betweenness Centrality (Approximate)
 194   //
 195   queue<vertex_descriptor> delta_stepping_vertices;
 196
 197   {
 198     // Distributed Centrality Map
 199     typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
 200     typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap;
 201
 202     std::vector<int> centralityS(num_vertices(g), 0);
 203     CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
 204
 205     // Calculate number of vertices of degree 0
 206     vertices_size_type n0 = 0;
 207     BGL_FORALL_VERTICES_T(v, g, Graph) {
 208       if (out_degree(v, g) == 0) n0++;
 209     }
 210     n0 = boost::parallel::all_reduce(pg, n0, std::plus<vertices_size_type>());
 211
 212     queue<vertex_descriptor> sources;
 213
 214     {
 215       assert(num_sources >= p);  // Don't feel like adding a special case for num_sources < p
 216
 217       minstd_rand gen;
 218       uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1);
 219       std::vector<vertex_descriptor> all_sources, local_sources;
 220       vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p));
 221       local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0);
 222
 223       while (local_vertices > 0) {
 224         vertex_iterator iter = vertices(g).first;
 225         std::advance(iter, rand_vertex(gen));
 226
 227         if (out_degree(*iter, g) != 0
 228             && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) {
 229           local_sources.push_back(*iter);
 230           --local_vertices;
 231         }
 232       }
 233       all_gather(pg, local_sources.begin(), local_sources.end(), all_sources);
 234       std::sort(all_sources.begin(), all_sources.end());
 235       for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin();
 236            iter != all_sources.end(); ++iter) {
 237         sources.push(*iter);
 238         delta_stepping_vertices.push(*iter);
 239       }
 240     }
 241
 242     // NOTE: The delta below assumes uniform edge weight distribution
 243     time_type start = get_time();
 244     brandes_betweenness_centrality(g, buffer(sources).weight_map(weight).
 245                                    centrality_map(centrality).lookahead((m / n) * (C / 2)));
 246     time_type end = get_time();
 247
 248     edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
 249
 250     if (id == 0)
 251       std::cerr << "    Betweenness Centrality Approximate (" << num_sources << " sources) = "
 252                 << print_time(end - start) << " (" << exactTEPs << " TEPs)\n";
 253   }
 254
 255   //
 256   // Delta stepping performance (to compare to SSSP inside BC
 257   //
 258   if (false) {
 259     typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
 260     typedef iterator_property_map<std::vector<int>::iterator, IndexMap> DistanceMap;
 261
 262     std::vector<int> distanceS(num_vertices(g), 0);
 263     DistanceMap distance(distanceS.begin(), get(vertex_index, g));
 264
 265     while(!delta_stepping_vertices.empty()) {
 266
 267       time_type start = get_time();
 268       delta_stepping_shortest_paths(g, delta_stepping_vertices.top(), dummy_property_map(),
 269                                     distance, weight);
 270       time_type end = get_time();
 271
 272       delta_stepping_vertices.pop();
 273       distance.reset();
 274
 275       if (id == 0)
 276         std::cerr << "    Delta-stepping shortest paths = " << print_time(end - start)
 277                   << std::endl;
 278     }
 279   }
 280
 281 }
 282
 283 template <typename Graph>
 284 void test_directed_algorithms(const Graph& g)
 285 {
 286 }
 287
 288 template <typename Graph>
 289 void test_undirected_algorithms(const Graph& g)
 290 {
 291   typedef typename boost::graph::parallel::process_group_type<Graph>::type
 292     process_group_type;
 293
 294   process_group_type pg = process_group(g);
 295   typename process_group_type::process_id_type id = process_id(pg);
 296   typename process_group_type::process_size_type p = num_processes(pg);
 297
 298
 299   // Connected Components
 300   std::vector<unsigned int> local_components_vec(num_vertices(g));
 301   typedef iterator_property_map<
 302       std::vector<unsigned int>::iterator,
 303       typename property_map<Graph, vertex_index_t>::type>
 304     ComponentMap;
 305   ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
 306
 307   int num_components;
 308
 309   time_type start = get_time();
 310   num_components = connected_components(g, component);
 311   time_type end = get_time();
 312   if (id == 0)
 313     std::cerr << "    Connected Components time = " << print_time(end - start)
 314               << " seconds.\n"
 315               << "    " << num_components << " components identified\n";
 316
 317   start = get_time();
 318   num_components = boost::graph::distributed::connected_components_ps(g, component);
 319   end = get_time();
 320   if (id == 0)
 321     std::cerr << "    Connected Components (parallel search) time = "
 322               << print_time(end - start) << " seconds.\n"
 323               << "    " << num_components << " components identified\n";
 324 }
 325
 326 /****************************************************************************
 327  * Graph Type Tests                                                         *
 328  ****************************************************************************/
 329
 330 // TODO: Re-seed PRNG before sequential tests to get the same graph as the
 331 // distributed case?
 332
 333 //
 334 // Compressed Sparse Row
 335 //
 336
 337 // R-MAT
 338 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 339 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 340               bool sequential_tests, size_t N, size_t M, size_t C,
 341               double a, double b, double c, double d, size_t num_sources,
 342               rmat_edge_distribution_tag)
 343 {
 344   if (process_id(pg) == 0)
 345     std::cerr << "  R-MAT\n";
 346
 347   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
 348                                       distributedS<mpi_process_group> > Graph;
 349
 350   Graph g(sorted_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 351           sorted_rmat_iterator<RandomGenerator, Graph>(),
 352           make_generator_iterator(gen, uniform_int<int>(1, C)),
 353           N, pg, distrib);
 354
 355   test_directed_algorithms(g);
 356   test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
 357
 358   if (sequential_tests && process_id(pg) == 0) {
 359     typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
 360       seqGraph;
 361
 362     seqGraph sg(edges_are_sorted,
 363                 sorted_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 364                 sorted_rmat_iterator<RandomGenerator, seqGraph>(),
 365                 make_generator_iterator(gen, uniform_int<int>(1, C)),
 366                 N);
 367
 368     test_directed_sequential_algorithms(sg);
 369   }
 370 }
 371
 372 // R-MAT with unique edges
 373 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 374 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 375               bool sequential_tests, size_t N, size_t M, size_t C,
 376               double a, double b, double c, double d, size_t num_sources,
 377               rmat_unique_edge_distribution_tag)
 378 {
 379   if (process_id(pg) == 0)
 380     std::cerr << "  R-MAT - unique\n";
 381
 382   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
 383                                       distributedS<mpi_process_group> > Graph;
 384
 385   // Last boolean parameter makes R-MAT bidirectional
 386   Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 387           sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
 388           make_generator_iterator(gen, uniform_int<int>(1, C)),
 389           N, pg, distrib);
 390
 391   test_directed_algorithms(g);
 392   test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
 393
 394   if (sequential_tests && process_id(pg) == 0) {
 395     typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
 396       seqGraph;
 397
 398     seqGraph sg(edges_are_sorted,
 399                 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 400                 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
 401                 make_generator_iterator(gen, uniform_int<int>(1, C)),
 402                 N);
 403
 404     test_directed_sequential_algorithms(sg);
 405   }
 406 }
 407
 408 // Erdos-Renyi
 409 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 410 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 411               bool sequential_tests, size_t N, size_t M, size_t C, size_t num_sources)
 412 {
 413   if (process_id(pg) == 0)
 414     std::cerr << "  Erdos-Renyi\n";
 415
 416   double _p = static_cast<double>(M) / (N*N);
 417
 418   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
 419                                       distributedS<mpi_process_group> > Graph;
 420
 421   Graph g(sorted_erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
 422           sorted_erdos_renyi_iterator<RandomGenerator, Graph>(),
 423           make_generator_iterator(gen, uniform_int<int>(1, C)),
 424           N, pg, distrib);
 425
 426   test_directed_algorithms(g);
 427   test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
 428
 429   if (sequential_tests && process_id(pg) == 0) {
 430     typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
 431       seqGraph;
 432
 433     seqGraph sg(edges_are_sorted,
 434                 sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
 435                 sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(),
 436                 make_generator_iterator(gen, uniform_int<int>(1, C)),
 437                 N);
 438
 439     test_directed_sequential_algorithms(sg);
 440   }
 441 }
 442
 443 // Small World
 444 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 445 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 446               bool sequential_tests, size_t N, size_t M, size_t C, double p,
 447               size_t num_sources)
 448 {
 449   if (process_id(pg) == 0)
 450     std::cerr << "  Small-World\n";
 451
 452   int k = M / N;
 453
 454   typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
 455                                       distributedS<mpi_process_group> > Graph;
 456
 457   Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
 458           small_world_iterator<RandomGenerator, Graph>(),
 459           make_generator_iterator(gen, uniform_int<int>(1, C)),
 460           N, pg, distrib);
 461
 462   test_directed_algorithms(g);
 463   test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
 464
 465   if (sequential_tests && process_id(pg) == 0) {
 466     typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
 467       seqGraph;
 468
 469     seqGraph sg(edges_are_sorted,
 470                 small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
 471                 small_world_iterator<RandomGenerator, seqGraph>(),
 472                 make_generator_iterator(gen, uniform_int<int>(1, C)),
 473                 N);
 474
 475     test_directed_sequential_algorithms(sg);
 476   }
 477 }
 478
 479 //
 480 // Adjacency List
 481 //
 482
 483 // R-MAT
 484 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 485 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 486                          bool sequential_tests, size_t N, size_t M, size_t C,
 487                          double a, double b, double c, double d,
 488                          rmat_edge_distribution_tag)
 489 {
 490   if (process_id(pg) == 0)
 491     std::cerr << "R-MAT\n";
 492
 493   {
 494     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 495                            directedS, no_property, WeightedEdge> Graph;
 496
 497     Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 498             rmat_iterator<RandomGenerator, Graph>(),
 499             make_generator_iterator(gen, uniform_int<int>(1, C)),
 500             N, pg, distrib);
 501
 502     test_directed_algorithms(g);
 503   }
 504
 505   {
 506     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 507                            undirectedS, no_property, WeightedEdge> Graph;
 508
 509     Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 510             rmat_iterator<RandomGenerator, Graph>(),
 511             make_generator_iterator(gen, uniform_int<int>(1, C)),
 512             N, pg, distrib);
 513
 514     test_undirected_algorithms(g);
 515   }
 516
 517   if (sequential_tests && process_id(pg) == 0) {
 518     {
 519       typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
 520         seqGraph;
 521
 522       seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 523                   rmat_iterator<RandomGenerator, seqGraph>(),
 524                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 525                   N);
 526
 527       test_directed_sequential_algorithms(sg);
 528     }
 529
 530     {
 531       typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
 532         seqGraph;
 533
 534       seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 535                   rmat_iterator<RandomGenerator, seqGraph>(),
 536                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 537                   N);
 538
 539       test_undirected_sequential_algorithms(sg);
 540     }
 541   }
 542 }
 543
 544 // R-MAT with unique edges
 545 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 546 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 547                          bool sequential_tests, size_t N, size_t M, size_t C,
 548                          double a, double b, double c, double d,
 549                          rmat_unique_edge_distribution_tag)
 550 {
 551   if (process_id(pg) == 0)
 552     std::cerr << "  R-MAT - unique\n";
 553
 554   {
 555     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 556                            directedS, no_property, WeightedEdge> Graph;
 557
 558     Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 559             sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
 560             make_generator_iterator(gen, uniform_int<int>(1, C)),
 561             N, pg, distrib);
 562
 563     test_directed_algorithms(g);
 564   }
 565
 566   {
 567     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 568                            undirectedS, no_property, WeightedEdge> Graph;
 569
 570     Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
 571             sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
 572             make_generator_iterator(gen, uniform_int<int>(1, C)),
 573             N, pg, distrib);
 574
 575     test_undirected_algorithms(g);
 576   }
 577
 578   if (sequential_tests && process_id(pg) == 0) {
 579     {
 580       typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
 581         seqGraph;
 582
 583       seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 584                   sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
 585                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 586                   N);
 587
 588       test_directed_sequential_algorithms(sg);
 589     }
 590
 591     {
 592       typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
 593         seqGraph;
 594
 595       seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
 596                   sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
 597                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 598                   N);
 599
 600       test_undirected_sequential_algorithms(sg);
 601     }
 602   }
 603 }
 604
 605 // Erdos-Renyi
 606 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 607 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 608                          bool sequential_tests, size_t N, size_t M, size_t C)
 609 {
 610   if (process_id(pg) == 0)
 611     std::cerr << "  Erdos-Renyi\n";
 612
 613   double _p = static_cast<double>(M) / N*N;
 614
 615   {
 616     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 617                            directedS, no_property, WeightedEdge> Graph;
 618
 619     Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
 620             erdos_renyi_iterator<RandomGenerator, Graph>(),
 621             make_generator_iterator(gen, uniform_int<int>(1, C)),
 622             N, pg, distrib);
 623
 624     test_directed_algorithms(g);
 625   }
 626
 627   {
 628     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 629                            undirectedS, no_property, WeightedEdge> Graph;
 630
 631     Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
 632             erdos_renyi_iterator<RandomGenerator, Graph>(),
 633             make_generator_iterator(gen, uniform_int<int>(1, C)),
 634             N, pg, distrib);
 635
 636     test_undirected_algorithms(g);
 637   }
 638
 639   if (sequential_tests && process_id(pg) == 0) {
 640     {
 641       typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
 642         seqGraph;
 643
 644       seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
 645                   erdos_renyi_iterator<RandomGenerator, seqGraph>(),
 646                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 647                   N);
 648
 649       test_directed_sequential_algorithms(sg);
 650     }
 651
 652     {
 653       typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
 654         seqGraph;
 655
 656       seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
 657                   erdos_renyi_iterator<RandomGenerator, seqGraph>(),
 658                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 659                   N);
 660
 661       test_undirected_sequential_algorithms(sg);
 662     }
 663   }
 664 }
 665
 666 // Small World
 667 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
 668 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
 669                          bool sequential_tests, size_t N, size_t M, size_t C, double p)
 670 {
 671   if (process_id(pg) == 0)
 672     std::cerr << "  Small-World\n";
 673
 674   int k = M / N;
 675
 676   {
 677     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 678                            directedS, no_property, WeightedEdge> Graph;
 679
 680     Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
 681             small_world_iterator<RandomGenerator, Graph>(),
 682             make_generator_iterator(gen, uniform_int<int>(1, C)),
 683             N, pg, distrib);
 684
 685     test_directed_algorithms(g);
 686   }
 687
 688   {
 689     typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
 690                            undirectedS, no_property, WeightedEdge> Graph;
 691
 692     Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
 693             small_world_iterator<RandomGenerator, Graph>(),
 694             make_generator_iterator(gen, uniform_int<int>(1, C)),
 695             N, pg, distrib);
 696
 697     test_undirected_algorithms(g);
 698   }
 699
 700   if (sequential_tests && process_id(pg) == 0) {
 701     {
 702       typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
 703         seqGraph;
 704
 705       seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
 706                   small_world_iterator<RandomGenerator, seqGraph>(),
 707                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 708                   N);
 709
 710       test_directed_sequential_algorithms(sg);
 711     }
 712
 713     {
 714       typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
 715         seqGraph;
 716
 717       seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
 718                   small_world_iterator<RandomGenerator, seqGraph>(),
 719                   make_generator_iterator(gen, uniform_int<int>(1, C)),
 720                   N);
 721
 722       test_undirected_sequential_algorithms(sg);
 723     }
 724   }
 725 }
 726
 727 void usage()
 728 {
 729   std::cerr << "Algorithm Performance Test\n"
 730             << "Usage : algorithm_performance [options]\n\n"
 731             << "Options are:\n"
 732             << "\t--vertices v\t\t\tNumber of vertices in the graph\n"
 733             << "\t--edges v\t\t\tNumber of edges in the graph\n"
 734             << "\t--seed s\t\t\tSeed for synchronized random number generator\n"
 735             << "\t--max-weight miw\t\tMaximum integer edge weight\n"
 736             << "\t--rewire-probability\t\tRewire-probabitility (p) for small-world graphs\n"
 737             << "\t--dot\t\t\t\tEmit a dot file containing the graph\n"
 738             << "\t--verify\t\t\tVerify result\n"
 739             << "\t--degree-dist\t\t\tOutput degree distribution of graph\n"
 740             << "\t--sequential-graph\t\tRun sequential graph tests\n"
 741             << "\t--erdos-renyi\t\t\tRun tests on Erdos-Renyi graphs\n"
 742             << "\t--small-world\t\t\tRun tests on Small World graphs\n"
 743             << "\t--rmat\t\t\t\tRun tests on R-MAT graphs\n"
 744             << "\t--rmat-unique\t\t\tRun tests on R-MAT graphs with no duplicate edges\n"
 745             << "\t--csr <bool>\t\t\tRun tests using CSR graphs\n"
 746             << "\t--adjacency-list <bool>\t\tRun tests using Adjacency List graphs\n";
 747 }
 748
 749
 750 int test_main(int argc, char* argv[])
 751 {
 752   mpi::environment env(argc, argv);
 753
 754   rand48 gen;
 755
 756   // Default args
 757   size_t n = 100,
 758     m = 8*n,
 759     c = 100,
 760     num_sources = 32,
 761     num_headers = 16 * 1024,
 762     batch_buffer_size = 1024 * 1024;
 763   uint64_t seed = 1;
 764   bool emit_dot_file = false,
 765     verify = false,
 766     sequential_graph = false,
 767     show_degree_dist = false,
 768     erdos_renyi = false,
 769     small_world = false,
 770     rmat = false,
 771     rmat_unique = false,
 772     csr = false,
 773     adj_list = false;
 774   double p = 0.1,
 775     rmat_a = 0.5,
 776     rmat_b = 0.25,
 777     rmat_c = 0.1,
 778     rmat_d = 0.15;
 779
 780   // Parse args
 781   for (int i = 1; i < argc; ++i) {
 782     std::string arg = argv[i];
 783
 784     if (arg == "--vertices")
 785       n = boost::lexical_cast<size_t>( argv[i+1] );
 786
 787     if (arg == "--seed")
 788       seed = boost::lexical_cast<uint64_t>( argv[i+1] );
 789
 790     if (arg == "--edges")
 791       m = boost::lexical_cast<size_t>( argv[i+1] );
 792
 793     if (arg == "--max-weight")
 794       c = boost::lexical_cast<int>( argv[i+1] );
 795
 796     if (arg == "--batch-buffer-size") {
 797       batch_buffer_size = boost::lexical_cast<size_t>( argv[i+1] );
 798       num_headers = batch_buffer_size / 16;
 799       num_headers = num_headers > 0 ? num_headers : 1;
 800     }
 801
 802     if (arg == "--rewire-probability")
 803       p = boost::lexical_cast<double>( argv[i+1] );
 804
 805     if (arg == "--num-sources")
 806       num_sources = boost::lexical_cast<size_t>( argv[i + 1] );
 807
 808     if (arg == "--erdos-renyi")
 809       erdos_renyi = true;
 810
 811     if (arg == "--small-world")
 812       small_world = true;
 813
 814     if (arg == "--rmat")
 815       rmat = true;
 816
 817     if (arg == "--rmat-unique")
 818       rmat_unique = true;
 819
 820     if (arg == "--dot")
 821       emit_dot_file = true;
 822
 823     if (arg == "--verify")
 824       verify = true;
 825
 826     if (arg == "--degree-dist")
 827       show_degree_dist = true;
 828
 829     if (arg == "--sequential-graph")
 830       sequential_graph = true;
 831
 832     if (arg == "--csr")
 833       csr = std::string(argv[i+1]) == "true";
 834
 835     if (arg == "--adjacency-list")
 836       adj_list = std::string(argv[i+1]) == "true";
 837   }
 838
 839   mpi_process_group pg(num_headers, batch_buffer_size);
 840
 841   if (argc == 1) {
 842     if (process_id(pg) == 0)
 843       usage();
 844     exit(-1);
 845   }
 846
 847   gen.seed(seed);
 848
 849   parallel::variant_distribution<mpi_process_group> distrib
 850     = parallel::block(pg, n);
 851
 852   if (csr) {
 853     if (process_id(pg) == 0)
 854       std::cerr << "CSR Graph Tests\n";
 855
 856     if (erdos_renyi)
 857       test_csr(pg, gen, distrib, sequential_graph, n, m, c, num_sources);
 858     if (small_world)
 859       test_csr(pg, gen, distrib, sequential_graph, n, m, c, p, num_sources);
 860     if (rmat)
 861       test_csr(pg, gen, distrib, sequential_graph, n, m, c,
 862                rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_edge_distribution_tag());
 863     if (rmat_unique)
 864       test_csr(pg, gen, distrib, sequential_graph, n, m, c,
 865                rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_unique_edge_distribution_tag());
 866   }
 867
 868   gen.seed(seed); // DEBUG
 869
 870   if (adj_list) {
 871     if (process_id(pg) == 0)
 872       std::cerr << "Adjacency List Graph Tests\n";
 873
 874     if (erdos_renyi)
 875       test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c);
 876     if (small_world)
 877       test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, p);
 878     if (rmat)
 879       test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
 880                           rmat_a, rmat_b, rmat_c, rmat_d, rmat_edge_distribution_tag());
 881     if (rmat_unique)
 882       test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
 883                           rmat_a, rmat_b, rmat_c, rmat_d, rmat_unique_edge_distribution_tag());
 884   }
 885
 886   return 0;
 887 }