]>
Commit | Line | Data |
---|---|---|
1 | .. Copyright (C) 2004-2009 The Trustees of Indiana University. | |
2 | Use, modification and distribution is subject to the Boost Software | |
3 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
4 | http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | =================================== | |
7 | |Logo| Sorted R-MAT generator | |
8 | =================================== | |
9 | ||
10 | :: | |
11 | ||
12 | template<typename RandomGenerator, typename Graph, | |
13 | typename EdgePredicate = keep_all_edges> | |
14 | class sorted_rmat_iterator | |
15 | { | |
16 | public: | |
17 | typedef std::input_iterator_tag iterator_category; | |
18 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
19 | typedef const value_type& reference; | |
20 | typedef const value_type* pointer; | |
21 | typedef void difference_type; | |
22 | ||
23 | sorted_rmat_iterator(); | |
24 | sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
25 | edges_size_type m, double a, double b, double c, | |
26 | double d, bool permute_vertices = true); | |
27 | // Iterator operations | |
28 | reference operator*() const; | |
29 | pointer operator->() const; | |
30 | sorted_rmat_iterator& operator++(); | |
31 | sorted_rmat_iterator operator++(int); | |
32 | bool operator==(const sorted_rmat_iterator& other) const; | |
33 | bool operator!=(const sorted_rmat_iterator& other) const; | |
34 | }; | |
35 | ||
36 | This class template implements a generator for R-MAT graphs [CZF04]_, | |
37 | suitable for initializing an adjacency_list or other graph structure | |
38 | with iterator-based initialization. An R-MAT graph has a scale-free | |
39 | distribution w.r.t. vertex degree and is implemented using | |
40 | Recursive-MATrix partitioning. The output of this generator is sorted | |
41 | for use with `compressed sparse row graph`_. | |
42 | ||
43 | Where Defined | |
44 | ------------- | |
45 | <``boost/graph/rmat_graph_generator.hpp``> | |
46 | ||
47 | Constructors | |
48 | ------------ | |
49 | ||
50 | :: | |
51 | ||
52 | sorted_rmat_iterator(); | |
53 | ||
54 | Constructs a past-the-end iterator. | |
55 | ||
56 | :: | |
57 | ||
58 | ||
59 | sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
60 | edges_size_type m, double a, double b, double c, | |
61 | double d, bool permute_vertices = true, | |
62 | EdgePredicate ep = keep_all_edges()); | |
63 | ||
64 | Constructs an R-MAT generator iterator that creates a graph with ``n`` | |
65 | vertices and ``m`` edges. ``a``, ``b``, ``c``, and ``d`` represent | |
66 | the probability that a generated edge is placed of each of the 4 | |
67 | quadrants of the partitioned adjacency matrix. Probabilities are | |
68 | drawn from the random number generator ``gen``. Vertex indices are | |
69 | permuted to eliminate locality when ``permute_vertices`` is true. | |
70 | ``ep`` allows the user to specify which edges are retained, this is | |
71 | useful in the case where the user wishes to refrain from storing | |
72 | remote edges locally during generation to reduce memory consumption. | |
73 | ||
74 | Example | |
75 | ------- | |
76 | ||
77 | :: | |
78 | ||
79 | #include <boost/graph/compressed_sparse_row_graph.hpp> | |
80 | #include <boost/graph/rmat_graph_generator.hpp> | |
81 | #include <boost/random/linear_congruential.hpp> | |
82 | ||
83 | typedef boost::compressed_sparse_row_graph<> Graph; | |
84 | typedef boost::sorted_rmat_iterator<boost::minstd_rand, Graph> | |
85 | RMATGen; | |
86 | ||
87 | int main() | |
88 | { | |
89 | boost::minstd_rand gen; | |
90 | // Create graph with 100 nodes and 400 edges | |
91 | Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05), | |
92 | RMATGen(), 100); | |
93 | return 0; | |
94 | } | |
95 | ||
96 | Bibliography | |
97 | ------------ | |
98 | ||
99 | .. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos. R-MAT: A Recursive | |
100 | Model for Graph Mining. In Proceedings of 4th International Conference | |
101 | on Data Mining, pages 442--446, 2004. | |
102 | ||
103 | ----------------------------------------------------------------------------- | |
104 | ||
105 | Copyright (C) 2009 The Trustees of Indiana University. | |
106 | ||
107 | Authors: Nick Edmonds and Andrew Lumsdaine | |
108 | ||
109 | .. |Logo| image:: pbgl-logo.png | |
110 | :align: middle | |
111 | :alt: Parallel BGL | |
112 | :target: http://www.osl.iu.edu/research/pbgl | |
113 | ||
114 | .. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html |