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

   1 // Copyright (C) 2007  Douglas Gregor
   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 #include <boost/graph/use_mpi.hpp>
   8 #include <boost/config.hpp>
   9 #include <boost/throw_exception.hpp>
  10 #include <boost/graph/distributed/adjacency_list.hpp>
  11 #include <boost/graph/distributed/mpi_process_group.hpp>
  12 #include <boost/core/lightweight_test.hpp>
  13 #include <boost/random/linear_congruential.hpp>
  14 #include <boost/graph/erdos_renyi_generator.hpp>
  15 #include <boost/lexical_cast.hpp>
  16 #include <ctime>
  17
  18 using namespace boost;
  19 using boost::graph::distributed::mpi_process_group;
  20
  21 #ifdef BOOST_NO_EXCEPTIONS
  22 void
  23 boost::throw_exception(std::exception const& ex)
  24 {
  25     std::cout << ex.what() << std::endl;
  26     abort();
  27 }
  28 #endif
  29
  30
  31 int main(int argc, char** argv)
  32 {
  33   boost::mpi::environment env(argc, argv);
  34
  35   int n = 10000;
  36   double p = 3e-3;
  37   int seed = std::time(0);
  38   int immediate_response_percent = 10;
  39
  40   if (argc > 1) n = lexical_cast<int>(argv[1]);
  41   if (argc > 2) p = lexical_cast<double>(argv[2]);
  42   if (argc > 3) seed = lexical_cast<int>(argv[3]);
  43
  44   typedef adjacency_list<listS,
  45                          distributedS<mpi_process_group, vecS>,
  46                          bidirectionalS> Graph;
  47
  48   mpi_process_group pg;
  49   int rank = process_id(pg);
  50   int numprocs = num_processes(pg);
  51   bool i_am_root = rank == 0;
  52
  53   // broadcast the seed
  54   broadcast(pg, seed, 0);
  55
  56   // Random number generator
  57   minstd_rand gen;
  58   minstd_rand require_response_gen;
  59
  60   if (i_am_root) {
  61     std::cout << "n = " << n << ", p = " << p << ", seed = " << seed
  62               << "\nBuilding graph with the iterator constructor... ";
  63     std::cout.flush();
  64   }
  65
  66   // Build a graph using the iterator constructor, where each of the
  67   // processors has exactly the same information.
  68   gen.seed(seed);
  69   Graph g1(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
  70            erdos_renyi_iterator<minstd_rand, Graph>(),
  71            n, pg, Graph::graph_property_type());
  72   // NGE: Grrr, the default graph property is needed to resolve an
  73   //      ambiguous overload in the adjaceny list constructor
  74
  75   // Build another, identical graph using add_edge
  76   if (i_am_root) {
  77     std::cout << "done.\nBuilding graph with add_edge from the root...";
  78     std::cout.flush();
  79   }
  80
  81   gen.seed(seed);
  82   require_response_gen.seed(1);
  83   Graph g2(n, pg);
  84   if (i_am_root) {
  85     // The root will add all of the edges, some percentage of which
  86     // will require an immediate response from the owner of the edge.
  87     for (erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p), last;
  88          first != last; ++first) {
  89       Graph::lazy_add_edge lazy
  90         = add_edge(vertex(first->first, g2), vertex(first->second, g2), g2);
  91
  92       if ((int)require_response_gen() % 100 < immediate_response_percent) {
  93         // Send out-of-band to require a response
  94         std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
  95         BOOST_TEST(source(result.first, g2) == vertex(first->first, g2));
  96         BOOST_TEST(target(result.first, g2) == vertex(first->second, g2));
  97       }
  98     }
  99   }
 100
 101   if (i_am_root) {
 102     std::cout << "synchronizing...";
 103     std::cout.flush();
 104   }
 105
 106   synchronize(g2);
 107
 108   // Verify that the two graphs are indeed identical.
 109   if (i_am_root) {
 110     std::cout << "done.\nVerifying graphs...";
 111     std::cout.flush();
 112   }
 113
 114   // Check the number of vertices
 115   if (num_vertices(g1) != num_vertices(g2)) {
 116     std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
 117               << " vertices, g2 has " << num_vertices(g2) << " vertices.\n";
 118     communicator(pg).abort(-1);
 119   }
 120
 121   // Check the number of edges
 122   if (num_edges(g1) != num_edges(g2)) {
 123     std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
 124               << " edges, g2 has " << num_edges(g2) << " edges.\n";
 125     communicator(pg).abort(-1);
 126   }
 127
 128   // Check the in-degree and out-degree of each vertex
 129   graph_traits<Graph>::vertex_iterator vfirst1, vlast1, vfirst2, vlast2;
 130   boost::tie(vfirst1, vlast1) = vertices(g1);
 131   boost::tie(vfirst2, vlast2) = vertices(g2);
 132   for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
 133     if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g2)) {
 134       std::cerr << g1.processor() << ": out-degree mismatch ("
 135                 << out_degree(*vfirst1, g1) << " vs. "
 136                 << out_degree(*vfirst2, g2) << ").\n";
 137       communicator(pg).abort(-1);
 138     }
 139
 140     if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g2)) {
 141       std::cerr << g1.processor() << ": in-degree mismatch ("
 142                 << in_degree(*vfirst1, g1) << " vs. "
 143                 << in_degree(*vfirst2, g2) << ").\n";
 144       communicator(pg).abort(-1);
 145     }
 146   }
 147
 148   // TODO: Check the actual edge targets
 149
 150   // Build another, identical graph using add_edge
 151   if (i_am_root) {
 152     std::cout << "done.\nBuilding graph with add_edge from everywhere...";
 153     std::cout.flush();
 154   }
 155
 156   gen.seed(seed);
 157   require_response_gen.seed(1);
 158   Graph g3(n, pg);
 159
 160   {
 161     // Each processor will take a chunk of incoming edges and add
 162     // them. Some percentage of the edge additions will require an
 163     // immediate response from the owner of the edge. This should
 164     // create a lot of traffic when building the graph, but should
 165     // produce a graph identical to the other graphs.
 166     typedef graph_traits<Graph>::edges_size_type edges_size_type;
 167
 168     erdos_renyi_iterator<minstd_rand, Graph> first(gen, n, p);
 169     edges_size_type chunk_size = edges_size_type(p*n*n)/numprocs;
 170     edges_size_type start = chunk_size * rank;
 171     edges_size_type remaining_edges =
 172       (rank < numprocs - 1? chunk_size
 173        : edges_size_type(p*n*n) - start);
 174
 175     // Spin the generator to the first edge we're responsible for
 176     for (; start; ++first, --start) ;
 177
 178     for (; remaining_edges; --remaining_edges, ++first) {
 179       Graph::lazy_add_edge lazy
 180         = add_edge(vertex(first->first, g3), vertex(first->second, g3), g3);
 181
 182       if ((int)require_response_gen() % 100 < immediate_response_percent) {
 183         // Send out-of-band to require a response
 184         std::pair<graph_traits<Graph>::edge_descriptor, bool> result(lazy);
 185         BOOST_TEST(source(result.first, g3) == vertex(first->first, g3));
 186         BOOST_TEST(target(result.first, g3) == vertex(first->second, g3));
 187       }
 188     }
 189   }
 190
 191   if (i_am_root) {
 192     std::cout << "synchronizing...";
 193     std::cout.flush();
 194   }
 195
 196   synchronize(g3);
 197
 198   // Verify that the two graphs are indeed identical.
 199   if (i_am_root) {
 200     std::cout << "done.\nVerifying graphs...";
 201     std::cout.flush();
 202   }
 203
 204   // Check the number of vertices
 205   if (num_vertices(g1) != num_vertices(g3)) {
 206     std::cerr << g1.processor() << ": g1 has " << num_vertices(g1)
 207               << " vertices, g3 has " << num_vertices(g3) << " vertices.\n";
 208     communicator(pg).abort(-1);
 209   }
 210
 211   // Check the number of edges
 212   if (num_edges(g1) != num_edges(g3)) {
 213     std::cerr << g1.processor() << ": g1 has " << num_edges(g1)
 214               << " edges, g3 has " << num_edges(g3) << " edges.\n";
 215     communicator(pg).abort(-1);
 216   }
 217
 218   // Check the in-degree and out-degree of each vertex
 219   boost::tie(vfirst1, vlast1) = vertices(g1);
 220   boost::tie(vfirst2, vlast2) = vertices(g3);
 221   for(; vfirst1 != vlast1 && vfirst2 != vlast2; ++vfirst1, ++vfirst2) {
 222     if (out_degree(*vfirst1, g1) != out_degree(*vfirst2, g3)) {
 223       std::cerr << g1.processor() << ": out-degree mismatch ("
 224                 << out_degree(*vfirst1, g1) << " vs. "
 225                 << out_degree(*vfirst2, g3) << ").\n";
 226       communicator(pg).abort(-1);
 227     }
 228
 229     if (in_degree(*vfirst1, g1) != in_degree(*vfirst2, g3)) {
 230       std::cerr << g1.processor() << ": in-degree mismatch ("
 231                 << in_degree(*vfirst1, g1) << " vs. "
 232                 << in_degree(*vfirst2, g3) << ").\n";
 233       communicator(pg).abort(-1);
 234     }
 235   }
 236
 237   // TODO: Check the actual edge targets
 238
 239   if (i_am_root) {
 240     std::cout << "done.\n";
 241     std::cout.flush();
 242   }
 243
 244   return boost::report_errors();
 245 }