1 // Copyright 2004, 2005 The Trustees of Indiana University.
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)
7 // Authors: Nick Edmonds
9 #ifndef BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
10 #define BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
16 #include <boost/assert.hpp>
17 #include <boost/graph/parallel/algorithm.hpp>
18 #include <boost/graph/parallel/process_group.hpp>
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
28 template<typename ProcessGroup, typename Distribution,
29 typename RandomGenerator, typename Graph>
30 class scalable_rmat_iterator
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;
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;
43 // No argument constructor, set to terminating condition
44 scalable_rmat_iterator()
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)
55 BOOST_ASSERT(a + b + c + d == 1);
56 int id = process_id(pg);
58 this->gen.reset(new uniform_01<RandomGenerator>(gen));
60 std::vector<vertices_size_type> vertexPermutation;
62 generate_permutation_vector(gen, vertexPermutation, n);
64 int SCALE = int(floor(log(double(n))/log(2.)));
65 boost::uniform_01<RandomGenerator> prob(gen);
67 std::map<value_type, bool> edge_map;
69 edges_size_type generated = 0, local_edges = 0;
71 edges_size_type tossed = 0;
73 vertices_size_type u, v;
74 boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
76 if (permute_vertices) {
77 u = vertexPermutation[u];
78 v = vertexPermutation[v];
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)
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;
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)
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
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();
115 values.push_back(em_i->first);
118 current = values.back();
122 reference operator*() const { return current; }
123 pointer operator->() const { return ¤t; }
125 scalable_rmat_iterator& operator++()
127 if (!values.empty()) {
128 current = values.back();
136 scalable_rmat_iterator operator++(int)
138 scalable_rmat_iterator temp(*this);
143 bool operator==(const scalable_rmat_iterator& other) const
145 return values.empty() && other.values.empty() && done && other.done;
148 bool operator!=(const scalable_rmat_iterator& other) const
149 { return !(*this == other); }
154 shared_ptr<uniform_01<RandomGenerator> > gen;
156 // Internal data structures
157 std::vector<value_type> values;
162 } // end namespace boost
164 #endif // BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP