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