| // Copyright 2004, 2005 The Trustees of Indiana University. |
| |
| // Use, modification and distribution is subject to the Boost Software |
| // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Nick Edmonds |
| // Andrew Lumsdaine |
| #ifndef BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP |
| #define BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP |
| |
| #ifndef BOOST_GRAPH_USE_MPI |
| #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" |
| #endif |
| |
| #include <boost/graph/parallel/algorithm.hpp> |
| #include <boost/graph/parallel/process_group.hpp> |
| |
| namespace boost { |
| |
| // Memory-scalable (amount of memory required will scale down |
| // linearly as the number of processes increases) generator, which |
| // requires an MPI process group. Run-time is slightly worse than |
| // the unique rmat generator. Edge list generated is sorted and |
| // unique. |
| template<typename ProcessGroup, typename Distribution, |
| typename RandomGenerator, typename Graph> |
| class scalable_rmat_iterator |
| { |
| typedef typename graph_traits<Graph>::directed_category directed_category; |
| typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; |
| typedef typename graph_traits<Graph>::edges_size_type edges_size_type; |
| |
| public: |
| typedef std::input_iterator_tag iterator_category; |
| typedef std::pair<vertices_size_type, vertices_size_type> value_type; |
| typedef const value_type& reference; |
| typedef const value_type* pointer; |
| typedef void difference_type; |
| |
| // No argument constructor, set to terminating condition |
| scalable_rmat_iterator() |
| : gen(), done(true) |
| { } |
| |
| // 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) |
| : gen(), done(false) |
| { |
| assert(a + b + c + d == 1); |
| int id = process_id(pg); |
| |
| this->gen.reset(new uniform_01<RandomGenerator>(gen)); |
| |
| std::vector<vertices_size_type> vertexPermutation; |
| if (permute_vertices) |
| generate_permutation_vector(gen, vertexPermutation, n); |
| |
| int SCALE = int(floor(log2(n))); |
| boost::uniform_01<RandomGenerator> prob(gen); |
| |
| std::map<value_type, bool> edge_map; |
| |
| edges_size_type generated = 0, local_edges = 0; |
| do { |
| edges_size_type tossed = 0; |
| do { |
| vertices_size_type u, v; |
| tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d); |
| |
| if (permute_vertices) { |
| u = vertexPermutation[u]; |
| v = vertexPermutation[v]; |
| } |
| |
| // Lowest vertex number always comes first (this |
| // means we don't have to worry about i->j and j->i |
| // being in the edge list) |
| if (u > v && is_same<directed_category, undirected_tag>::value) |
| std::swap(u, v); |
| |
| if (distrib(u) == id || distrib(v) == id) { |
| if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) { |
| edge_map[std::make_pair(u, v)] = true; |
| local_edges++; |
| } else { |
| tossed++; |
| |
| // special case - if both u and v are on same |
| // proc, ++ twice, since we divide by two (to |
| // cover the two process case) |
| if (distrib(u) == id && distrib(v) == id) |
| tossed++; |
| } |
| } |
| generated++; |
| |
| } while (generated < m); |
| tossed = all_reduce(pg, tossed, boost::parallel::sum<vertices_size_type>()); |
| generated -= (tossed / 2); |
| } while (generated < m); |
| // NGE - Asking for more than n^2 edges will result in an infinite loop here |
| // Asking for a value too close to n^2 edges may as well |
| |
| values.reserve(local_edges); |
| typename std::map<value_type, bool>::reverse_iterator em_end = edge_map.rend(); |
| for (typename std::map<value_type, bool>::reverse_iterator em_i = edge_map.rbegin(); |
| em_i != em_end ; |
| ++em_i) { |
| values.push_back(em_i->first); |
| } |
| |
| current = values.back(); |
| values.pop_back(); |
| } |
| |
| reference operator*() const { return current; } |
| pointer operator->() const { return ¤t; } |
| |
| scalable_rmat_iterator& operator++() |
| { |
| if (!values.empty()) { |
| current = values.back(); |
| values.pop_back(); |
| } else |
| done = true; |
| |
| return *this; |
| } |
| |
| scalable_rmat_iterator operator++(int) |
| { |
| scalable_rmat_iterator temp(*this); |
| ++(*this); |
| return temp; |
| } |
| |
| bool operator==(const scalable_rmat_iterator& other) const |
| { |
| return values.empty() && other.values.empty() && done && other.done; |
| } |
| |
| bool operator!=(const scalable_rmat_iterator& other) const |
| { return !(*this == other); } |
| |
| private: |
| |
| // Parameters |
| shared_ptr<uniform_01<RandomGenerator> > gen; |
| |
| // Internal data structures |
| std::vector<value_type> values; |
| value_type current; |
| bool done; |
| }; |
| |
| } // end namespace boost |
| |
| #endif // BOOST_GRAPH_DISTRIBUTED_RMAT_GENERATOR_HPP |