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

   1 // Copyright (C) 2004-2006 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: Douglas Gregor
   8 //           Andrew Lumsdaine
   9
  10 #include <boost/graph/use_mpi.hpp>
  11 #include <boost/config.hpp>
  12 #include <boost/throw_exception.hpp>
  13 #include <boost/serialization/vector.hpp>
  14 #include <boost/graph/distributed/adjacency_list.hpp>
  15 #include <boost/graph/connected_components.hpp>
  16 #include <boost/graph/distributed/connected_components_parallel_search.hpp>
  17 #include <boost/graph/random.hpp>
  18 #include <boost/property_map/parallel/distributed_property_map.hpp>
  19 #include <boost/graph/distributed/mpi_process_group.hpp>
  20 #include <boost/graph/parallel/distribution.hpp>
  21 #include <boost/graph/erdos_renyi_generator.hpp>
  22 #include <boost/graph/distributed/graphviz.hpp>
  23 #include <iostream>
  24 #include <cstdlib>
  25 #include <iomanip>
  26 #include <boost/random.hpp>
  27 #include <boost/test/minimal.hpp>
  28
  29 #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
  30 #include <boost/graph/rmat_graph_generator.hpp>
  31
  32 #ifdef BOOST_NO_EXCEPTIONS
  33 void
  34 boost::throw_exception(std::exception const& ex)
  35 {
  36     std::cout << ex.what() << std::endl;
  37     abort();
  38 }
  39 #endif
  40
  41 using namespace boost;
  42 using boost::graph::distributed::mpi_process_group;
  43
  44 typedef double time_type;
  45
  46 inline time_type get_time()
  47 {
  48         return MPI_Wtime();
  49 }
  50
  51 std::string print_time(time_type t)
  52 {
  53   std::ostringstream out;
  54   out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
  55   return out.str();
  56 }
  57
  58 template<typename T>
  59 class map_lt
  60 {
  61 public:
  62   bool operator()() const { return false; }
  63   bool operator()(T x, T y) const { return (owner(x) < owner(y) || (owner(x) == owner(y) && local(x) < local(y))); }
  64 };
  65
  66 void
  67 test_distributed_connected_components(int n, double _p, bool verify, bool emit_dot_file, int seed, bool parallel_search)
  68 {
  69 //   typedef adjacency_list<listS,
  70 //                          distributedS<mpi_process_group, vecS>,
  71 //                          undirectedS> Graph;
  72
  73   typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
  74                                       distributedS<mpi_process_group> > Graph;
  75
  76   minstd_rand gen;
  77
  78   gen.seed(seed);
  79
  80   mpi_process_group pg;
  81   parallel::variant_distribution<mpi_process_group> distrib
  82     = parallel::block(pg, n);
  83
  84   minstd_rand dist_gen;
  85 #if 0
  86   if (false) {
  87     distrib = parallel::random_distribution(pg, dist_gen, n);
  88   } else if (true) {
  89     distrib = parallel::oned_block_cyclic(pg, 13);
  90   }
  91 #endif
  92
  93 //   Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
  94 //           erdos_renyi_iterator<minstd_rand, Graph>(),
  95 //           n, pg, distrib);
  96
  97   int m = int(n * n * _p/2);
  98   double a = 0.57, b = 0.19, c = 0.19, d = 0.05;
  99
 100   // Last boolean parameter makes R-MAT bidirectional
 101   Graph g(sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
 102           sorted_unique_rmat_iterator<minstd_rand, Graph>(),
 103           n, pg, distrib);
 104
 105   synchronize(g);
 106
 107   std::vector<int> local_components_vec(num_vertices(g));
 108   typedef iterator_property_map<std::vector<int>::iterator, property_map<Graph, vertex_index_t>::type> ComponentMap;
 109   ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
 110
 111   int num_components = 0;
 112
 113   time_type start = get_time();
 114   if (parallel_search) {
 115     num_components = connected_components_ps(g, component);
 116   } else {
 117     num_components = connected_components(g, component);
 118   }
 119   time_type end = get_time();
 120   if (process_id(g.process_group()) == 0)
 121     std::cerr << "Connected Components time = " << print_time(end - start) << " seconds.\n"
 122               << num_components << " components identified\n";
 123
 124   if ( verify )
 125     {
 126       if ( process_id(g.process_group()) == 0 )
 127         {
 128           component.set_max_ghost_cells(0);
 129           for (int i = 0; i < n; ++i)
 130             get(component, vertex(i, g));
 131           synchronize(component);
 132
 133           // Check against the sequential version
 134           typedef adjacency_list<listS,
 135             vecS,
 136             undirectedS,
 137             // Vertex properties
 138             no_property,
 139             // Edge properties
 140             no_property > Graph2;
 141
 142           gen.seed(seed);
 143
 144 //        Graph2 g2(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, _p/2),
 145 //                  erdos_renyi_iterator<minstd_rand, Graph>(),
 146 //                  n);
 147
 148           Graph2 g2( sorted_unique_rmat_iterator<minstd_rand, Graph>(gen, n, m, a, b, c, d, true),
 149                      sorted_unique_rmat_iterator<minstd_rand, Graph>(),
 150                      n);
 151
 152           std::vector<int> component2 (n);
 153           int tmp;
 154           tmp = connected_components(g2, make_iterator_property_map(component2.begin(), get(vertex_index, g2)));
 155           std::cerr << "Verifier found " << tmp << " components" << std::endl;
 156
 157           // Make sure components and component2 match
 158           std::map<int, int> c2c;
 159           int i;
 160           // This fails if there are more components in 'component' than
 161           // 'component2' because multiple components in 'component' may
 162           // legitimately map to the same component number in 'component2'.
 163           // We can either test the mapping in the opposite direction or
 164           // just assert that the numbers of components found by both
 165           // algorithms is the same
 166           for ( i = 0; i < n; i++ )
 167             if ( c2c.find( get(component, vertex(i, g)) ) == c2c.end() )
 168               c2c[get(component, vertex(i, g))] = component2[i];
 169             else
 170               if ( c2c[get(component, vertex(i, g))] != component2[i] )
 171                 break;
 172
 173           if ( i < n || num_components != tmp) {
 174             printf("Unable to verify CC result...\n");
 175           } else
 176             printf("Passed verification... %i connected components\n",
 177                    (int)c2c.size());
 178         }
 179       else
 180         {
 181           synchronize(component);
 182         }
 183       if ( emit_dot_file )
 184         write_graphviz("cc.dot", g, paint_by_number(component));
 185     }
 186 }
 187
 188 int test_main(int argc, char* argv[])
 189 {
 190   mpi::environment env(argc, argv);
 191
 192   if ( argc < 6 ) {
 193     test_distributed_connected_components(10000, 0.001, true, false, 1, false);
 194     test_distributed_connected_components(10000, 0.001, true, false, 1, true);
 195   }
 196   else
 197     test_distributed_connected_components
 198       (atoi(argv[1]), atof(argv[2]),
 199        argv[3]==std::string("true"), argv[4]==std::string("true"),
 200        argc == 6? 1 : atoi(argv[6]),
 201        argv[5]==std::string("true"));
 202
 203   return 0;
 204 }