// 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/assert.hpp> | |
#include <boost/graph/parallel/algorithm.hpp> | |
#include <boost/graph/parallel/process_group.hpp> | |
#include <math.h> | |
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) | |
{ | |
BOOST_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(log(double(n))/log(2.))); | |
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; | |
boost::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 |