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 throw_exception(std::exception const & ex)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 get_time()42 inline time_type get_time() 43 { 44 return MPI_Wtime(); 45 } 46 print_time(time_type t)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 generator_iterator(RandomGenerator & gen,const F & f=F ())68 generator_iterator(RandomGenerator& gen, const F& f = F()) 69 : f(f), gen(&gen) 70 { 71 value = this->f(gen); 72 } 73 operator *() const74 reference operator*() const { return value; } operator ->() const75 pointer operator->() const { return &value; } 76 operator ++()77 generator_iterator& operator++() 78 { 79 value = f(*gen); 80 return *this; 81 } 82 operator ++(int)83 generator_iterator operator++(int) 84 { 85 generator_iterator temp(*this); 86 ++(*this); 87 return temp; 88 } 89 operator ==(const generator_iterator & other) const90 bool operator==(const generator_iterator& other) const 91 { return f == other.f; } 92 operator !=(const generator_iterator & other) const93 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> make_generator_iterator(RandomGenerator & gen,const F & f)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 verify_shortest_paths(const Graph & g,DistanceMap distance,const WeightMap & weight)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 { WeightedEdgeWeightedEdge139 WeightedEdge(weight_type weight = 0) : weight(weight) { } 140 141 weight_type weight; 142 143 template<typename Archiver> serializeWeightedEdge144 void serialize(Archiver& ar, const unsigned int /*version*/) 145 { 146 ar & weight; 147 } 148 }; 149 150 struct VertexProperties { VertexPropertiesVertexProperties151 VertexProperties(int d = 0) 152 : distance(d) { } 153 154 int distance; 155 156 template<typename Archiver> serializeVertexProperties157 void serialize(Archiver& ar, const unsigned int /*version*/) 158 { 159 ar & distance; 160 } 161 }; 162 163 void test_distributed_shortest_paths(int n,double p,int c,int seed)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 test_main(int argc,char * argv[])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 } 215