using boost::uniform_01;
// Returns floor(log_2(n)), and -1 when n is 0
-template <typename IntegerType>
-inline int int_log2(IntegerType n) {
- int l = 0;
- while (n > 0) {++l; n >>= 1;}
- return l - 1;
+template < typename IntegerType > inline int int_log2(IntegerType n)
+{
+ int l = 0;
+ while (n > 0)
+ {
+ ++l;
+ n >>= 1;
+ }
+ return l - 1;
}
-struct keep_all_edges {
- template <typename T>
- bool operator()(const T&, const T&) { return true; }
+struct keep_all_edges
+{
+ template < typename T > bool operator()(const T&, const T&) { return true; }
};
-template <typename Distribution, typename ProcessId>
-struct keep_local_edges {
+template < typename Distribution, typename ProcessId > struct keep_local_edges
+{
- keep_local_edges(const Distribution& distrib, const ProcessId& id)
+ keep_local_edges(const Distribution& distrib, const ProcessId& id)
: distrib(distrib), id(id)
- { }
+ {
+ }
- template <typename T>
- bool operator()(const T& x, const T& y)
- { return distrib(x) == id || distrib(y) == id; }
+ template < typename T > bool operator()(const T& x, const T& y)
+ {
+ return distrib(x) == id || distrib(y) == id;
+ }
private:
- const Distribution& distrib;
- const ProcessId& id;
+ const Distribution& distrib;
+ const ProcessId& id;
};
-template <typename RandomGenerator, typename T>
-void
-generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n)
+template < typename RandomGenerator, typename T >
+void generate_permutation_vector(
+ RandomGenerator& gen, std::vector< T >& vertexPermutation, T n)
{
- using boost::uniform_int;
+ using boost::uniform_int;
- vertexPermutation.resize(n);
+ vertexPermutation.resize(n);
- // Generate permutation map of vertex numbers
- uniform_int<T> rand_vertex(0, n-1);
- for (T i = 0; i < n; ++i)
- vertexPermutation[i] = i;
+ // Generate permutation map of vertex numbers
+ uniform_int< T > rand_vertex(0, n - 1);
+ for (T i = 0; i < n; ++i)
+ vertexPermutation[i] = i;
- // Can't use std::random_shuffle unless we create another (synchronized) PRNG
- for (T i = 0; i < n; ++i)
- std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
+ // Can't use std::random_shuffle unless we create another (synchronized)
+ // PRNG
+ for (T i = 0; i < n; ++i)
+ std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
}
-template <typename RandomGenerator, typename T>
-std::pair<T,T>
-generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
- unsigned int SCALE, double a, double b, double c, double d)
+template < typename RandomGenerator, typename T >
+std::pair< T, T > generate_edge(
+ shared_ptr< uniform_01< RandomGenerator > > prob, T n, unsigned int SCALE,
+ double a, double b, double c, double d)
{
- T u = 0, v = 0;
- T step = n/2;
- for (unsigned int j = 0; j < SCALE; ++j) {
- double p = (*prob)();
-
- if (p < a)
- ;
- else if (p >= a && p < a + b)
- v += step;
- else if (p >= a + b && p < a + b + c)
- u += step;
- else { // p > a + b + c && p < a + b + c + d
- u += step;
- v += step;
- }
+ T u = 0, v = 0;
+ T step = n / 2;
+ for (unsigned int j = 0; j < SCALE; ++j)
+ {
+ double p = (*prob)();
+
+ if (p < a)
+ ;
+ else if (p >= a && p < a + b)
+ v += step;
+ else if (p >= a + b && p < a + b + c)
+ u += step;
+ else
+ { // p > a + b + c && p < a + b + c + d
+ u += step;
+ v += step;
+ }
- step /= 2;
+ step /= 2;
- // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
- // The maximum change in any given value should be less than 10%
- a *= 0.9 + 0.2 * (*prob)();
- b *= 0.9 + 0.2 * (*prob)();
- c *= 0.9 + 0.2 * (*prob)();
- d *= 0.9 + 0.2 * (*prob)();
+ // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
+ // The maximum change in any given value should be less than 10%
+ a *= 0.9 + 0.2 * (*prob)();
+ b *= 0.9 + 0.2 * (*prob)();
+ c *= 0.9 + 0.2 * (*prob)();
+ d *= 0.9 + 0.2 * (*prob)();
- double S = a + b + c + d;
+ double S = a + b + c + d;
- a /= S; b /= S; c /= S;
- // d /= S;
- // Ensure all values add up to 1, regardless of floating point errors
- d = 1. - a - b - c;
- }
+ a /= S;
+ b /= S;
+ c /= S;
+ // d /= S;
+ // Ensure all values add up to 1, regardless of floating point errors
+ d = 1. - a - b - c;
+ }
- return std::make_pair(u, v);
+ return std::make_pair(u, v);
}
-namespace boost {
+namespace boost
+{
- /*
- Chakrabarti's R-MAT scale free generator.
+/*
+ Chakrabarti's R-MAT scale free generator.
- For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
- unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
- generator may be unable to generate sufficient unique edges
+ For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
+ unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
+ generator may be unable to generate sufficient unique edges
- To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
- */
+ To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
+*/
- template<typename RandomGenerator, typename Graph>
- class 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;
+template < typename RandomGenerator, typename Graph > class 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:
+public:
typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef std::pair< vertices_size_type, vertices_size_type > value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
- rmat_iterator()
- : gen(), edge(0) { }
+ rmat_iterator() : gen(), edge(0) {}
// Initialize for edge generation
- rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool permute_vertices = true)
- : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
- permute_vertices(permute_vertices),
- SCALE(int_log2(n))
+ rmat_iterator(RandomGenerator& gen, vertices_size_type n, edges_size_type m,
+ double a, double b, double c, double d, bool permute_vertices = true)
+ : gen()
+ , n(n)
+ , a(a)
+ , b(b)
+ , c(c)
+ , d(d)
+ , edge(m)
+ , permute_vertices(permute_vertices)
+ , SCALE(int_log2(n))
{
- this->gen.reset(new uniform_01<RandomGenerator>(gen));
+ this->gen.reset(new uniform_01< RandomGenerator >(gen));
- // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c +
+ // d, 1., 1.e-5));
- if (permute_vertices)
- generate_permutation_vector(gen, vertexPermutation, n);
+ if (permute_vertices)
+ generate_permutation_vector(gen, vertexPermutation, n);
- // TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph
+ // TODO: Generate the entire adjacency matrix then "Clip and flip" if
+ // undirected graph
- // Generate the first edge
- vertices_size_type u, v;
- boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
+ // Generate the first edge
+ vertices_size_type u, v;
+ boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
- if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
- vertexPermutation[v]);
- else
- current = std::make_pair(u, v);
+ if (permute_vertices)
+ current
+ = std::make_pair(vertexPermutation[u], vertexPermutation[v]);
+ else
+ current = std::make_pair(u, v);
- --edge;
+ --edge;
}
reference operator*() const { return current; }
rmat_iterator& operator++()
{
- vertices_size_type u, v;
- boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
+ vertices_size_type u, v;
+ boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
- if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
- vertexPermutation[v]);
- else
- current = std::make_pair(u, v);
+ if (permute_vertices)
+ current
+ = std::make_pair(vertexPermutation[u], vertexPermutation[v]);
+ else
+ current = std::make_pair(u, v);
- --edge;
+ --edge;
- return *this;
+ return *this;
}
rmat_iterator operator++(int)
{
- rmat_iterator temp(*this);
- ++(*this);
- return temp;
+ rmat_iterator temp(*this);
+ ++(*this);
+ return temp;
}
bool operator==(const rmat_iterator& other) const
{
- return edge == other.edge;
+ return edge == other.edge;
}
bool operator!=(const rmat_iterator& other) const
- { return !(*this == other); }
-
- private:
+ {
+ return !(*this == other);
+ }
+private:
// Parameters
- shared_ptr<uniform_01<RandomGenerator> > gen;
+ shared_ptr< uniform_01< RandomGenerator > > gen;
vertices_size_type n;
double a, b, c, d;
int edge;
int SCALE;
// Internal data structures
- std::vector<vertices_size_type> vertexPermutation;
+ std::vector< vertices_size_type > vertexPermutation;
value_type current;
- };
+};
- // Sorted version for CSR
- template <typename T>
- struct sort_pair {
- bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
+// Sorted version for CSR
+template < typename T > struct sort_pair
+{
+ bool operator()(const std::pair< T, T >& x, const std::pair< T, T >& y)
{
- if (x.first == y.first)
- return x.second > y.second;
- else
- return x.first > y.first;
+ if (x.first == y.first)
+ return x.second > y.second;
+ else
+ return x.first > y.first;
}
- };
+};
- template<typename RandomGenerator, typename Graph,
- typename EdgePredicate = keep_all_edges>
- class sorted_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;
+template < typename RandomGenerator, typename Graph,
+ typename EdgePredicate = keep_all_edges >
+class sorted_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:
+public:
typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef std::pair< vertices_size_type, vertices_size_type > value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
sorted_rmat_iterator()
- : gen(), values(sort_pair<vertices_size_type>()), done(true)
- { }
+ : gen(), values(sort_pair< vertices_size_type >()), done(true)
+ {
+ }
// Initialize for edge generation
sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool permute_vertices = true,
- EdgePredicate ep = keep_all_edges())
- : gen(), permute_vertices(permute_vertices),
- values(sort_pair<vertices_size_type>()), done(false)
+ edges_size_type m, double a, double b, double c, double d,
+ bool permute_vertices = true, EdgePredicate ep = keep_all_edges())
+ : gen()
+ , permute_vertices(permute_vertices)
+ , values(sort_pair< vertices_size_type >())
+ , done(false)
{
- // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c +
+ // d, 1., 1.e-5));
- this->gen.reset(new uniform_01<RandomGenerator>(gen));
+ this->gen.reset(new uniform_01< RandomGenerator >(gen));
- std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
- generate_permutation_vector(gen, vertexPermutation, n);
+ std::vector< vertices_size_type > vertexPermutation;
+ if (permute_vertices)
+ generate_permutation_vector(gen, vertexPermutation, n);
- // TODO: "Clip and flip" if undirected graph
- int SCALE = int_log2(n);
+ // TODO: "Clip and flip" if undirected graph
+ int SCALE = int_log2(n);
- for (edges_size_type i = 0; i < m; ++i) {
+ for (edges_size_type i = 0; i < m; ++i)
+ {
- vertices_size_type u, v;
- boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
+ vertices_size_type u, v;
+ boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
- if (permute_vertices) {
- if (ep(vertexPermutation[u], vertexPermutation[v]))
- values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
- } else {
- if (ep(u, v))
- values.push(std::make_pair(u, v));
+ if (permute_vertices)
+ {
+ if (ep(vertexPermutation[u], vertexPermutation[v]))
+ values.push(std::make_pair(
+ vertexPermutation[u], vertexPermutation[v]));
+ }
+ else
+ {
+ if (ep(u, v))
+ values.push(std::make_pair(u, v));
+ }
}
- }
-
- current = values.top();
- values.pop();
+ current = values.top();
+ values.pop();
}
reference operator*() const { return current; }
sorted_rmat_iterator& operator++()
{
- if (!values.empty()) {
- current = values.top();
- values.pop();
- } else
- done = true;
+ if (!values.empty())
+ {
+ current = values.top();
+ values.pop();
+ }
+ else
+ done = true;
- return *this;
+ return *this;
}
sorted_rmat_iterator operator++(int)
{
- sorted_rmat_iterator temp(*this);
- ++(*this);
- return temp;
+ sorted_rmat_iterator temp(*this);
+ ++(*this);
+ return temp;
}
bool operator==(const sorted_rmat_iterator& other) const
{
- return values.empty() && other.values.empty() && done && other.done;
+ return values.empty() && other.values.empty() && done && other.done;
}
bool operator!=(const sorted_rmat_iterator& other) const
- { return !(*this == other); }
-
- private:
+ {
+ return !(*this == other);
+ }
+private:
// Parameters
- shared_ptr<uniform_01<RandomGenerator> > gen;
+ shared_ptr< uniform_01< RandomGenerator > > gen;
bool permute_vertices;
// Internal data structures
- std::priority_queue<value_type, std::vector<value_type>, sort_pair<vertices_size_type> > values;
+ std::priority_queue< value_type, std::vector< value_type >,
+ sort_pair< vertices_size_type > >
+ values;
value_type current;
- bool done;
- };
-
+ bool done;
+};
- // This version is slow but guarantees unique edges
- template<typename RandomGenerator, typename Graph,
- typename EdgePredicate = keep_all_edges>
- class unique_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;
+// This version is slow but guarantees unique edges
+template < typename RandomGenerator, typename Graph,
+ typename EdgePredicate = keep_all_edges >
+class unique_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:
+public:
typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
+ typedef std::pair< vertices_size_type, vertices_size_type > value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
- unique_rmat_iterator()
- : gen(), done(true)
- { }
+ unique_rmat_iterator() : gen(), done(true) {}
// Initialize for edge generation
unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool permute_vertices = true,
- EdgePredicate ep = keep_all_edges())
- : gen(), done(false)
+ edges_size_type m, double a, double b, double c, double d,
+ bool permute_vertices = true, EdgePredicate ep = keep_all_edges())
+ : gen(), done(false)
{
- // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
-
- 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_log2(n);
-
- std::map<value_type, bool> edge_map;
-
- edges_size_type edges = 0;
- do {
- vertices_size_type u, v;
- boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
-
- // 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 (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
- edge_map[std::make_pair(u, v)] = true;
-
- if (permute_vertices) {
- if (ep(vertexPermutation[u], vertexPermutation[v]))
- values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
- } else {
- if (ep(u, v))
- values.push_back(std::make_pair(u, v));
- }
-
- edges++;
- }
- } while (edges < 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
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c +
+ // d, 1., 1.e-5));
+
+ 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_log2(n);
+
+ std::map< value_type, bool > edge_map;
+
+ edges_size_type edges = 0;
+ do
+ {
+ vertices_size_type u, v;
+ boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
+
+ // 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 (edge_map.find(std::make_pair(u, v)) == edge_map.end())
+ {
+ edge_map[std::make_pair(u, v)] = true;
+
+ if (permute_vertices)
+ {
+ if (ep(vertexPermutation[u], vertexPermutation[v]))
+ values.push_back(std::make_pair(
+ vertexPermutation[u], vertexPermutation[v]));
+ }
+ else
+ {
+ if (ep(u, v))
+ values.push_back(std::make_pair(u, v));
+ }
+
+ edges++;
+ }
+ } while (edges < 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
- current = values.back();
- values.pop_back();
+ current = values.back();
+ values.pop_back();
}
reference operator*() const { return current; }
unique_rmat_iterator& operator++()
{
- if (!values.empty()) {
- current = values.back();
- values.pop_back();
- } else
- done = true;
+ if (!values.empty())
+ {
+ current = values.back();
+ values.pop_back();
+ }
+ else
+ done = true;
- return *this;
+ return *this;
}
unique_rmat_iterator operator++(int)
{
- unique_rmat_iterator temp(*this);
- ++(*this);
- return temp;
+ unique_rmat_iterator temp(*this);
+ ++(*this);
+ return temp;
}
bool operator==(const unique_rmat_iterator& other) const
{
- return values.empty() && other.values.empty() && done && other.done;
+ return values.empty() && other.values.empty() && done && other.done;
}
bool operator!=(const unique_rmat_iterator& other) const
- { return !(*this == other); }
-
- private:
+ {
+ return !(*this == other);
+ }
+private:
// Parameters
- shared_ptr<uniform_01<RandomGenerator> > gen;
+ shared_ptr< uniform_01< RandomGenerator > > gen;
// Internal data structures
- std::vector<value_type> values;
- value_type current;
- bool done;
- };
-
- // This version is slow but guarantees unique edges
- template<typename RandomGenerator, typename Graph,
- typename EdgePredicate = keep_all_edges>
- class sorted_unique_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:
+ std::vector< value_type > values;
+ value_type current;
+ bool done;
+};
+
+// This version is slow but guarantees unique edges
+template < typename RandomGenerator, typename Graph,
+ typename EdgePredicate = keep_all_edges >
+class sorted_unique_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 std::pair< vertices_size_type, vertices_size_type > value_type;
typedef const value_type& reference;
typedef const value_type* pointer;
typedef std::ptrdiff_t difference_type; // Not used
// No argument constructor, set to terminating condition
sorted_unique_rmat_iterator()
- : gen(), values(sort_pair<vertices_size_type>()), done(true) { }
+ : gen(), values(sort_pair< vertices_size_type >()), done(true)
+ {
+ }
// Initialize for edge generation
sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool bidirectional = false,
- bool permute_vertices = true,
- EdgePredicate ep = keep_all_edges())
- : gen(), bidirectional(bidirectional),
- values(sort_pair<vertices_size_type>()), done(false)
+ edges_size_type m, double a, double b, double c, double d,
+ bool bidirectional = false, bool permute_vertices = true,
+ EdgePredicate ep = keep_all_edges())
+ : gen()
+ , bidirectional(bidirectional)
+ , values(sort_pair< vertices_size_type >())
+ , done(false)
{
- // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
-
- 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_log2(n);
-
- std::map<value_type, bool> edge_map;
-
- edges_size_type edges = 0;
- do {
-
- vertices_size_type u, v;
- boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
-
- if (bidirectional) {
- if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
- edge_map[std::make_pair(u, v)] = true;
- edge_map[std::make_pair(v, u)] = true;
-
- if (ep(u, v)) {
- if (permute_vertices) {
- values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
- values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u]));
- } else {
- values.push(std::make_pair(u, v));
- values.push(std::make_pair(v, u));
- }
- }
-
- ++edges;
- }
- } else {
- // 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 (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
- edge_map[std::make_pair(u, v)] = true;
-
- if (permute_vertices) {
- if (ep(vertexPermutation[u], vertexPermutation[v]))
- values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
- } else {
- if (ep(u, v))
- values.push(std::make_pair(u, v));
+ // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c +
+ // d, 1., 1.e-5));
+
+ 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_log2(n);
+
+ std::map< value_type, bool > edge_map;
+
+ edges_size_type edges = 0;
+ do
+ {
+
+ vertices_size_type u, v;
+ boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
+
+ if (bidirectional)
+ {
+ if (edge_map.find(std::make_pair(u, v)) == edge_map.end())
+ {
+ edge_map[std::make_pair(u, v)] = true;
+ edge_map[std::make_pair(v, u)] = true;
+
+ if (ep(u, v))
+ {
+ if (permute_vertices)
+ {
+ values.push(std::make_pair(
+ vertexPermutation[u], vertexPermutation[v]));
+ values.push(std::make_pair(
+ vertexPermutation[v], vertexPermutation[u]));
+ }
+ else
+ {
+ values.push(std::make_pair(u, v));
+ values.push(std::make_pair(v, u));
+ }
+ }
+
+ ++edges;
+ }
+ }
+ else
+ {
+ // 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 (edge_map.find(std::make_pair(u, v)) == edge_map.end())
+ {
+ edge_map[std::make_pair(u, v)] = true;
+
+ if (permute_vertices)
+ {
+ if (ep(vertexPermutation[u], vertexPermutation[v]))
+ values.push(std::make_pair(
+ vertexPermutation[u], vertexPermutation[v]));
+ }
+ else
+ {
+ if (ep(u, v))
+ values.push(std::make_pair(u, v));
+ }
+
+ ++edges;
+ }
}
- ++edges;
- }
- }
-
- } while (edges < 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
+ } while (edges < 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
- current = values.top();
- values.pop();
+ current = values.top();
+ values.pop();
}
reference operator*() const { return current; }
sorted_unique_rmat_iterator& operator++()
{
- if (!values.empty()) {
- current = values.top();
- values.pop();
- } else
- done = true;
+ if (!values.empty())
+ {
+ current = values.top();
+ values.pop();
+ }
+ else
+ done = true;
- return *this;
+ return *this;
}
sorted_unique_rmat_iterator operator++(int)
{
- sorted_unique_rmat_iterator temp(*this);
- ++(*this);
- return temp;
+ sorted_unique_rmat_iterator temp(*this);
+ ++(*this);
+ return temp;
}
bool operator==(const sorted_unique_rmat_iterator& other) const
{
- return values.empty() && other.values.empty() && done && other.done;
+ return values.empty() && other.values.empty() && done && other.done;
}
bool operator!=(const sorted_unique_rmat_iterator& other) const
- { return !(*this == other); }
-
- private:
+ {
+ return !(*this == other);
+ }
+private:
// Parameters
- shared_ptr<uniform_01<RandomGenerator> > gen;
- bool bidirectional;
+ shared_ptr< uniform_01< RandomGenerator > > gen;
+ bool bidirectional;
// Internal data structures
- std::priority_queue<value_type, std::vector<value_type>,
- sort_pair<vertices_size_type> > values;
+ std::priority_queue< value_type, std::vector< value_type >,
+ sort_pair< vertices_size_type > >
+ values;
value_type current;
- bool done;
- };
+ bool done;
+};
} // end namespace boost
-#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/rmat_graph_generator.hpp>)
+#include BOOST_GRAPH_MPI_INCLUDE(< boost / graph / distributed / rmat_graph_generator.hpp >)
#endif // BOOST_GRAPH_RMAT_GENERATOR_HPP
projects / ceph.git / blobdiff