ceph/src/boost/libs/mpi/test/graph_topology_test.cpp

   1 // Copyright (C) 2007 Trustees of Indiana University
   2
   3 // Authors: Douglas Gregor
   4 //          Andrew Lumsdaine
   5
   6 // Use, modification and distribution is subject to the Boost Software
   7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 // A test of the communicator that passes data around a ring and
  11 // verifies that the same data makes it all the way. Should test all
  12 // of the various kinds of data that can be sent (primitive types, POD
  13 // types, serializable objects, etc.)
  14 #include <boost/mpi/graph_communicator.hpp>
  15 #include <boost/mpi/communicator.hpp>
  16 #include <boost/mpi/environment.hpp>
  17 #include <boost/graph/adjacency_list.hpp>
  18 #include <boost/lexical_cast.hpp>
  19 #include <boost/graph/erdos_renyi_generator.hpp>
  20 #include <boost/random/linear_congruential.hpp>
  21 #include <boost/graph/iteration_macros.hpp>
  22 #include <boost/graph/isomorphism.hpp>
  23 #include <algorithm> // for random_shuffle
  24 #include <boost/serialization/vector.hpp>
  25 #include <boost/mpi/collectives/broadcast.hpp>
  26 #include <boost/config.hpp>
  27
  28 #define BOOST_TEST_MODULE mpi_graph_topology
  29 #include <boost/test/included/unit_test.hpp>
  30
  31 #if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
  32
  33 #include <random>
  34
  35 std::default_random_engine gen;
  36
  37 template<typename RandomIt> void random_shuffle( RandomIt first, RandomIt last )
  38 {
  39     std::shuffle( first, last, gen );
  40 }
  41
  42 #else
  43
  44 using std::random_shuffle;
  45
  46 #endif // #if defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
  47
  48
  49 using boost::mpi::communicator;
  50 using boost::mpi::graph_communicator;
  51 using namespace boost;
  52
  53 BOOST_AUTO_TEST_CASE(graph_topology)
  54 {
  55   boost::function_requires< IncidenceGraphConcept<graph_communicator> >();
  56   boost::function_requires< AdjacencyGraphConcept<graph_communicator> >();
  57   boost::function_requires< VertexListGraphConcept<graph_communicator> >();
  58   boost::function_requires< EdgeListGraphConcept<graph_communicator> >();
  59
  60   double prob = 0.1;
  61
  62   boost::mpi::environment env;
  63   communicator world;
  64
  65   // Random number generator
  66   minstd_rand gen;
  67
  68   // Build a random graph with as many vertices as there are processes
  69   typedef adjacency_list<listS, vecS, bidirectionalS> Graph;
  70   sorted_erdos_renyi_iterator<minstd_rand, Graph>
  71     first(gen, world.size(), prob), last;
  72   Graph graph(first, last, world.size());
  73
  74   // Display the original graph
  75   if (world.rank() == 0) {
  76     std::cout << "Original, random graph:\n";
  77     BGL_FORALL_VERTICES(v, graph, Graph) {
  78       BGL_FORALL_OUTEDGES(v, e, graph, Graph) {
  79         std::cout << source(e, graph) << " -> " << target(e, graph)
  80                   << std::endl;
  81       }
  82     }
  83   }
  84
  85   // Create an arbitrary mapping from vertices to integers
  86   typedef property_map<Graph, vertex_index_t>::type GraphVertexIndexMap;
  87   std::vector<int> graph_alt_index_vec(num_vertices(graph));
  88   iterator_property_map<int*, GraphVertexIndexMap>
  89     graph_alt_index(&graph_alt_index_vec[0], get(vertex_index, graph));
  90
  91   // Rank 0 will populate the alternative index vector
  92   if (world.rank() == 0) {
  93     int index = 0;
  94     BGL_FORALL_VERTICES(v, graph, Graph)
  95       put(graph_alt_index, v, index++);
  96
  97     ::random_shuffle(graph_alt_index_vec.begin(), graph_alt_index_vec.end());
  98   }
  99   broadcast(world, graph_alt_index_vec, 0);
 100
 101   // Display the original graph with the remapping
 102   if (world.rank() == 0) {
 103     std::cout << "Original, random graph with remapped vertex numbers:\n";
 104     BGL_FORALL_VERTICES(v, graph, Graph) {
 105       BGL_FORALL_OUTEDGES(v, e, graph, Graph) {
 106         std::cout << get(graph_alt_index, source(e, graph)) << " -> "
 107                   << get(graph_alt_index, target(e, graph)) << std::endl;
 108       }
 109     }
 110   }
 111
 112   // Create a communicator with a topology equivalent to the graph
 113   graph_communicator graph_comm(world, graph, graph_alt_index, false);
 114
 115   // The communicator's topology should have the same number of
 116   // vertices and edges and the original graph
 117   BOOST_CHECK((int)num_vertices(graph) == num_vertices(graph_comm));
 118   BOOST_CHECK((int)num_edges(graph) == num_edges(graph_comm));
 119
 120   // Display the communicator graph
 121   if (graph_comm.rank() == 0) {
 122     std::cout << "Communicator graph:\n";
 123     BGL_FORALL_VERTICES(v, graph_comm, graph_communicator) {
 124       BGL_FORALL_OUTEDGES(v, e, graph_comm, graph_communicator) {
 125         std::cout << source(e, graph_comm) << " -> " << target(e, graph_comm)
 126                   << std::endl;
 127       }
 128     }
 129
 130     std::cout << "Communicator graph via edges():\n";
 131     BGL_FORALL_EDGES(e, graph_comm, graph_communicator)
 132       std::cout << source(e, graph_comm) << " -> " << target(e, graph_comm)
 133                 << std::endl;
 134   }
 135   (graph_comm.barrier)();
 136
 137   // Verify the isomorphism
 138   if (graph_comm.rank() == 0)
 139     std::cout << "Verifying isomorphism..." << std::endl;
 140   BOOST_CHECK(verify_isomorphism(graph, graph_comm, graph_alt_index));
 141 }