]>
Commit | Line | Data |
---|---|---|
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_DISTRIBUTED_RMAT_GENERATOR_HPP | |
10 | #define BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP | |
11 | ||
12 | #ifndef BOOST_GRAPH_USE_MPI | |
13 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
14 | #endif | |
15 | ||
16 | #include <boost/assert.hpp> | |
17 | #include <boost/graph/parallel/algorithm.hpp> | |
18 | #include <boost/graph/parallel/process_group.hpp> | |
19 | #include <math.h> | |
20 | ||
21 | namespace boost { | |
22 | ||
23 | // Memory-scalable (amount of memory required will scale down | |
24 | // linearly as the number of processes increases) generator, which | |
25 | // requires an MPI process group. Run-time is slightly worse than | |
26 | // the unique rmat generator. Edge list generated is sorted and | |
27 | // unique. | |
28 | template<typename ProcessGroup, typename Distribution, | |
29 | typename RandomGenerator, typename Graph> | |
30 | class scalable_rmat_iterator | |
31 | { | |
32 | typedef typename graph_traits<Graph>::directed_category directed_category; | |
33 | typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; | |
34 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
35 | ||
36 | public: | |
37 | typedef std::input_iterator_tag iterator_category; | |
38 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
39 | typedef const value_type& reference; | |
40 | typedef const value_type* pointer; | |
41 | typedef void difference_type; | |
42 | ||
43 | // No argument constructor, set to terminating condition | |
44 | scalable_rmat_iterator() | |
45 | : gen(), done(true) | |
46 | { } | |
47 | ||
48 | // Initialize for edge generation | |
49 | scalable_rmat_iterator(ProcessGroup pg, Distribution distrib, | |
50 | RandomGenerator& gen, vertices_size_type n, | |
51 | edges_size_type m, double a, double b, double c, | |
52 | double d, bool permute_vertices = true) | |
53 | : gen(), done(false) | |
54 | { | |
55 | BOOST_ASSERT(a + b + c + d == 1); | |
56 | int id = process_id(pg); | |
57 | ||
58 | this->gen.reset(new uniform_01<RandomGenerator>(gen)); | |
59 | ||
60 | std::vector<vertices_size_type> vertexPermutation; | |
61 | if (permute_vertices) | |
62 | generate_permutation_vector(gen, vertexPermutation, n); | |
63 | ||
64 | int SCALE = int(floor(log(double(n))/log(2.))); | |
65 | boost::uniform_01<RandomGenerator> prob(gen); | |
66 | ||
67 | std::map<value_type, bool> edge_map; | |
68 | ||
69 | edges_size_type generated = 0, local_edges = 0; | |
70 | do { | |
71 | edges_size_type tossed = 0; | |
72 | do { | |
73 | vertices_size_type u, v; | |
74 | boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); | |
75 | ||
76 | if (permute_vertices) { | |
77 | u = vertexPermutation[u]; | |
78 | v = vertexPermutation[v]; | |
79 | } | |
80 | ||
81 | // Lowest vertex number always comes first (this | |
82 | // means we don't have to worry about i->j and j->i | |
83 | // being in the edge list) | |
84 | if (u > v && is_same<directed_category, undirected_tag>::value) | |
85 | std::swap(u, v); | |
86 | ||
87 | if (distrib(u) == id || distrib(v) == id) { | |
88 | if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) { | |
89 | edge_map[std::make_pair(u, v)] = true; | |
90 | local_edges++; | |
91 | } else { | |
92 | tossed++; | |
93 | ||
94 | // special case - if both u and v are on same | |
95 | // proc, ++ twice, since we divide by two (to | |
96 | // cover the two process case) | |
97 | if (distrib(u) == id && distrib(v) == id) | |
98 | tossed++; | |
99 | } | |
100 | } | |
101 | generated++; | |
102 | ||
103 | } while (generated < m); | |
104 | tossed = all_reduce(pg, tossed, boost::parallel::sum<vertices_size_type>()); | |
105 | generated -= (tossed / 2); | |
106 | } while (generated < m); | |
107 | // NGE - Asking for more than n^2 edges will result in an infinite loop here | |
108 | // Asking for a value too close to n^2 edges may as well | |
109 | ||
110 | values.reserve(local_edges); | |
111 | typename std::map<value_type, bool>::reverse_iterator em_end = edge_map.rend(); | |
112 | for (typename std::map<value_type, bool>::reverse_iterator em_i = edge_map.rbegin(); | |
113 | em_i != em_end ; | |
114 | ++em_i) { | |
115 | values.push_back(em_i->first); | |
116 | } | |
117 | ||
118 | current = values.back(); | |
119 | values.pop_back(); | |
120 | } | |
121 | ||
122 | reference operator*() const { return current; } | |
123 | pointer operator->() const { return ¤t; } | |
124 | ||
125 | scalable_rmat_iterator& operator++() | |
126 | { | |
127 | if (!values.empty()) { | |
128 | current = values.back(); | |
129 | values.pop_back(); | |
130 | } else | |
131 | done = true; | |
132 | ||
133 | return *this; | |
134 | } | |
135 | ||
136 | scalable_rmat_iterator operator++(int) | |
137 | { | |
138 | scalable_rmat_iterator temp(*this); | |
139 | ++(*this); | |
140 | return temp; | |
141 | } | |
142 | ||
143 | bool operator==(const scalable_rmat_iterator& other) const | |
144 | { | |
145 | return values.empty() && other.values.empty() && done && other.done; | |
146 | } | |
147 | ||
148 | bool operator!=(const scalable_rmat_iterator& other) const | |
149 | { return !(*this == other); } | |
150 | ||
151 | private: | |
152 | ||
153 | // Parameters | |
154 | shared_ptr<uniform_01<RandomGenerator> > gen; | |
155 | ||
156 | // Internal data structures | |
157 | std::vector<value_type> values; | |
158 | value_type current; | |
159 | bool done; | |
160 | }; | |
161 | ||
162 | } // end namespace boost | |
163 | ||
164 | #endif // BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP |