1 // Copyright 2004 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 // #define PBGL_ACCOUNTING
11
12 #include <boost/graph/use_mpi.hpp>
13
14 #include <boost/graph/distributed/compressed_sparse_row_graph.hpp>
15 #include <boost/graph/distributed/adjacency_list.hpp>
16
17 #include <boost/graph/distributed/mpi_process_group.hpp>
18
19 #include <boost/test/minimal.hpp>
20 #include <boost/random.hpp>
21 #include <boost/property_map/parallel/distributed_property_map.hpp>
22 #include <boost/graph/distributed/graphviz.hpp>
23 #include <boost/graph/iteration_macros.hpp>
24 #include <boost/graph/properties.hpp>
25
26 #include <boost/graph/rmat_graph_generator.hpp>
27 #include <boost/graph/small_world_generator.hpp>
28 #include <boost/graph/erdos_renyi_generator.hpp>
29
30 #include <boost/graph/distributed/connected_components.hpp>
31 #include <boost/graph/distributed/connected_components_parallel_search.hpp>
32 #include <boost/graph/distributed/betweenness_centrality.hpp>
33 #include <boost/graph/distributed/delta_stepping_shortest_paths.hpp>
34
35 #include <time.h>
36 #include <sys/time.h>
37
38 #include <iostream>
39 #include <iomanip>
40 #include <vector>
41 #include <stdint.h>
42
43 // Edge distribution tags select a generator
44 struct rmat_edge_distribution_tag { };
45 struct rmat_unique_edge_distribution_tag { };
46
47 using namespace boost;
48 using boost::graph::distributed::mpi_process_group;
49
50 /****************************************************************************
51 * Timing
52 ****************************************************************************/
53 #ifndef PBGL_ACCOUNTING
54
55 typedef double time_type;
56
get_time()57 inline time_type get_time()
58 {
59 timeval tp;
60 gettimeofday(&tp, 0);
61 return tp.tv_sec + tp.tv_usec / 1000000.0;
62 }
63
print_time(time_type t)64 std::string print_time(time_type t)
65 {
66 std::ostringstream out;
67 out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t;
68 return out.str();
69 }
70
71 #endif // PBGL_ACCOUNTING
72
73 /****************************************************************************
74 * Edge weight generator iterator *
75 ****************************************************************************/
76 template<typename F, typename RandomGenerator>
77 class generator_iterator
78 {
79 public:
80 typedef std::input_iterator_tag iterator_category;
81 typedef typename F::result_type value_type;
82 typedef const value_type& reference;
83 typedef const value_type* pointer;
84 typedef void difference_type;
85
86 explicit
generator_iterator(RandomGenerator & gen,const F & f=F ())87 generator_iterator(RandomGenerator& gen, const F& f = F())
88 : f(f), gen(&gen)
89 {
90 value = this->f(gen);
91 }
92
operator *() const93 reference operator*() const { return value; }
operator ->() const94 pointer operator->() const { return &value; }
95
operator ++()96 generator_iterator& operator++()
97 {
98 value = f(*gen);
99 return *this;
100 }
101
operator ++(int)102 generator_iterator operator++(int)
103 {
104 generator_iterator temp(*this);
105 ++(*this);
106 return temp;
107 }
108
operator ==(const generator_iterator & other) const109 bool operator==(const generator_iterator& other) const
110 { return f == other.f; }
111
operator !=(const generator_iterator & other) const112 bool operator!=(const generator_iterator& other) const
113 { return !(*this == other); }
114
115 private:
116 F f;
117 RandomGenerator* gen;
118 value_type value;
119 };
120
121 template<typename F, typename RandomGenerator>
122 inline generator_iterator<F, RandomGenerator>
make_generator_iterator(RandomGenerator & gen,const F & f)123 make_generator_iterator( RandomGenerator& gen, const F& f)
124 { return generator_iterator<F, RandomGenerator>(gen, f); }
125
126 /****************************************************************************
127 * Edge Property *
128 ****************************************************************************/
129 typedef int weight_type;
130
131 struct WeightedEdge {
WeightedEdgeWeightedEdge132 WeightedEdge(weight_type weight = 0) : weight(weight) { }
133
134 weight_type weight;
135
136 template<typename Archiver>
serializeWeightedEdge137 void serialize(Archiver& ar, const unsigned int /*version*/)
138 {
139 ar & weight;
140 }
141 };
142
143 /****************************************************************************
144 * Algorithm Tests *
145 ****************************************************************************/
146 template <typename Graph>
test_directed_sequential_algorithms(const Graph & g)147 void test_directed_sequential_algorithms(const Graph& g)
148 { }
149
150 template <typename Graph>
test_undirected_sequential_algorithms(const Graph & g)151 void test_undirected_sequential_algorithms(const Graph& g)
152 {
153 std::vector<unsigned int> componentS(num_vertices(g));
154 typedef iterator_property_map<
155 std::vector<unsigned int>::iterator,
156 typename property_map<Graph, vertex_index_t>::type>
157 ComponentMap;
158 ComponentMap component(componentS.begin(), get(vertex_index, g));
159
160 time_type start = get_time();
161 unsigned int num_components = connected_components(g, component);
162 time_type end = get_time();
163
164 std::cerr << " Sequential connected Components time = "
165 << print_time(end - start) << " seconds.\n"
166 << " " << num_components << " components identified\n";
167 }
168
169 template <typename Graph, typename EdgeWeightMap>
test_directed_csr_only_algorithms(const Graph & g,EdgeWeightMap weight,typename graph_traits<Graph>::vertices_size_type num_sources,typename property_traits<EdgeWeightMap>::value_type C)170 void test_directed_csr_only_algorithms(const Graph& g, EdgeWeightMap weight,
171 typename graph_traits<Graph>::vertices_size_type num_sources,
172 typename property_traits<EdgeWeightMap>::value_type C)
173 {
174 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
175 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
176 typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
177 typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
178
179 typedef typename boost::graph::parallel::process_group_type<Graph>::type
180 process_group_type;
181
182 process_group_type pg = process_group(g);
183 typename process_group_type::process_id_type id = process_id(pg);
184 typename process_group_type::process_size_type p = num_processes(pg);
185
186 vertices_size_type n = num_vertices(g);
187 n = boost::parallel::all_reduce(pg, n, std::plus<vertices_size_type>());
188
189 edges_size_type m = num_edges(g);
190 m = boost::parallel::all_reduce(pg, m, std::plus<edges_size_type>());
191
192 //
193 // Betweenness Centrality (Approximate)
194 //
195 queue<vertex_descriptor> delta_stepping_vertices;
196
197 {
198 // Distributed Centrality Map
199 typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
200 typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap;
201
202 std::vector<int> centralityS(num_vertices(g), 0);
203 CentralityMap centrality(centralityS.begin(), get(vertex_index, g));
204
205 // Calculate number of vertices of degree 0
206 vertices_size_type n0 = 0;
207 BGL_FORALL_VERTICES_T(v, g, Graph) {
208 if (out_degree(v, g) == 0) n0++;
209 }
210 n0 = boost::parallel::all_reduce(pg, n0, std::plus<vertices_size_type>());
211
212 queue<vertex_descriptor> sources;
213
214 {
215 assert(num_sources >= p); // Don't feel like adding a special case for num_sources < p
216
217 minstd_rand gen;
218 uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1);
219 std::vector<vertex_descriptor> all_sources, local_sources;
220 vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p));
221 local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0);
222
223 while (local_vertices > 0) {
224 vertex_iterator iter = vertices(g).first;
225 std::advance(iter, rand_vertex(gen));
226
227 if (out_degree(*iter, g) != 0
228 && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) {
229 local_sources.push_back(*iter);
230 --local_vertices;
231 }
232 }
233 all_gather(pg, local_sources.begin(), local_sources.end(), all_sources);
234 std::sort(all_sources.begin(), all_sources.end());
235 for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin();
236 iter != all_sources.end(); ++iter) {
237 sources.push(*iter);
238 delta_stepping_vertices.push(*iter);
239 }
240 }
241
242 // NOTE: The delta below assumes uniform edge weight distribution
243 time_type start = get_time();
244 brandes_betweenness_centrality(g, buffer(sources).weight_map(weight).
245 centrality_map(centrality).lookahead((m / n) * (C / 2)));
246 time_type end = get_time();
247
248 edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start)));
249
250 if (id == 0)
251 std::cerr << " Betweenness Centrality Approximate (" << num_sources << " sources) = "
252 << print_time(end - start) << " (" << exactTEPs << " TEPs)\n";
253 }
254
255 //
256 // Delta stepping performance (to compare to SSSP inside BC
257 //
258 if (false) {
259 typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
260 typedef iterator_property_map<std::vector<int>::iterator, IndexMap> DistanceMap;
261
262 std::vector<int> distanceS(num_vertices(g), 0);
263 DistanceMap distance(distanceS.begin(), get(vertex_index, g));
264
265 while(!delta_stepping_vertices.empty()) {
266
267 time_type start = get_time();
268 delta_stepping_shortest_paths(g, delta_stepping_vertices.top(), dummy_property_map(),
269 distance, weight);
270 time_type end = get_time();
271
272 delta_stepping_vertices.pop();
273 distance.reset();
274
275 if (id == 0)
276 std::cerr << " Delta-stepping shortest paths = " << print_time(end - start)
277 << std::endl;
278 }
279 }
280
281 }
282
283 template <typename Graph>
test_directed_algorithms(const Graph & g)284 void test_directed_algorithms(const Graph& g)
285 {
286 }
287
288 template <typename Graph>
test_undirected_algorithms(const Graph & g)289 void test_undirected_algorithms(const Graph& g)
290 {
291 typedef typename boost::graph::parallel::process_group_type<Graph>::type
292 process_group_type;
293
294 process_group_type pg = process_group(g);
295 typename process_group_type::process_id_type id = process_id(pg);
296 typename process_group_type::process_size_type p = num_processes(pg);
297
298
299 // Connected Components
300 std::vector<unsigned int> local_components_vec(num_vertices(g));
301 typedef iterator_property_map<
302 std::vector<unsigned int>::iterator,
303 typename property_map<Graph, vertex_index_t>::type>
304 ComponentMap;
305 ComponentMap component(local_components_vec.begin(), get(vertex_index, g));
306
307 int num_components;
308
309 time_type start = get_time();
310 num_components = connected_components(g, component);
311 time_type end = get_time();
312 if (id == 0)
313 std::cerr << " Connected Components time = " << print_time(end - start)
314 << " seconds.\n"
315 << " " << num_components << " components identified\n";
316
317 start = get_time();
318 num_components = boost::graph::distributed::connected_components_ps(g, component);
319 end = get_time();
320 if (id == 0)
321 std::cerr << " Connected Components (parallel search) time = "
322 << print_time(end - start) << " seconds.\n"
323 << " " << num_components << " components identified\n";
324 }
325
326 /****************************************************************************
327 * Graph Type Tests *
328 ****************************************************************************/
329
330 // TODO: Re-seed PRNG before sequential tests to get the same graph as the
331 // distributed case?
332
333 //
334 // Compressed Sparse Row
335 //
336
337 // R-MAT
338 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_csr(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double a,double b,double c,double d,size_t num_sources,rmat_edge_distribution_tag)339 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
340 bool sequential_tests, size_t N, size_t M, size_t C,
341 double a, double b, double c, double d, size_t num_sources,
342 rmat_edge_distribution_tag)
343 {
344 if (process_id(pg) == 0)
345 std::cerr << " R-MAT\n";
346
347 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
348 distributedS<mpi_process_group> > Graph;
349
350 Graph g(sorted_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
351 sorted_rmat_iterator<RandomGenerator, Graph>(),
352 make_generator_iterator(gen, uniform_int<int>(1, C)),
353 N, pg, distrib);
354
355 test_directed_algorithms(g);
356 test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
357
358 if (sequential_tests && process_id(pg) == 0) {
359 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
360 seqGraph;
361
362 seqGraph sg(edges_are_sorted,
363 sorted_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
364 sorted_rmat_iterator<RandomGenerator, seqGraph>(),
365 make_generator_iterator(gen, uniform_int<int>(1, C)),
366 N);
367
368 test_directed_sequential_algorithms(sg);
369 }
370 }
371
372 // R-MAT with unique edges
373 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_csr(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double a,double b,double c,double d,size_t num_sources,rmat_unique_edge_distribution_tag)374 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
375 bool sequential_tests, size_t N, size_t M, size_t C,
376 double a, double b, double c, double d, size_t num_sources,
377 rmat_unique_edge_distribution_tag)
378 {
379 if (process_id(pg) == 0)
380 std::cerr << " R-MAT - unique\n";
381
382 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
383 distributedS<mpi_process_group> > Graph;
384
385 // Last boolean parameter makes R-MAT bidirectional
386 Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
387 sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
388 make_generator_iterator(gen, uniform_int<int>(1, C)),
389 N, pg, distrib);
390
391 test_directed_algorithms(g);
392 test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
393
394 if (sequential_tests && process_id(pg) == 0) {
395 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
396 seqGraph;
397
398 seqGraph sg(edges_are_sorted,
399 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
400 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
401 make_generator_iterator(gen, uniform_int<int>(1, C)),
402 N);
403
404 test_directed_sequential_algorithms(sg);
405 }
406 }
407
408 // Erdos-Renyi
409 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_csr(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,size_t num_sources)410 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
411 bool sequential_tests, size_t N, size_t M, size_t C, size_t num_sources)
412 {
413 if (process_id(pg) == 0)
414 std::cerr << " Erdos-Renyi\n";
415
416 double _p = static_cast<double>(M) / (N*N);
417
418 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
419 distributedS<mpi_process_group> > Graph;
420
421 Graph g(sorted_erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
422 sorted_erdos_renyi_iterator<RandomGenerator, Graph>(),
423 make_generator_iterator(gen, uniform_int<int>(1, C)),
424 N, pg, distrib);
425
426 test_directed_algorithms(g);
427 test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
428
429 if (sequential_tests && process_id(pg) == 0) {
430 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
431 seqGraph;
432
433 seqGraph sg(edges_are_sorted,
434 sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
435 sorted_erdos_renyi_iterator<RandomGenerator, seqGraph>(),
436 make_generator_iterator(gen, uniform_int<int>(1, C)),
437 N);
438
439 test_directed_sequential_algorithms(sg);
440 }
441 }
442
443 // Small World
444 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_csr(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double p,size_t num_sources)445 void test_csr(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
446 bool sequential_tests, size_t N, size_t M, size_t C, double p,
447 size_t num_sources)
448 {
449 if (process_id(pg) == 0)
450 std::cerr << " Small-World\n";
451
452 int k = M / N;
453
454 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge, no_property,
455 distributedS<mpi_process_group> > Graph;
456
457 Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
458 small_world_iterator<RandomGenerator, Graph>(),
459 make_generator_iterator(gen, uniform_int<int>(1, C)),
460 N, pg, distrib);
461
462 test_directed_algorithms(g);
463 test_directed_csr_only_algorithms(g, get(&WeightedEdge::weight, g), num_sources, C);
464
465 if (sequential_tests && process_id(pg) == 0) {
466 typedef compressed_sparse_row_graph<directedS, no_property, WeightedEdge>
467 seqGraph;
468
469 seqGraph sg(edges_are_sorted,
470 small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
471 small_world_iterator<RandomGenerator, seqGraph>(),
472 make_generator_iterator(gen, uniform_int<int>(1, C)),
473 N);
474
475 test_directed_sequential_algorithms(sg);
476 }
477 }
478
479 //
480 // Adjacency List
481 //
482
483 // R-MAT
484 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_adjacency_list(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double a,double b,double c,double d,rmat_edge_distribution_tag)485 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
486 bool sequential_tests, size_t N, size_t M, size_t C,
487 double a, double b, double c, double d,
488 rmat_edge_distribution_tag)
489 {
490 if (process_id(pg) == 0)
491 std::cerr << "R-MAT\n";
492
493 {
494 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
495 directedS, no_property, WeightedEdge> Graph;
496
497 Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
498 rmat_iterator<RandomGenerator, Graph>(),
499 make_generator_iterator(gen, uniform_int<int>(1, C)),
500 N, pg, distrib);
501
502 test_directed_algorithms(g);
503 }
504
505 {
506 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
507 undirectedS, no_property, WeightedEdge> Graph;
508
509 Graph g(rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
510 rmat_iterator<RandomGenerator, Graph>(),
511 make_generator_iterator(gen, uniform_int<int>(1, C)),
512 N, pg, distrib);
513
514 test_undirected_algorithms(g);
515 }
516
517 if (sequential_tests && process_id(pg) == 0) {
518 {
519 typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
520 seqGraph;
521
522 seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
523 rmat_iterator<RandomGenerator, seqGraph>(),
524 make_generator_iterator(gen, uniform_int<int>(1, C)),
525 N);
526
527 test_directed_sequential_algorithms(sg);
528 }
529
530 {
531 typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
532 seqGraph;
533
534 seqGraph sg(rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
535 rmat_iterator<RandomGenerator, seqGraph>(),
536 make_generator_iterator(gen, uniform_int<int>(1, C)),
537 N);
538
539 test_undirected_sequential_algorithms(sg);
540 }
541 }
542 }
543
544 // R-MAT with unique edges
545 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_adjacency_list(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double a,double b,double c,double d,rmat_unique_edge_distribution_tag)546 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
547 bool sequential_tests, size_t N, size_t M, size_t C,
548 double a, double b, double c, double d,
549 rmat_unique_edge_distribution_tag)
550 {
551 if (process_id(pg) == 0)
552 std::cerr << " R-MAT - unique\n";
553
554 {
555 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
556 directedS, no_property, WeightedEdge> Graph;
557
558 Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
559 sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
560 make_generator_iterator(gen, uniform_int<int>(1, C)),
561 N, pg, distrib);
562
563 test_directed_algorithms(g);
564 }
565
566 {
567 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
568 undirectedS, no_property, WeightedEdge> Graph;
569
570 Graph g(sorted_unique_rmat_iterator<RandomGenerator, Graph>(gen, N, M, a, b, c, d),
571 sorted_unique_rmat_iterator<RandomGenerator, Graph>(),
572 make_generator_iterator(gen, uniform_int<int>(1, C)),
573 N, pg, distrib);
574
575 test_undirected_algorithms(g);
576 }
577
578 if (sequential_tests && process_id(pg) == 0) {
579 {
580 typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
581 seqGraph;
582
583 seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
584 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
585 make_generator_iterator(gen, uniform_int<int>(1, C)),
586 N);
587
588 test_directed_sequential_algorithms(sg);
589 }
590
591 {
592 typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
593 seqGraph;
594
595 seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, N, M, a, b, c, d),
596 sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(),
597 make_generator_iterator(gen, uniform_int<int>(1, C)),
598 N);
599
600 test_undirected_sequential_algorithms(sg);
601 }
602 }
603 }
604
605 // Erdos-Renyi
606 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_adjacency_list(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C)607 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
608 bool sequential_tests, size_t N, size_t M, size_t C)
609 {
610 if (process_id(pg) == 0)
611 std::cerr << " Erdos-Renyi\n";
612
613 double _p = static_cast<double>(M) / N*N;
614
615 {
616 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
617 directedS, no_property, WeightedEdge> Graph;
618
619 Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
620 erdos_renyi_iterator<RandomGenerator, Graph>(),
621 make_generator_iterator(gen, uniform_int<int>(1, C)),
622 N, pg, distrib);
623
624 test_directed_algorithms(g);
625 }
626
627 {
628 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
629 undirectedS, no_property, WeightedEdge> Graph;
630
631 Graph g(erdos_renyi_iterator<RandomGenerator, Graph>(gen, N, _p/2),
632 erdos_renyi_iterator<RandomGenerator, Graph>(),
633 make_generator_iterator(gen, uniform_int<int>(1, C)),
634 N, pg, distrib);
635
636 test_undirected_algorithms(g);
637 }
638
639 if (sequential_tests && process_id(pg) == 0) {
640 {
641 typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
642 seqGraph;
643
644 seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
645 erdos_renyi_iterator<RandomGenerator, seqGraph>(),
646 make_generator_iterator(gen, uniform_int<int>(1, C)),
647 N);
648
649 test_directed_sequential_algorithms(sg);
650 }
651
652 {
653 typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
654 seqGraph;
655
656 seqGraph sg(erdos_renyi_iterator<RandomGenerator, seqGraph>(gen, N, _p/2),
657 erdos_renyi_iterator<RandomGenerator, seqGraph>(),
658 make_generator_iterator(gen, uniform_int<int>(1, C)),
659 N);
660
661 test_undirected_sequential_algorithms(sg);
662 }
663 }
664 }
665
666 // Small World
667 template <typename ProcessGroup, typename RandomGenerator, typename Distribution>
test_adjacency_list(const ProcessGroup & pg,RandomGenerator & gen,Distribution & distrib,bool sequential_tests,size_t N,size_t M,size_t C,double p)668 void test_adjacency_list(const ProcessGroup& pg, RandomGenerator& gen, Distribution& distrib,
669 bool sequential_tests, size_t N, size_t M, size_t C, double p)
670 {
671 if (process_id(pg) == 0)
672 std::cerr << " Small-World\n";
673
674 int k = M / N;
675
676 {
677 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
678 directedS, no_property, WeightedEdge> Graph;
679
680 Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
681 small_world_iterator<RandomGenerator, Graph>(),
682 make_generator_iterator(gen, uniform_int<int>(1, C)),
683 N, pg, distrib);
684
685 test_directed_algorithms(g);
686 }
687
688 {
689 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
690 undirectedS, no_property, WeightedEdge> Graph;
691
692 Graph g(small_world_iterator<RandomGenerator, Graph>(gen, N, k, p),
693 small_world_iterator<RandomGenerator, Graph>(),
694 make_generator_iterator(gen, uniform_int<int>(1, C)),
695 N, pg, distrib);
696
697 test_undirected_algorithms(g);
698 }
699
700 if (sequential_tests && process_id(pg) == 0) {
701 {
702 typedef adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, int> >
703 seqGraph;
704
705 seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
706 small_world_iterator<RandomGenerator, seqGraph>(),
707 make_generator_iterator(gen, uniform_int<int>(1, C)),
708 N);
709
710 test_directed_sequential_algorithms(sg);
711 }
712
713 {
714 typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> >
715 seqGraph;
716
717 seqGraph sg(small_world_iterator<RandomGenerator, seqGraph>(gen, N, k, p),
718 small_world_iterator<RandomGenerator, seqGraph>(),
719 make_generator_iterator(gen, uniform_int<int>(1, C)),
720 N);
721
722 test_undirected_sequential_algorithms(sg);
723 }
724 }
725 }
726
usage()727 void usage()
728 {
729 std::cerr << "Algorithm Performance Test\n"
730 << "Usage : algorithm_performance [options]\n\n"
731 << "Options are:\n"
732 << "\t--vertices v\t\t\tNumber of vertices in the graph\n"
733 << "\t--edges v\t\t\tNumber of edges in the graph\n"
734 << "\t--seed s\t\t\tSeed for synchronized random number generator\n"
735 << "\t--max-weight miw\t\tMaximum integer edge weight\n"
736 << "\t--rewire-probability\t\tRewire-probabitility (p) for small-world graphs\n"
737 << "\t--dot\t\t\t\tEmit a dot file containing the graph\n"
738 << "\t--verify\t\t\tVerify result\n"
739 << "\t--degree-dist\t\t\tOutput degree distribution of graph\n"
740 << "\t--sequential-graph\t\tRun sequential graph tests\n"
741 << "\t--erdos-renyi\t\t\tRun tests on Erdos-Renyi graphs\n"
742 << "\t--small-world\t\t\tRun tests on Small World graphs\n"
743 << "\t--rmat\t\t\t\tRun tests on R-MAT graphs\n"
744 << "\t--rmat-unique\t\t\tRun tests on R-MAT graphs with no duplicate edges\n"
745 << "\t--csr <bool>\t\t\tRun tests using CSR graphs\n"
746 << "\t--adjacency-list <bool>\t\tRun tests using Adjacency List graphs\n";
747 }
748
749
test_main(int argc,char * argv[])750 int test_main(int argc, char* argv[])
751 {
752 mpi::environment env(argc, argv);
753
754 rand48 gen;
755
756 // Default args
757 size_t n = 100,
758 m = 8*n,
759 c = 100,
760 num_sources = 32,
761 num_headers = 16 * 1024,
762 batch_buffer_size = 1024 * 1024;
763 uint64_t seed = 1;
764 bool emit_dot_file = false,
765 verify = false,
766 sequential_graph = false,
767 show_degree_dist = false,
768 erdos_renyi = false,
769 small_world = false,
770 rmat = false,
771 rmat_unique = false,
772 csr = false,
773 adj_list = false;
774 double p = 0.1,
775 rmat_a = 0.5,
776 rmat_b = 0.25,
777 rmat_c = 0.1,
778 rmat_d = 0.15;
779
780 // Parse args
781 for (int i = 1; i < argc; ++i) {
782 std::string arg = argv[i];
783
784 if (arg == "--vertices")
785 n = boost::lexical_cast<size_t>( argv[i+1] );
786
787 if (arg == "--seed")
788 seed = boost::lexical_cast<uint64_t>( argv[i+1] );
789
790 if (arg == "--edges")
791 m = boost::lexical_cast<size_t>( argv[i+1] );
792
793 if (arg == "--max-weight")
794 c = boost::lexical_cast<int>( argv[i+1] );
795
796 if (arg == "--batch-buffer-size") {
797 batch_buffer_size = boost::lexical_cast<size_t>( argv[i+1] );
798 num_headers = batch_buffer_size / 16;
799 num_headers = num_headers > 0 ? num_headers : 1;
800 }
801
802 if (arg == "--rewire-probability")
803 p = boost::lexical_cast<double>( argv[i+1] );
804
805 if (arg == "--num-sources")
806 num_sources = boost::lexical_cast<size_t>( argv[i + 1] );
807
808 if (arg == "--erdos-renyi")
809 erdos_renyi = true;
810
811 if (arg == "--small-world")
812 small_world = true;
813
814 if (arg == "--rmat")
815 rmat = true;
816
817 if (arg == "--rmat-unique")
818 rmat_unique = true;
819
820 if (arg == "--dot")
821 emit_dot_file = true;
822
823 if (arg == "--verify")
824 verify = true;
825
826 if (arg == "--degree-dist")
827 show_degree_dist = true;
828
829 if (arg == "--sequential-graph")
830 sequential_graph = true;
831
832 if (arg == "--csr")
833 csr = std::string(argv[i+1]) == "true";
834
835 if (arg == "--adjacency-list")
836 adj_list = std::string(argv[i+1]) == "true";
837 }
838
839 mpi_process_group pg(num_headers, batch_buffer_size);
840
841 if (argc == 1) {
842 if (process_id(pg) == 0)
843 usage();
844 exit(-1);
845 }
846
847 gen.seed(seed);
848
849 parallel::variant_distribution<mpi_process_group> distrib
850 = parallel::block(pg, n);
851
852 if (csr) {
853 if (process_id(pg) == 0)
854 std::cerr << "CSR Graph Tests\n";
855
856 if (erdos_renyi)
857 test_csr(pg, gen, distrib, sequential_graph, n, m, c, num_sources);
858 if (small_world)
859 test_csr(pg, gen, distrib, sequential_graph, n, m, c, p, num_sources);
860 if (rmat)
861 test_csr(pg, gen, distrib, sequential_graph, n, m, c,
862 rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_edge_distribution_tag());
863 if (rmat_unique)
864 test_csr(pg, gen, distrib, sequential_graph, n, m, c,
865 rmat_a, rmat_b, rmat_c, rmat_d, num_sources, rmat_unique_edge_distribution_tag());
866 }
867
868 gen.seed(seed); // DEBUG
869
870 if (adj_list) {
871 if (process_id(pg) == 0)
872 std::cerr << "Adjacency List Graph Tests\n";
873
874 if (erdos_renyi)
875 test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c);
876 if (small_world)
877 test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c, p);
878 if (rmat)
879 test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
880 rmat_a, rmat_b, rmat_c, rmat_d, rmat_edge_distribution_tag());
881 if (rmat_unique)
882 test_adjacency_list(pg, gen, distrib, sequential_graph, n, m, c,
883 rmat_a, rmat_b, rmat_c, rmat_d, rmat_unique_edge_distribution_tag());
884 }
885
886 return 0;
887 }
888