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