1 // Copyright (C) 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: Nick Edmonds
8 // Andrew Lumsdaine
9
10 #include <boost/graph/use_mpi.hpp>
11
12 #define CSR
13
14 #ifdef CSR
15 # include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
16 #else
17 # include <boost/graph/distributed/adjacency_list.hpp>
18 #endif
19
20 #include <boost/config.hpp>
21 #include <boost/throw_exception.hpp>
22 #include <boost/graph/distributed/mpi_process_group.hpp>
23 #include <boost/graph/distributed/concepts.hpp>
24 #include <boost/graph/erdos_renyi_generator.hpp>
25 #include <boost/graph/distributed/betweenness_centrality.hpp>
26 #include <boost/random/linear_congruential.hpp>
27 #include <boost/graph/graphviz.hpp>
28 #include <boost/property_map/vector_property_map.hpp>
29 #include <boost/test/minimal.hpp>
30
31 #ifdef BOOST_NO_EXCEPTIONS
32 void
throw_exception(std::exception const & ex)33 boost::throw_exception(std::exception const& ex)
34 {
35 std::cout << ex.what() << std::endl;
36 abort();
37 }
38 #endif
39
40 /****************************************************************************
41 * Edge weight generator iterator *
42 ****************************************************************************/
43 template<typename F, typename RandomGenerator>
44 class generator_iterator
45 {
46 public:
47 typedef std::input_iterator_tag iterator_category;
48 typedef typename F::result_type value_type;
49 typedef const value_type& reference;
50 typedef const value_type* pointer;
51 typedef void difference_type;
52
53 explicit
generator_iterator(RandomGenerator & gen,const F & f=F ())54 generator_iterator(RandomGenerator& gen, const F& f = F())
55 : f(f), gen(&gen)
56 {
57 value = this->f(gen);
58 }
59
operator *() const60 reference operator*() const { return value; }
operator ->() const61 pointer operator->() const { return &value; }
62
operator ++()63 generator_iterator& operator++()
64 {
65 value = f(*gen);
66 return *this;
67 }
68
operator ++(int)69 generator_iterator operator++(int)
70 {
71 generator_iterator temp(*this);
72 ++(*this);
73 return temp;
74 }
75
operator ==(const generator_iterator & other) const76 bool operator==(const generator_iterator& other) const
77 { return f == other.f; }
78
operator !=(const generator_iterator & other) const79 bool operator!=(const generator_iterator& other) const
80 { return !(*this == other); }
81
82 private:
83 F f;
84 RandomGenerator* gen;
85 value_type value;
86 };
87
88 template<typename F, typename RandomGenerator>
89 inline generator_iterator<F, RandomGenerator>
make_generator_iterator(RandomGenerator & gen,const F & f)90 make_generator_iterator( RandomGenerator& gen, const F& f)
91 { return generator_iterator<F, RandomGenerator>(gen, f); }
92
93 using namespace boost;
94 using boost::graph::distributed::mpi_process_group;
95
96 typedef int weight_type;
97
98 struct WeightedEdge {
WeightedEdgeWeightedEdge99 WeightedEdge(weight_type weight = 0) : weight(weight) { }
100
101 weight_type weight;
102
103 template<typename Archiver>
serializeWeightedEdge104 void serialize(Archiver& ar, const unsigned int /*version*/)
105 {
106 ar & weight;
107 }
108 };
109
test_main(int argc,char * argv[])110 int test_main(int argc, char* argv[])
111 {
112 mpi::environment env(argc, argv);
113
114 #ifdef CSR
115 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge,
116 no_property, distributedS<mpi_process_group> >
117 Graph;
118 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
119 seqGraph;
120 #else
121 typedef adjacency_list<vecS,
122 distributedS<mpi_process_group, vecS>,
123 directedS,
124 no_property,
125 property<edge_weight_t, int> > Graph;
126
127 typedef adjacency_list<vecS, vecS, directedS, no_property,
128 property<edge_weight_t, int> > seqGraph;
129 #endif
130
131
132 typedef sorted_erdos_renyi_iterator<minstd_rand, Graph> ERIter;
133
134 int n = 100;
135 double prob = 0.1;
136 int C = 3;
137
138 minstd_rand gen;
139
140 gen.seed(1);
141
142 // NOTE: Weighted betweenness centrality only works with non-zero edge weights
143
144 // Build graphs
145 Graph g(edges_are_sorted, ERIter(gen, n, prob), ERIter(),
146 make_generator_iterator(gen, uniform_int<int>(1, C)),
147 n);
148
149 gen.seed(1); // Re-seed PRNG so we get the same graph
150
151 seqGraph sg(
152 #ifdef CSR
153 edges_are_sorted,
154 #endif
155 ERIter(gen, n, prob), ERIter(),
156 make_generator_iterator(gen, uniform_int<int>(1, C)),
157 n);
158
159 // Test Betweenness Centrality
160 typedef property_map<Graph, vertex_index_t>::const_type IndexMap;
161 typedef iterator_property_map<std::vector<int>::iterator, IndexMap>
162 CentralityMap;
163
164 std::vector<int> centralityS(num_vertices(g), 0);
165 CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
166
167 brandes_betweenness_centrality(g, centrality);
168
169 std::vector<int> weightedCentralityS(num_vertices(g), 0);
170 CentralityMap weightedCentrality(weightedCentralityS.begin(), get(vertex_index, g));
171
172 brandes_betweenness_centrality(g, centrality_map(weightedCentrality).
173 #ifdef CSR
174 weight_map(get(&WeightedEdge::weight, g)));
175 #else
176 weight_map(get(edge_weight, g)));
177 #endif
178
179 int g_cpd = central_point_dominance(g, centrality);
180
181 //
182 // Non-distributed (embarassingly parallel) Betweenness Centrality
183 //
184 typedef boost::graph::parallel::process_group_type<Graph>::type
185 process_group_type;
186
187 process_group_type pg = process_group(g);
188
189 process_group_type::process_id_type id = process_id(pg);
190 process_group_type::process_size_type p = num_processes(pg);
191
192 typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap;
193 typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap;
194
195 std::vector<int> nonDistributedCentralityS(num_vertices(sg), 0);
196 seqCentralityMap nonDistributedCentrality(nonDistributedCentralityS.begin(), get(vertex_index, sg));
197
198 std::vector<int> nonDistributedWeightedCentralityS(num_vertices(sg), 0);
199 seqCentralityMap nonDistributedWeightedCentrality(nonDistributedWeightedCentralityS.begin(),
200 get(vertex_index, sg));
201
202 non_distributed_brandes_betweenness_centrality(pg, sg, nonDistributedCentrality);
203
204 non_distributed_brandes_betweenness_centrality(pg, sg,
205 centrality_map(nonDistributedWeightedCentrality).
206 #ifdef CSR
207 weight_map(get(&WeightedEdge::weight, sg)));
208 #else
209 weight_map(get(edge_weight, sg)));
210 #endif
211
212 //
213 // Verify
214 //
215 std::vector<int> seqCentralityS(num_vertices(sg), 0);
216 seqCentralityMap seqCentrality(seqCentralityS.begin(), get(vertex_index, sg));
217
218 std::vector<int> seqWeightedCentralityS(num_vertices(sg), 0);
219 seqCentralityMap seqWeightedCentrality(seqWeightedCentralityS.begin(), get(vertex_index, sg));
220
221 brandes_betweenness_centrality(sg, seqCentrality);
222
223 brandes_betweenness_centrality(sg, centrality_map(seqWeightedCentrality).
224 #ifdef CSR
225 weight_map(get(&WeightedEdge::weight, sg)));
226 #else
227 weight_map(get(edge_weight, sg)));
228 #endif
229
230 int sg_cpd = central_point_dominance(sg, seqCentrality);
231
232 // Verify exact betweenness centrality
233 //
234 // We're cheating when we map vertices in g to vertices in sg
235 // since we know that g is using the block distribution here
236 typedef property_map<Graph, vertex_owner_t>::const_type OwnerMap;
237 typedef property_map<Graph, vertex_local_t>::const_type LocalMap;
238
239 OwnerMap owner = get(vertex_owner, g);
240 LocalMap local = get(vertex_local, g);
241
242 bool passed = true;
243
244 {
245 typedef graph_traits<Graph>::vertex_iterator vertex_iterator;
246 vertex_iterator v, v_end;
247
248 for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
249 if (get(centrality, *v) != seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
250 std::cerr << " " << id << ": Error - centrality of " << get(local, *v) << "@" << get(owner, *v)
251 << " does not match the sequential result (" << get(centrality, *v) << " vs. "
252 << seqCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
253 passed = false;
254 }
255
256 if (get(weightedCentrality, *v) != seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)]) {
257 std::cerr << " " << id << ": Error - weighted centrality of " << get(local, *v) << "@" << get(owner, *v)
258 << " does not match the sequential result (" << get(weightedCentrality, *v) << " vs. "
259 << seqWeightedCentralityS[(n/p) * get(owner, *v) + get(local, *v)] << ")\n";
260 passed = false;
261 }
262 }
263 }
264
265 if (id == 0) {
266 typedef graph_traits<seqGraph>::vertex_iterator vertex_iterator;
267 vertex_iterator v, v_end;
268
269 for (boost::tie(v, v_end) = vertices(sg); v != v_end; ++v) {
270 if (get(seqCentrality, *v) != get(nonDistributedCentrality, *v)) {
271 std::cerr << " " << id << ": Error - non-distributed centrality of " << *v
272 << " does not match the sequential result (" << get(nonDistributedCentrality, *v)
273 << " vs. " << get(seqCentrality, *v) << ")\n";
274 passed = false;
275 }
276
277 if (get(seqWeightedCentrality, *v) != get(nonDistributedWeightedCentrality, *v)) {
278 std::cerr << " " << id << ": Error - non-distributed weighted centrality of " << *v
279 << " does not match the sequential result (" << get(nonDistributedWeightedCentrality, *v)
280 << " vs. " << get(seqCentrality, *v) << ")\n";
281 passed = false;
282 }
283 }
284 }
285
286 if (g_cpd != sg_cpd) {
287 passed = false;
288 std::cerr << "Central point dominance did not match the sequential result\n";
289 }
290
291 if (!passed)
292 MPI_Abort(MPI_COMM_WORLD, -1);
293
294 return 0;
295 }
296