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

   1 // Copyright (C) 2005, 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/lexical_cast.hpp>
  14 #include <boost/serialization/vector.hpp>
  15 #include <boost/graph/distributed/adjacency_list.hpp>
  16 #include <boost/graph/distributed/mpi_process_group.hpp>
  17 #include <boost/random/linear_congruential.hpp>
  18 #include <iostream>
  19 #include <boost/property_map/property_map_iterator.hpp>
  20 #include <boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp>
  21 #include <boost/graph/distributed/vertex_list_adaptor.hpp>
  22 #include <boost/graph/erdos_renyi_generator.hpp>
  23 #include <boost/graph/distributed/graphviz.hpp>
  24 #include <sstream>
  25 #include <string>
  26 #include <boost/graph/iteration_macros.hpp>
  27 #include <boost/test/minimal.hpp>
  28
  29 #ifdef BOOST_NO_EXCEPTIONS
  30 void
  31 boost::throw_exception(std::exception const& ex)
  32 {
  33     std::cout << ex.what() << std::endl;
  34     abort();
  35 }
  36 #endif
  37
  38 using namespace boost;
  39 using boost::graph::distributed::mpi_process_group;
  40
  41 /****************************************************************************
  42  * Edge weight generator iterator                                           *
  43  ****************************************************************************/
  44 template<typename F>
  45 class generator_iterator
  46 {
  47 public:
  48   typedef std::input_iterator_tag iterator_category;
  49   typedef typename F::result_type value_type;
  50   typedef const value_type&       reference;
  51   typedef const value_type*       pointer;
  52   typedef void                    difference_type;
  53
  54   explicit generator_iterator(const F& f = F()) : f(f) { value = this->f(); }
  55
  56   reference operator*() const  { return value; }
  57   pointer   operator->() const { return &value; }
  58
  59   generator_iterator& operator++()
  60   {
  61     value = f();
  62     return *this;
  63   }
  64
  65   generator_iterator operator++(int)
  66   {
  67     generator_iterator temp(*this);
  68     ++(*this);
  69     return temp;
  70   }
  71
  72   bool operator==(const generator_iterator& other) const
  73   { return f == other.f; }
  74
  75   bool operator!=(const generator_iterator& other) const
  76   { return !(*this == other); }
  77
  78 private:
  79   F f;
  80   value_type value;
  81 };
  82
  83 template<typename F>
  84 inline generator_iterator<F> make_generator_iterator(const F& f)
  85 { return generator_iterator<F>(f); }
  86
  87 typedef minstd_rand RandomGenerator;
  88
  89 template<typename Graph>
  90 double get_mst_weight (const Graph& g)
  91 {
  92   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
  93   typename property_map<Graph, edge_weight_t>::const_type weight
  94     = get(edge_weight, g);
  95
  96   // Boruvka then merge test
  97   std::vector<edge_descriptor> results;
  98   graph::boruvka_then_merge(make_vertex_list_adaptor(g), weight,
  99                             std::back_inserter(results));
 100   if (process_id(g.process_group()) == 0)
 101     return accumulate(make_property_map_iterator(weight, results.begin()),
 102                       make_property_map_iterator(weight, results.end()),
 103                       0.0);
 104   else
 105     return 0.0;
 106 }
 107
 108 template<typename Graph>
 109 void test_redistribution(int n, double p, int iterations, bool debug_output)
 110 {
 111   RandomGenerator gen;
 112   Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, n, p),
 113           erdos_renyi_iterator<RandomGenerator, Graph>(),
 114           make_generator_iterator(uniform_01<RandomGenerator>(gen)),
 115           n);
 116
 117   int iter = 0;
 118   mpi_process_group pg = g.process_group();
 119
 120   // Set the names of the vertices to be the global index in the
 121   // initial distribution. Then when we are debugging we'll be able to
 122   // see how vertices have moved.
 123   {
 124     typedef typename property_map<Graph, vertex_index_t>::type VertexIndexMap;
 125     typedef typename property_map<Graph, vertex_global_t>::type VertexGlobalMap;
 126     typename property_map<Graph, vertex_name_t>::type name_map
 127       = get(vertex_name, g);
 128
 129     parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
 130       global_index(g.process_group(), num_vertices(g),
 131                    get(vertex_index, g), get(vertex_global, g));
 132     BGL_FORALL_VERTICES_T(v, g, Graph)
 133       put(name_map, v, get(global_index, v));
 134   }
 135
 136   if (debug_output)
 137     write_graphviz("redist-0.dot", g,
 138                    make_label_writer(get(vertex_name, g)),
 139                    make_label_writer(get(edge_weight, g)));
 140
 141   double mst_weight = get_mst_weight(g);
 142   if (process_id(pg) == 0)
 143     std::cout << "MST weight = " << mst_weight << std::endl;
 144
 145   RandomGenerator nonsync_gen(process_id(pg) + gen());
 146   while (++iter <= iterations) {
 147     typename property_map<Graph, vertex_rank_t>::type to_processor_map =
 148       get(vertex_rank, g);
 149
 150     // Randomly assign a new distribution
 151     typename graph_traits<Graph>::vertex_iterator vi, vi_end;
 152     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 153       put(to_processor_map, *vi, gen() % num_processes(pg));
 154
 155     if (process_id(pg) == 0)
 156       std::cout << "Redistributing...";
 157     // Perform the actual redistribution
 158     g.redistribute(to_processor_map);
 159
 160     if (process_id(pg) == 0)
 161       std::cout << " done." << std::endl;
 162
 163     if (debug_output) {
 164       std::ostringstream out;
 165       out << "redist-" << iter << ".dot";
 166       write_graphviz(out.str().c_str(), g,
 167                      make_label_writer(get(vertex_name, g)),
 168                      make_label_writer(get(edge_weight, g)));
 169     }
 170
 171     // Check that the MST weight is unchanged
 172     double new_mst_weight = get_mst_weight(g);
 173     if (process_id(pg) == 0) {
 174       std::cout << "MST weight = " << new_mst_weight << std::endl;
 175       if (std::fabs(new_mst_weight - mst_weight) > 0.0001)
 176         communicator(pg).abort(-1);    }
 177   }
 178 }
 179
 180 int test_main(int argc, char** argv)
 181 {
 182   int n = 1000;
 183   double p = 3e-3;
 184   int iterations = 5;
 185   bool debug_output = false;
 186
 187   boost::mpi::environment env(argc, argv);
 188
 189   if (argc > 1) n = lexical_cast<int>(argv[1]);
 190   if (argc > 2) p = lexical_cast<double>(argv[2]);
 191   if (argc > 3) iterations = lexical_cast<int>(argv[3]);
 192   if (argc > 4) debug_output = true;
 193
 194   typedef adjacency_list<listS,
 195                          distributedS<mpi_process_group, vecS>,
 196                          undirectedS,
 197                          // Vertex properties
 198                          property<vertex_name_t, std::size_t,
 199                            property<vertex_rank_t, int> >,
 200                          // Edge properties
 201                          property<edge_weight_t, double> > UnstableUDGraph;
 202   typedef adjacency_list<listS,
 203                          distributedS<mpi_process_group, listS>,
 204                          undirectedS,
 205                          // Vertex properties
 206                          property<vertex_name_t, std::size_t,
 207                            property<vertex_rank_t, int,
 208                               property<vertex_index_t, std::size_t> > >,
 209                          // Edge properties
 210                          property<edge_weight_t, double> > StableUDGraph;
 211
 212   test_redistribution<UnstableUDGraph>(n, p, iterations, debug_output);
 213   test_redistribution<StableUDGraph>(n, p, iterations, debug_output);
 214
 215   return 0;
 216 }