]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 unique R-MAT generator | |
8 | ==================================== | |
9 | ||
10 | :: | |
11 | ||
12 | template<typename RandomGenerator, typename Graph, | |
13 | typename EdgePredicate = keep_all_edges> | |
14 | class sorted_unique_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_unique_rmat_iterator(); | |
24 | sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
25 | edges_size_type m, double a, double b, double c, | |
26 | double d, bool bidirectional = true, | |
27 | bool permute_vertices = true, | |
28 | EdgePredicate ep = keep_all_edges()); | |
29 | // Iterator operations | |
30 | reference operator*() const; | |
31 | pointer operator->() const; | |
32 | sorted_unique_rmat_iterator& operator++(); | |
33 | sorted_unique_rmat_iterator operator++(int); | |
34 | bool operator==(const sorted_unique_rmat_iterator& other) const; | |
35 | bool operator!=(const sorted_unique_rmat_iterator& other) const; | |
36 | }; | |
37 | ||
38 | This class template implements a generator for R-MAT graphs [CZF04]_, | |
39 | suitable for initializing an adjacency_list or other graph structure | |
40 | with iterator-based initialization. An R-MAT graph has a scale-free | |
41 | distribution w.r.t. vertex degree and is implemented using | |
42 | Recursive-MATrix partitioning. The output of this generator is sorted | |
43 | for use with a `compressed sparse row graph`_. The edge list produced by | |
44 | this iterator is guaranteed not to contain parallel edges. | |
45 | ||
46 | Where Defined | |
47 | ------------- | |
48 | <``boost/graph/rmat_graph_generator.hpp``> | |
49 | ||
50 | Constructors | |
51 | ------------ | |
52 | ||
53 | :: | |
54 | ||
55 | sorted_unique_rmat_iterator(); | |
56 | ||
57 | Constructs a past-the-end iterator. | |
58 | ||
59 | :: | |
60 | ||
61 | sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, | |
62 | edges_size_type m, double a, double b, double c, | |
63 | double d, bool bidirectional = false, | |
64 | bool permute_vertices = true, | |
65 | EdgePredicate ep = keep_all_edges()); | |
66 | ||
67 | Constructs an R-MAT generator iterator that creates a graph with ``n`` | |
68 | vertices and ``m`` edges. ``a``, ``b``, ``c``, and ``d`` represent | |
69 | the probability that a generated edge is placed of each of the 4 | |
70 | quadrants of the partitioned adjacency matrix. Probabilities are | |
71 | drawn from the random number generator ``gen``. Vertex indices are | |
72 | permuted to eliminate locality when ``permute_vertices`` is true. | |
73 | When ``bidirectional`` is ``true`` for every edge s-t, the | |
74 | corresponding anti-edge t-s is added as well, these anti-edges are not | |
75 | counted towards ``m``. ``ep`` allows the user to specify which edges | |
76 | are retained, this is useful in the case where the user wishes to | |
77 | refrain from storing remote edges locally during generation to reduce | |
78 | memory consumption. | |
79 | ||
80 | Example | |
81 | ------- | |
82 | ||
83 | :: | |
84 | ||
85 | #include <boost/graph/distributed/mpi_process_group.hpp> | |
86 | #include <boost/graph/compressed_sparse_row_graph.hpp> | |
87 | #include <boost/graph/rmat_graph_generator.hpp> | |
88 | #include <boost/random/linear_congruential.hpp> | |
89 | ||
90 | using boost::graph::distributed::mpi_process_group; | |
91 | ||
92 | typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, | |
93 | distributedS<mpi_process_group> > Graph; | |
94 | typedef keep_local_edges<boost::parallel::variant_distribution<mpi_process_group>, | |
95 | mpi_process_group::process_id_type> EdgeFilter; | |
96 | typedef boost::sorted_unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen; | |
97 | ||
98 | int main() | |
99 | { | |
100 | boost::minstd_rand gen; | |
101 | mpi_process_group pg; | |
102 | ||
103 | int N = 100; | |
104 | ||
105 | boost::parallel::variant_distribution<ProcessGroup> distrib | |
106 | = boost::parallel::block(pg, N); | |
107 | ||
108 | mpi_process_group::process_id_type id = process_id(pg); | |
109 | ||
110 | // Create graph with 100 nodes and 400 edges | |
111 | Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true, | |
112 | true, EdgeFilter(distrib, id)), | |
113 | RMATGen(), N, pg, distrib); | |
114 | return 0; | |
115 | } | |
116 | ||
117 | ||
118 | Bibliography | |
119 | ------------ | |
120 | ||
121 | .. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos. R-MAT: A Recursive | |
122 | Model for Graph Mining. In Proceedings of 4th International Conference | |
123 | on Data Mining, pages 442--446, 2004. | |
124 | ||
125 | ----------------------------------------------------------------------------- | |
126 | ||
127 | Copyright (C) 2009 The Trustees of Indiana University. | |
128 | ||
129 | Authors: Nick Edmonds and Andrew Lumsdaine | |
130 | ||
131 | .. |Logo| image:: pbgl-logo.png | |
132 | :align: middle | |
133 | :alt: Parallel BGL | |
134 | :target: http://www.osl.iu.edu/research/pbgl | |
135 | ||
136 | .. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html |