]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2004, 2005 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 | #ifndef BOOST_GRAPH_RMAT_GENERATOR_HPP | |
10 | #define BOOST_GRAPH_RMAT_GENERATOR_HPP | |
11 | ||
12 | #include <math.h> | |
13 | #include <iterator> | |
14 | #include <utility> | |
15 | #include <vector> | |
16 | #include <queue> | |
17 | #include <map> | |
18 | #include <boost/shared_ptr.hpp> | |
19 | #include <boost/assert.hpp> | |
20 | #include <boost/random/uniform_int.hpp> | |
21 | #include <boost/random/uniform_01.hpp> | |
22 | #include <boost/graph/graph_traits.hpp> | |
23 | #include <boost/type_traits/is_base_and_derived.hpp> | |
24 | #include <boost/type_traits/is_same.hpp> | |
25 | // #include <boost/test/floating_point_comparison.hpp> | |
26 | ||
27 | using boost::shared_ptr; | |
28 | using boost::uniform_01; | |
29 | ||
30 | // Returns floor(log_2(n)), and -1 when n is 0 | |
31 | template <typename IntegerType> | |
32 | inline int int_log2(IntegerType n) { | |
33 | int l = 0; | |
34 | while (n > 0) {++l; n >>= 1;} | |
35 | return l - 1; | |
36 | } | |
37 | ||
38 | struct keep_all_edges { | |
39 | template <typename T> | |
40 | bool operator()(const T&, const T&) { return true; } | |
41 | }; | |
42 | ||
43 | template <typename Distribution, typename ProcessId> | |
44 | struct keep_local_edges { | |
45 | ||
46 | keep_local_edges(const Distribution& distrib, const ProcessId& id) | |
47 | : distrib(distrib), id(id) | |
48 | { } | |
49 | ||
50 | template <typename T> | |
51 | bool operator()(const T& x, const T& y) | |
52 | { return distrib(x) == id || distrib(y) == id; } | |
53 | ||
54 | private: | |
55 | const Distribution& distrib; | |
56 | const ProcessId& id; | |
57 | }; | |
58 | ||
59 | template <typename RandomGenerator, typename T> | |
60 | void | |
61 | generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n) | |
62 | { | |
63 | using boost::uniform_int; | |
64 | ||
65 | vertexPermutation.resize(n); | |
66 | ||
67 | // Generate permutation map of vertex numbers | |
68 | uniform_int<T> rand_vertex(0, n-1); | |
69 | for (T i = 0; i < n; ++i) | |
70 | vertexPermutation[i] = i; | |
71 | ||
72 | // Can't use std::random_shuffle unless we create another (synchronized) PRNG | |
73 | for (T i = 0; i < n; ++i) | |
74 | std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]); | |
75 | } | |
76 | ||
77 | template <typename RandomGenerator, typename T> | |
78 | std::pair<T,T> | |
79 | generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n, | |
80 | unsigned int SCALE, double a, double b, double c, double d) | |
81 | { | |
82 | T u = 0, v = 0; | |
83 | T step = n/2; | |
84 | for (unsigned int j = 0; j < SCALE; ++j) { | |
85 | double p = (*prob)(); | |
86 | ||
87 | if (p < a) | |
88 | ; | |
89 | else if (p >= a && p < a + b) | |
90 | v += step; | |
91 | else if (p >= a + b && p < a + b + c) | |
92 | u += step; | |
93 | else { // p > a + b + c && p < a + b + c + d | |
94 | u += step; | |
95 | v += step; | |
96 | } | |
97 | ||
98 | step /= 2; | |
99 | ||
100 | // 0.2 and 0.9 are hardcoded in the reference SSCA implementation. | |
101 | // The maximum change in any given value should be less than 10% | |
102 | a *= 0.9 + 0.2 * (*prob)(); | |
103 | b *= 0.9 + 0.2 * (*prob)(); | |
104 | c *= 0.9 + 0.2 * (*prob)(); | |
105 | d *= 0.9 + 0.2 * (*prob)(); | |
106 | ||
107 | double S = a + b + c + d; | |
108 | ||
109 | a /= S; b /= S; c /= S; | |
110 | // d /= S; | |
111 | // Ensure all values add up to 1, regardless of floating point errors | |
112 | d = 1. - a - b - c; | |
113 | } | |
114 | ||
115 | return std::make_pair(u, v); | |
116 | } | |
117 | ||
118 | namespace boost { | |
119 | ||
120 | /* | |
121 | Chakrabarti's R-MAT scale free generator. | |
122 | ||
123 | For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the | |
124 | unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the | |
125 | generator may be unable to generate sufficient unique edges | |
126 | ||
127 | To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d} | |
128 | */ | |
129 | ||
130 | template<typename RandomGenerator, typename Graph> | |
131 | class rmat_iterator | |
132 | { | |
133 | typedef typename graph_traits<Graph>::directed_category directed_category; | |
134 | typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; | |
135 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
136 | ||
137 | public: | |
138 | typedef std::input_iterator_tag iterator_category; | |
139 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
140 | typedef const value_type& reference; | |
141 | typedef const value_type* pointer; | |
142 | typedef std::ptrdiff_t difference_type; // Not used | |
143 | ||
144 | // No argument constructor, set to terminating condition | |
145 | rmat_iterator() | |
146 | : gen(), edge(0) { } | |
147 | ||
148 | // Initialize for edge generation | |
149 | rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
150 | edges_size_type m, double a, double b, double c, | |
151 | double d, bool permute_vertices = true) | |
152 | : gen(), n(n), a(a), b(b), c(c), d(d), edge(m), | |
153 | permute_vertices(permute_vertices), | |
154 | SCALE(int_log2(n)) | |
155 | ||
156 | { | |
157 | this->gen.reset(new uniform_01<RandomGenerator>(gen)); | |
158 | ||
159 | // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5)); | |
160 | ||
161 | if (permute_vertices) | |
162 | generate_permutation_vector(gen, vertexPermutation, n); | |
163 | ||
164 | // TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph | |
165 | ||
166 | // Generate the first edge | |
167 | vertices_size_type u, v; | |
168 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
169 | ||
170 | if (permute_vertices) | |
171 | current = std::make_pair(vertexPermutation[u], | |
172 | vertexPermutation[v]); | |
173 | else | |
174 | current = std::make_pair(u, v); | |
175 | ||
176 | --edge; | |
177 | } | |
178 | ||
179 | reference operator*() const { return current; } | |
180 | pointer operator->() const { return ¤t; } | |
181 | ||
182 | rmat_iterator& operator++() | |
183 | { | |
184 | vertices_size_type u, v; | |
185 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
186 | ||
187 | if (permute_vertices) | |
188 | current = std::make_pair(vertexPermutation[u], | |
189 | vertexPermutation[v]); | |
190 | else | |
191 | current = std::make_pair(u, v); | |
192 | ||
193 | --edge; | |
194 | ||
195 | return *this; | |
196 | } | |
197 | ||
198 | rmat_iterator operator++(int) | |
199 | { | |
200 | rmat_iterator temp(*this); | |
201 | ++(*this); | |
202 | return temp; | |
203 | } | |
204 | ||
205 | bool operator==(const rmat_iterator& other) const | |
206 | { | |
207 | return edge == other.edge; | |
208 | } | |
209 | ||
210 | bool operator!=(const rmat_iterator& other) const | |
211 | { return !(*this == other); } | |
212 | ||
213 | private: | |
214 | ||
215 | // Parameters | |
216 | shared_ptr<uniform_01<RandomGenerator> > gen; | |
217 | vertices_size_type n; | |
218 | double a, b, c, d; | |
219 | int edge; | |
220 | bool permute_vertices; | |
221 | int SCALE; | |
222 | ||
223 | // Internal data structures | |
224 | std::vector<vertices_size_type> vertexPermutation; | |
225 | value_type current; | |
226 | }; | |
227 | ||
228 | // Sorted version for CSR | |
229 | template <typename T> | |
230 | struct sort_pair { | |
231 | bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y) | |
232 | { | |
233 | if (x.first == y.first) | |
234 | return x.second > y.second; | |
235 | else | |
236 | return x.first > y.first; | |
237 | } | |
238 | }; | |
239 | ||
240 | template<typename RandomGenerator, typename Graph, | |
241 | typename EdgePredicate = keep_all_edges> | |
242 | class sorted_rmat_iterator | |
243 | { | |
244 | typedef typename graph_traits<Graph>::directed_category directed_category; | |
245 | typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; | |
246 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
247 | ||
248 | public: | |
249 | typedef std::input_iterator_tag iterator_category; | |
250 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
251 | typedef const value_type& reference; | |
252 | typedef const value_type* pointer; | |
253 | typedef std::ptrdiff_t difference_type; // Not used | |
254 | ||
255 | // No argument constructor, set to terminating condition | |
256 | sorted_rmat_iterator() | |
257 | : gen(), values(sort_pair<vertices_size_type>()), done(true) | |
258 | { } | |
259 | ||
260 | // Initialize for edge generation | |
261 | sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
262 | edges_size_type m, double a, double b, double c, | |
263 | double d, bool permute_vertices = true, | |
264 | EdgePredicate ep = keep_all_edges()) | |
265 | : gen(), permute_vertices(permute_vertices), | |
266 | values(sort_pair<vertices_size_type>()), done(false) | |
267 | ||
268 | { | |
269 | // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5)); | |
270 | ||
271 | this->gen.reset(new uniform_01<RandomGenerator>(gen)); | |
272 | ||
273 | std::vector<vertices_size_type> vertexPermutation; | |
274 | if (permute_vertices) | |
275 | generate_permutation_vector(gen, vertexPermutation, n); | |
276 | ||
277 | // TODO: "Clip and flip" if undirected graph | |
278 | int SCALE = int_log2(n); | |
279 | ||
280 | for (edges_size_type i = 0; i < m; ++i) { | |
281 | ||
282 | vertices_size_type u, v; | |
283 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
284 | ||
285 | if (permute_vertices) { | |
286 | if (ep(vertexPermutation[u], vertexPermutation[v])) | |
287 | values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v])); | |
288 | } else { | |
289 | if (ep(u, v)) | |
290 | values.push(std::make_pair(u, v)); | |
291 | } | |
292 | ||
293 | } | |
294 | ||
295 | current = values.top(); | |
296 | values.pop(); | |
297 | } | |
298 | ||
299 | reference operator*() const { return current; } | |
300 | pointer operator->() const { return ¤t; } | |
301 | ||
302 | sorted_rmat_iterator& operator++() | |
303 | { | |
304 | if (!values.empty()) { | |
305 | current = values.top(); | |
306 | values.pop(); | |
307 | } else | |
308 | done = true; | |
309 | ||
310 | return *this; | |
311 | } | |
312 | ||
313 | sorted_rmat_iterator operator++(int) | |
314 | { | |
315 | sorted_rmat_iterator temp(*this); | |
316 | ++(*this); | |
317 | return temp; | |
318 | } | |
319 | ||
320 | bool operator==(const sorted_rmat_iterator& other) const | |
321 | { | |
322 | return values.empty() && other.values.empty() && done && other.done; | |
323 | } | |
324 | ||
325 | bool operator!=(const sorted_rmat_iterator& other) const | |
326 | { return !(*this == other); } | |
327 | ||
328 | private: | |
329 | ||
330 | // Parameters | |
331 | shared_ptr<uniform_01<RandomGenerator> > gen; | |
332 | bool permute_vertices; | |
333 | ||
334 | // Internal data structures | |
335 | std::priority_queue<value_type, std::vector<value_type>, sort_pair<vertices_size_type> > values; | |
336 | value_type current; | |
337 | bool done; | |
338 | }; | |
339 | ||
340 | ||
341 | // This version is slow but guarantees unique edges | |
342 | template<typename RandomGenerator, typename Graph, | |
343 | typename EdgePredicate = keep_all_edges> | |
344 | class unique_rmat_iterator | |
345 | { | |
346 | typedef typename graph_traits<Graph>::directed_category directed_category; | |
347 | typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; | |
348 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
349 | ||
350 | public: | |
351 | typedef std::input_iterator_tag iterator_category; | |
352 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
353 | typedef const value_type& reference; | |
354 | typedef const value_type* pointer; | |
355 | typedef std::ptrdiff_t difference_type; // Not used | |
356 | ||
357 | // No argument constructor, set to terminating condition | |
358 | unique_rmat_iterator() | |
359 | : gen(), done(true) | |
360 | { } | |
361 | ||
362 | // Initialize for edge generation | |
363 | unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
364 | edges_size_type m, double a, double b, double c, | |
365 | double d, bool permute_vertices = true, | |
366 | EdgePredicate ep = keep_all_edges()) | |
367 | : gen(), done(false) | |
368 | ||
369 | { | |
370 | // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5)); | |
371 | ||
372 | this->gen.reset(new uniform_01<RandomGenerator>(gen)); | |
373 | ||
374 | std::vector<vertices_size_type> vertexPermutation; | |
375 | if (permute_vertices) | |
376 | generate_permutation_vector(gen, vertexPermutation, n); | |
377 | ||
378 | int SCALE = int_log2(n); | |
379 | ||
380 | std::map<value_type, bool> edge_map; | |
381 | ||
382 | edges_size_type edges = 0; | |
383 | do { | |
384 | vertices_size_type u, v; | |
385 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
386 | ||
387 | // Lowest vertex number always comes first | |
388 | // (this means we don't have to worry about i->j and j->i being in the edge list) | |
389 | if (u > v && is_same<directed_category, undirected_tag>::value) | |
390 | std::swap(u, v); | |
391 | ||
392 | if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) { | |
393 | edge_map[std::make_pair(u, v)] = true; | |
394 | ||
395 | if (permute_vertices) { | |
396 | if (ep(vertexPermutation[u], vertexPermutation[v])) | |
397 | values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v])); | |
398 | } else { | |
399 | if (ep(u, v)) | |
400 | values.push_back(std::make_pair(u, v)); | |
401 | } | |
402 | ||
403 | edges++; | |
404 | } | |
405 | } while (edges < m); | |
406 | // NGE - Asking for more than n^2 edges will result in an infinite loop here | |
407 | // Asking for a value too close to n^2 edges may as well | |
408 | ||
409 | current = values.back(); | |
410 | values.pop_back(); | |
411 | } | |
412 | ||
413 | reference operator*() const { return current; } | |
414 | pointer operator->() const { return ¤t; } | |
415 | ||
416 | unique_rmat_iterator& operator++() | |
417 | { | |
418 | if (!values.empty()) { | |
419 | current = values.back(); | |
420 | values.pop_back(); | |
421 | } else | |
422 | done = true; | |
423 | ||
424 | return *this; | |
425 | } | |
426 | ||
427 | unique_rmat_iterator operator++(int) | |
428 | { | |
429 | unique_rmat_iterator temp(*this); | |
430 | ++(*this); | |
431 | return temp; | |
432 | } | |
433 | ||
434 | bool operator==(const unique_rmat_iterator& other) const | |
435 | { | |
436 | return values.empty() && other.values.empty() && done && other.done; | |
437 | } | |
438 | ||
439 | bool operator!=(const unique_rmat_iterator& other) const | |
440 | { return !(*this == other); } | |
441 | ||
442 | private: | |
443 | ||
444 | // Parameters | |
445 | shared_ptr<uniform_01<RandomGenerator> > gen; | |
446 | ||
447 | // Internal data structures | |
448 | std::vector<value_type> values; | |
449 | value_type current; | |
450 | bool done; | |
451 | }; | |
452 | ||
453 | // This version is slow but guarantees unique edges | |
454 | template<typename RandomGenerator, typename Graph, | |
455 | typename EdgePredicate = keep_all_edges> | |
456 | class sorted_unique_rmat_iterator | |
457 | { | |
458 | typedef typename graph_traits<Graph>::directed_category directed_category; | |
459 | typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; | |
460 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
461 | ||
462 | public: | |
463 | typedef std::input_iterator_tag iterator_category; | |
464 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
465 | typedef const value_type& reference; | |
466 | typedef const value_type* pointer; | |
467 | typedef std::ptrdiff_t difference_type; // Not used | |
468 | ||
469 | // No argument constructor, set to terminating condition | |
470 | sorted_unique_rmat_iterator() | |
471 | : gen(), values(sort_pair<vertices_size_type>()), done(true) { } | |
472 | ||
473 | // Initialize for edge generation | |
474 | sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
475 | edges_size_type m, double a, double b, double c, | |
476 | double d, bool bidirectional = false, | |
477 | bool permute_vertices = true, | |
478 | EdgePredicate ep = keep_all_edges()) | |
479 | : gen(), bidirectional(bidirectional), | |
480 | values(sort_pair<vertices_size_type>()), done(false) | |
481 | ||
482 | { | |
483 | // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5)); | |
484 | ||
485 | this->gen.reset(new uniform_01<RandomGenerator>(gen)); | |
486 | ||
487 | std::vector<vertices_size_type> vertexPermutation; | |
488 | if (permute_vertices) | |
489 | generate_permutation_vector(gen, vertexPermutation, n); | |
490 | ||
491 | int SCALE = int_log2(n); | |
492 | ||
493 | std::map<value_type, bool> edge_map; | |
494 | ||
495 | edges_size_type edges = 0; | |
496 | do { | |
497 | ||
498 | vertices_size_type u, v; | |
499 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
500 | ||
501 | if (bidirectional) { | |
502 | if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) { | |
503 | edge_map[std::make_pair(u, v)] = true; | |
504 | edge_map[std::make_pair(v, u)] = true; | |
505 | ||
506 | if (ep(u, v)) { | |
507 | if (permute_vertices) { | |
508 | values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v])); | |
509 | values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u])); | |
510 | } else { | |
511 | values.push(std::make_pair(u, v)); | |
512 | values.push(std::make_pair(v, u)); | |
513 | } | |
514 | } | |
515 | ||
516 | ++edges; | |
517 | } | |
518 | } else { | |
519 | // Lowest vertex number always comes first | |
520 | // (this means we don't have to worry about i->j and j->i being in the edge list) | |
521 | if (u > v && is_same<directed_category, undirected_tag>::value) | |
522 | std::swap(u, v); | |
523 | ||
524 | if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) { | |
525 | edge_map[std::make_pair(u, v)] = true; | |
526 | ||
527 | if (permute_vertices) { | |
528 | if (ep(vertexPermutation[u], vertexPermutation[v])) | |
529 | values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v])); | |
530 | } else { | |
531 | if (ep(u, v)) | |
532 | values.push(std::make_pair(u, v)); | |
533 | } | |
534 | ||
535 | ++edges; | |
536 | } | |
537 | } | |
538 | ||
539 | } while (edges < m); | |
540 | // NGE - Asking for more than n^2 edges will result in an infinite loop here | |
541 | // Asking for a value too close to n^2 edges may as well | |
542 | ||
543 | current = values.top(); | |
544 | values.pop(); | |
545 | } | |
546 | ||
547 | reference operator*() const { return current; } | |
548 | pointer operator->() const { return ¤t; } | |
549 | ||
550 | sorted_unique_rmat_iterator& operator++() | |
551 | { | |
552 | if (!values.empty()) { | |
553 | current = values.top(); | |
554 | values.pop(); | |
555 | } else | |
556 | done = true; | |
557 | ||
558 | return *this; | |
559 | } | |
560 | ||
561 | sorted_unique_rmat_iterator operator++(int) | |
562 | { | |
563 | sorted_unique_rmat_iterator temp(*this); | |
564 | ++(*this); | |
565 | return temp; | |
566 | } | |
567 | ||
568 | bool operator==(const sorted_unique_rmat_iterator& other) const | |
569 | { | |
570 | return values.empty() && other.values.empty() && done && other.done; | |
571 | } | |
572 | ||
573 | bool operator!=(const sorted_unique_rmat_iterator& other) const | |
574 | { return !(*this == other); } | |
575 | ||
576 | private: | |
577 | ||
578 | // Parameters | |
579 | shared_ptr<uniform_01<RandomGenerator> > gen; | |
580 | bool bidirectional; | |
581 | ||
582 | // Internal data structures | |
583 | std::priority_queue<value_type, std::vector<value_type>, | |
584 | sort_pair<vertices_size_type> > values; | |
585 | value_type current; | |
586 | bool done; | |
587 | }; | |
588 | ||
589 | } // end namespace boost | |
590 | ||
591 | #ifdef BOOST_GRAPH_USE_MPI | |
592 | #include <boost/graph/distributed/rmat_graph_generator.hpp> | |
593 | #endif // BOOST_GRAPH_USE_MPI | |
594 | ||
595 | #endif // BOOST_GRAPH_RMAT_GENERATOR_HPP |