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 scalable_rmat_iterator()44 scalable_rmat_iterator() 45 : gen(), done(true) 46 { } 47 48 // Initialize for edge generation scalable_rmat_iterator(ProcessGroup pg,Distribution distrib,RandomGenerator & gen,vertices_size_type n,edges_size_type m,double a,double b,double c,double d,bool permute_vertices=true)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 operator *() const122 reference operator*() const { return current; } operator ->() const123 pointer operator->() const { return ¤t; } 124 operator ++()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 operator ++(int)136 scalable_rmat_iterator operator++(int) 137 { 138 scalable_rmat_iterator temp(*this); 139 ++(*this); 140 return temp; 141 } 142 operator ==(const scalable_rmat_iterator & other) const143 bool operator==(const scalable_rmat_iterator& other) const 144 { 145 return values.empty() && other.values.empty() && done && other.done; 146 } 147 operator !=(const scalable_rmat_iterator & other) const148 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 165