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 |
596 | |