ceph/src/boost/libs/graph_parallel/test/distributed_shortest_paths_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 #define PBGL_ACCOUNTING
  10
  11 #include <boost/graph/use_mpi.hpp>
  12 #include <boost/config.hpp>
  13 #include <boost/throw_exception.hpp>
  14 #include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
  15 #include <boost/graph/distributed/mpi_process_group.hpp>
  16 #include <boost/lexical_cast.hpp>
  17 #include <boost/graph/parallel/distribution.hpp>
  18 #include <boost/graph/erdos_renyi_generator.hpp>
  19 #include <boost/graph/distributed/adjacency_list.hpp>
  20 #include <boost/graph/graphviz.hpp>
  21 #include <boost/random.hpp>
  22 #include <boost/test/minimal.hpp>
  23 #include <boost/graph/iteration_macros.hpp>
  24
  25 #include <iostream>
  26 #include <iomanip>
  27
  28 #ifdef BOOST_NO_EXCEPTIONS
  29 void
  30 boost::throw_exception(std::exception const& ex)
  31 {
  32     std::cout << ex.what() << std::endl;
  33     abort();
  34 }
  35 #endif
  36
  37 /****************************************************************************
  38  * Timing                                                                   *
  39  ****************************************************************************/
  40 typedef double time_type;
  41
  42 inline time_type get_time()
  43 {
  44   return MPI_Wtime();
  45 }
  46
  47 std::string print_time(time_type t)
  48 {
  49   std::ostringstream out;
  50   out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
  51   return out.str();
  52 }
  53
  54 /****************************************************************************
  55  * Edge weight generator iterator                                           *
  56  ****************************************************************************/
  57 template<typename F, typename RandomGenerator>
  58 class generator_iterator
  59 {
  60 public:
  61   typedef std::input_iterator_tag iterator_category;
  62   typedef typename F::result_type value_type;
  63   typedef const value_type&       reference;
  64   typedef const value_type*       pointer;
  65   typedef void                    difference_type;
  66
  67   explicit
  68   generator_iterator(RandomGenerator& gen, const F& f = F())
  69     : f(f), gen(&gen)
  70   {
  71     value = this->f(gen);
  72   }
  73
  74   reference operator*() const  { return value; }
  75   pointer   operator->() const { return &value; }
  76
  77   generator_iterator& operator++()
  78   {
  79     value = f(*gen);
  80     return *this;
  81   }
  82
  83   generator_iterator operator++(int)
  84   {
  85     generator_iterator temp(*this);
  86     ++(*this);
  87     return temp;
  88   }
  89
  90   bool operator==(const generator_iterator& other) const
  91   { return f == other.f; }
  92
  93   bool operator!=(const generator_iterator& other) const
  94   { return !(*this == other); }
  95
  96 private:
  97   F f;
  98   RandomGenerator* gen;
  99   value_type value;
 100 };
 101
 102 template<typename F, typename RandomGenerator>
 103 inline generator_iterator<F, RandomGenerator>
 104 make_generator_iterator( RandomGenerator& gen, const F& f)
 105 { return generator_iterator<F, RandomGenerator>(gen, f); }
 106
 107 /****************************************************************************
 108  * Verification                                                             *
 109  ****************************************************************************/
 110 template <typename Graph, typename DistanceMap, typename WeightMap>
 111 void
 112 verify_shortest_paths(const Graph& g, DistanceMap distance,
 113                       const WeightMap& weight) {
 114
 115   distance.set_max_ghost_cells(0);
 116
 117   BGL_FORALL_VERTICES_T(v, g, Graph) {
 118     BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
 119       get(distance, target(e, g));
 120     }
 121   }
 122
 123   synchronize(process_group(g));
 124
 125   BGL_FORALL_VERTICES_T(v, g, Graph) {
 126     BGL_FORALL_OUTEDGES_T(v, e, g, Graph) {
 127       assert(get(distance, target(e, g)) <=
 128              get(distance, source(e, g)) + get(weight, e));
 129     }
 130   }
 131 }
 132
 133 using namespace boost;
 134 using boost::graph::distributed::mpi_process_group;
 135
 136 typedef int weight_type;
 137
 138 struct WeightedEdge {
 139   WeightedEdge(weight_type weight = 0) : weight(weight) { }
 140
 141   weight_type weight;
 142
 143   template<typename Archiver>
 144   void serialize(Archiver& ar, const unsigned int /*version*/)
 145   {
 146     ar & weight;
 147   }
 148 };
 149
 150 struct VertexProperties {
 151   VertexProperties(int d = 0)
 152     : distance(d) { }
 153
 154   int distance;
 155
 156   template<typename Archiver>
 157   void serialize(Archiver& ar, const unsigned int /*version*/)
 158   {
 159     ar & distance;
 160   }
 161 };
 162
 163 void
 164 test_distributed_shortest_paths(int n, double p, int c, int seed)
 165 {
 166   typedef adjacency_list<listS,
 167                          distributedS<mpi_process_group, vecS>,
 168                          undirectedS,
 169                          VertexProperties,
 170                          WeightedEdge> Graph;
 171
 172   typedef graph_traits<Graph>::vertices_size_type vertices_size_type;
 173
 174   // Build a random number generator
 175   minstd_rand gen;
 176   gen.seed(seed);
 177
 178   // Build a random graph
 179   Graph g(erdos_renyi_iterator<minstd_rand, Graph>(gen, n, p),
 180           erdos_renyi_iterator<minstd_rand, Graph>(),
 181           make_generator_iterator(gen, uniform_int<int>(0, c)),
 182           n);
 183
 184   uniform_int<vertices_size_type> rand_vertex(0, n);
 185
 186   graph::distributed::delta_stepping_shortest_paths(g,
 187                                                     vertex(rand_vertex(gen), g),
 188                                                     dummy_property_map(),
 189                                                     get(&VertexProperties::distance, g),
 190                                                     get(&WeightedEdge::weight, g));
 191
 192   verify_shortest_paths(g,
 193                         get(&VertexProperties::distance, g),
 194                         get(&WeightedEdge::weight, g));
 195 }
 196
 197 int test_main(int argc, char* argv[])
 198 {
 199   mpi::environment env(argc, argv);
 200
 201   int n = 1000;
 202   double p = 0.01;
 203   int c = 100;
 204   int seed = 1;
 205
 206   if (argc > 1) n             = lexical_cast<int>(argv[1]);
 207   if (argc > 2) p             = lexical_cast<double>(argv[2]);
 208   if (argc > 3) c             = lexical_cast<int>(argv[3]);
 209   if (argc > 4) seed          = lexical_cast<int>(argv[4]);
 210
 211   test_distributed_shortest_paths(n, p, c, seed);
 212
 213   return 0;
 214 }