]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
1e59de90 | 19 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
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 | ||
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 | ||
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 | |
87 | generator_iterator(RandomGenerator& gen, const F& f = F()) | |
88 | : f(f), gen(&gen) | |
89 | { | |
90 | value = this->f(gen); | |
91 | } | |
92 | ||
93 | reference operator*() const { return value; } | |
94 | pointer operator->() const { return &value; } | |
95 | ||
96 | generator_iterator& operator++() | |
97 | { | |
98 | value = f(*gen); | |
99 | return *this; | |
100 | } | |
101 | ||
102 | generator_iterator operator++(int) | |
103 | { | |
104 | generator_iterator temp(*this); | |
105 | ++(*this); | |
106 | return temp; | |
107 | } | |
108 | ||
109 | bool operator==(const generator_iterator& other) const | |
110 | { return f == other.f; } | |
111 | ||
112 | 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> | |
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 { | |
132 | WeightedEdge(weight_type weight = 0) : weight(weight) { } | |
133 | ||
134 | weight_type weight; | |
135 | ||
136 | template<typename Archiver> | |
137 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
138 | { | |
139 | ar & weight; | |
140 | } | |
141 | }; | |
142 | ||
143 | /**************************************************************************** | |
144 | * Algorithm Tests * | |
145 | ****************************************************************************/ | |
146 | template <typename Graph> | |
147 | void test_directed_sequential_algorithms(const Graph& g) | |
148 | { } | |
149 | ||
150 | template <typename Graph> | |
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> | |
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> | |
284 | void test_directed_algorithms(const Graph& g) | |
285 | { | |
286 | } | |
287 | ||
288 | template <typename Graph> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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 | ||
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 | ||
1e59de90 | 750 | int main(int argc, char* argv[]) |
7c673cae FG |
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 | ||
1e59de90 | 886 | return boost::report_errors(); |
7c673cae | 887 | } |