Chris@16: // Copyright 2004, 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Nick Edmonds
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_RMAT_GENERATOR_HPP
Chris@16: #define BOOST_GRAPH_RMAT_GENERATOR_HPP
Chris@16: 
Chris@16: #include <math.h>
Chris@16: #include <iterator>
Chris@16: #include <utility>
Chris@16: #include <vector>
Chris@16: #include <queue>
Chris@16: #include <map>
Chris@16: #include <boost/shared_ptr.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/random/uniform_int.hpp>
Chris@16: #include <boost/random/uniform_01.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/type_traits/is_base_and_derived.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: // #include <boost/test/floating_point_comparison.hpp>
Chris@16: 
Chris@16: using boost::shared_ptr;
Chris@16: using boost::uniform_01;
Chris@16: 
Chris@16: // Returns floor(log_2(n)), and -1 when n is 0
Chris@16: template <typename IntegerType>
Chris@16: inline int int_log2(IntegerType n) {
Chris@16:   int l = 0;
Chris@16:   while (n > 0) {++l; n >>= 1;}
Chris@16:   return l - 1;
Chris@16: }
Chris@16: 
Chris@16: struct keep_all_edges {
Chris@16:   template <typename T>
Chris@16:   bool operator()(const T&, const T&) { return true; }
Chris@16: };
Chris@16: 
Chris@16: template <typename Distribution, typename ProcessId>
Chris@16: struct keep_local_edges {
Chris@16: 
Chris@16:   keep_local_edges(const Distribution& distrib, const ProcessId& id)
Chris@16:     : distrib(distrib), id(id)
Chris@16:   { }
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   bool operator()(const T& x, const T& y)
Chris@16:   { return distrib(x) == id || distrib(y) == id; }
Chris@16: 
Chris@16: private:
Chris@16:   const Distribution& distrib;
Chris@16:   const ProcessId&    id;
Chris@16: };
Chris@16: 
Chris@16: template <typename RandomGenerator, typename T>
Chris@16: void
Chris@16: generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n)
Chris@16: {
Chris@16:   using boost::uniform_int;
Chris@16: 
Chris@16:   vertexPermutation.resize(n);
Chris@16: 
Chris@16:   // Generate permutation map of vertex numbers
Chris@16:   uniform_int<T> rand_vertex(0, n-1);
Chris@16:   for (T i = 0; i < n; ++i)
Chris@16:     vertexPermutation[i] = i;
Chris@16: 
Chris@16:   // Can't use std::random_shuffle unless we create another (synchronized) PRNG
Chris@16:   for (T i = 0; i < n; ++i)
Chris@16:     std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
Chris@16: }
Chris@16: 
Chris@16: template <typename RandomGenerator, typename T>
Chris@16: std::pair<T,T>
Chris@16: generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
Chris@16:               unsigned int SCALE, double a, double b, double c, double d)
Chris@16: {
Chris@16:   T u = 0, v = 0;
Chris@16:   T step = n/2;
Chris@16:   for (unsigned int j = 0; j < SCALE; ++j) {
Chris@16:     double p = (*prob)();
Chris@16: 
Chris@16:     if (p < a)
Chris@16:       ;
Chris@16:     else if (p >= a && p < a + b)
Chris@16:       v += step;
Chris@16:     else if (p >= a + b && p < a + b + c)
Chris@16:       u += step;
Chris@16:     else { // p > a + b + c && p < a + b + c + d
Chris@16:       u += step;
Chris@16:       v += step;
Chris@16:     }
Chris@16: 
Chris@16:     step /= 2;
Chris@16: 
Chris@16:     // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
Chris@16:     // The maximum change in any given value should be less than 10%
Chris@16:     a *= 0.9 + 0.2 * (*prob)();
Chris@16:     b *= 0.9 + 0.2 * (*prob)();
Chris@16:     c *= 0.9 + 0.2 * (*prob)();
Chris@16:     d *= 0.9 + 0.2 * (*prob)();
Chris@16: 
Chris@16:     double S = a + b + c + d;
Chris@16: 
Chris@16:     a /= S; b /= S; c /= S;
Chris@16:     // d /= S;
Chris@16:     // Ensure all values add up to 1, regardless of floating point errors
Chris@16:     d = 1. - a - b - c;
Chris@16:   }
Chris@16: 
Chris@16:   return std::make_pair(u, v);
Chris@16: }
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   /*
Chris@16:     Chakrabarti's R-MAT scale free generator.
Chris@16: 
Chris@16:     For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
Chris@16:     unique_rmat_iterator 'm' << 'n^2'.  If 'm' is too close to 'n^2' the
Chris@16:     generator may be unable to generate sufficient unique edges
Chris@16: 
Chris@16:     To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
Chris@16:   */
Chris@16: 
Chris@16:   template<typename RandomGenerator, typename Graph>
Chris@16:   class rmat_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::input_iterator_tag iterator_category;
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:     typedef const value_type& reference;
Chris@16:     typedef const value_type* pointer;
Chris@16:     typedef std::ptrdiff_t difference_type; // Not used
Chris@16: 
Chris@16:     // No argument constructor, set to terminating condition
Chris@16:     rmat_iterator()
Chris@16:       : gen(), edge(0) { }
Chris@16: 
Chris@16:     // Initialize for edge generation
Chris@16:     rmat_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                   edges_size_type m, double a, double b, double c,
Chris@16:                   double d, bool permute_vertices = true)
Chris@16:       : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
Chris@16:         permute_vertices(permute_vertices),
Chris@16:         SCALE(int_log2(n))
Chris@16: 
Chris@16:     {
Chris@16:       this->gen.reset(new uniform_01<RandomGenerator>(gen));
Chris@16: 
Chris@16:       // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
Chris@16: 
Chris@16:       if (permute_vertices)
Chris@16:         generate_permutation_vector(gen, vertexPermutation, n);
Chris@16: 
Chris@16:       // TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph
Chris@16: 
Chris@16:       // Generate the first edge
Chris@16:       vertices_size_type u, v;
Chris@16:       boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:       if (permute_vertices)
Chris@16:         current = std::make_pair(vertexPermutation[u],
Chris@16:                                  vertexPermutation[v]);
Chris@16:       else
Chris@16:         current = std::make_pair(u, v);
Chris@16: 
Chris@16:       --edge;
Chris@16:     }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16: 
Chris@16:     rmat_iterator& operator++()
Chris@16:     {
Chris@16:       vertices_size_type u, v;
Chris@16:       boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:       if (permute_vertices)
Chris@16:         current = std::make_pair(vertexPermutation[u],
Chris@16:                                  vertexPermutation[v]);
Chris@16:       else
Chris@16:         current = std::make_pair(u, v);
Chris@16: 
Chris@16:       --edge;
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     rmat_iterator operator++(int)
Chris@16:     {
Chris@16:       rmat_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const rmat_iterator& other) const
Chris@16:     {
Chris@16:       return edge == other.edge;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const rmat_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     // Parameters
Chris@16:     shared_ptr<uniform_01<RandomGenerator> > gen;
Chris@16:     vertices_size_type n;
Chris@16:     double a, b, c, d;
Chris@16:     int edge;
Chris@16:     bool permute_vertices;
Chris@16:     int SCALE;
Chris@16: 
Chris@16:     // Internal data structures
Chris@16:     std::vector<vertices_size_type> vertexPermutation;
Chris@16:     value_type current;
Chris@16:   };
Chris@16: 
Chris@16:   // Sorted version for CSR
Chris@16:   template <typename T>
Chris@16:   struct sort_pair {
Chris@16:     bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
Chris@16:     {
Chris@16:       if (x.first == y.first)
Chris@16:         return x.second > y.second;
Chris@16:       else
Chris@16:         return x.first > y.first;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template<typename RandomGenerator, typename Graph,
Chris@16:            typename EdgePredicate = keep_all_edges>
Chris@16:   class sorted_rmat_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::input_iterator_tag iterator_category;
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:     typedef const value_type& reference;
Chris@16:     typedef const value_type* pointer;
Chris@16:     typedef std::ptrdiff_t difference_type; // Not used
Chris@16: 
Chris@16:     // No argument constructor, set to terminating condition
Chris@16:     sorted_rmat_iterator()
Chris@16:       : gen(), values(sort_pair<vertices_size_type>()), done(true)
Chris@16:     { }
Chris@16: 
Chris@16:     // Initialize for edge generation
Chris@16:     sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                          edges_size_type m, double a, double b, double c,
Chris@16:                          double d, bool permute_vertices = true,
Chris@16:                          EdgePredicate ep = keep_all_edges())
Chris@16:       : gen(), permute_vertices(permute_vertices),
Chris@16:         values(sort_pair<vertices_size_type>()), done(false)
Chris@16: 
Chris@16:     {
Chris@16:       // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
Chris@16: 
Chris@16:       this->gen.reset(new uniform_01<RandomGenerator>(gen));
Chris@16: 
Chris@16:       std::vector<vertices_size_type> vertexPermutation;
Chris@16:       if (permute_vertices)
Chris@16:         generate_permutation_vector(gen, vertexPermutation, n);
Chris@16: 
Chris@16:       // TODO: "Clip and flip" if undirected graph
Chris@16:       int SCALE = int_log2(n);
Chris@16: 
Chris@16:       for (edges_size_type i = 0; i < m; ++i) {
Chris@16: 
Chris@16:         vertices_size_type u, v;
Chris@16:         boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:         if (permute_vertices) {
Chris@16:           if (ep(vertexPermutation[u], vertexPermutation[v]))
Chris@16:             values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
Chris@16:         } else {
Chris@16:           if (ep(u, v))
Chris@16:             values.push(std::make_pair(u, v));
Chris@16:         }
Chris@16: 
Chris@16:       }
Chris@16: 
Chris@16:       current = values.top();
Chris@16:       values.pop();
Chris@16:     }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16: 
Chris@16:     sorted_rmat_iterator& operator++()
Chris@16:     {
Chris@16:       if (!values.empty()) {
Chris@16:         current = values.top();
Chris@16:         values.pop();
Chris@16:       } else
Chris@16:         done = true;
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     sorted_rmat_iterator operator++(int)
Chris@16:     {
Chris@16:       sorted_rmat_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const sorted_rmat_iterator& other) const
Chris@16:     {
Chris@16:       return values.empty() && other.values.empty() && done && other.done;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const sorted_rmat_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     // Parameters
Chris@16:     shared_ptr<uniform_01<RandomGenerator> > gen;
Chris@16:     bool permute_vertices;
Chris@16: 
Chris@16:     // Internal data structures
Chris@16:     std::priority_queue<value_type, std::vector<value_type>, sort_pair<vertices_size_type> > values;
Chris@16:     value_type current;
Chris@16:     bool       done;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   // This version is slow but guarantees unique edges
Chris@16:   template<typename RandomGenerator, typename Graph,
Chris@16:            typename EdgePredicate = keep_all_edges>
Chris@16:   class unique_rmat_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::input_iterator_tag iterator_category;
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:     typedef const value_type& reference;
Chris@16:     typedef const value_type* pointer;
Chris@16:     typedef std::ptrdiff_t difference_type; // Not used
Chris@16: 
Chris@16:     // No argument constructor, set to terminating condition
Chris@16:     unique_rmat_iterator()
Chris@16:         : gen(), done(true)
Chris@16:     { }
Chris@16: 
Chris@16:     // Initialize for edge generation
Chris@16:     unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                          edges_size_type m, double a, double b, double c,
Chris@16:                          double d, bool permute_vertices = true,
Chris@16:                          EdgePredicate ep = keep_all_edges())
Chris@16:       : gen(), done(false)
Chris@16: 
Chris@16:     {
Chris@16:       // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
Chris@16: 
Chris@16:       this->gen.reset(new uniform_01<RandomGenerator>(gen));
Chris@16: 
Chris@16:       std::vector<vertices_size_type> vertexPermutation;
Chris@16:       if (permute_vertices)
Chris@16:         generate_permutation_vector(gen, vertexPermutation, n);
Chris@16: 
Chris@16:       int SCALE = int_log2(n);
Chris@16: 
Chris@16:       std::map<value_type, bool> edge_map;
Chris@16: 
Chris@16:       edges_size_type edges = 0;
Chris@16:       do {
Chris@16:         vertices_size_type u, v;
Chris@16:         boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:         // Lowest vertex number always comes first
Chris@16:         // (this means we don't have to worry about i->j and j->i being in the edge list)
Chris@16:         if (u > v && is_same<directed_category, undirected_tag>::value)
Chris@16:           std::swap(u, v);
Chris@16: 
Chris@16:         if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
Chris@16:           edge_map[std::make_pair(u, v)] = true;
Chris@16: 
Chris@16:           if (permute_vertices) {
Chris@16:             if (ep(vertexPermutation[u], vertexPermutation[v]))
Chris@16:               values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
Chris@16:           } else {
Chris@16:             if (ep(u, v))
Chris@16:               values.push_back(std::make_pair(u, v));
Chris@16:           }
Chris@16: 
Chris@16:           edges++;
Chris@16:         }
Chris@16:       } while (edges < m);
Chris@16:       // NGE - Asking for more than n^2 edges will result in an infinite loop here
Chris@16:       //       Asking for a value too close to n^2 edges may as well
Chris@16: 
Chris@16:       current = values.back();
Chris@16:       values.pop_back();
Chris@16:     }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16: 
Chris@16:     unique_rmat_iterator& operator++()
Chris@16:     {
Chris@16:       if (!values.empty()) {
Chris@16:         current = values.back();
Chris@16:         values.pop_back();
Chris@16:       } else
Chris@16:         done = true;
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     unique_rmat_iterator operator++(int)
Chris@16:     {
Chris@16:       unique_rmat_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const unique_rmat_iterator& other) const
Chris@16:     {
Chris@16:       return values.empty() && other.values.empty() && done && other.done;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const unique_rmat_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     // Parameters
Chris@16:     shared_ptr<uniform_01<RandomGenerator> > gen;
Chris@16: 
Chris@16:     // Internal data structures
Chris@16:     std::vector<value_type> values;
Chris@16:     value_type              current;
Chris@16:     bool                    done;
Chris@16:   };
Chris@16: 
Chris@16:   // This version is slow but guarantees unique edges
Chris@16:   template<typename RandomGenerator, typename Graph,
Chris@16:            typename EdgePredicate = keep_all_edges>
Chris@16:   class sorted_unique_rmat_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::input_iterator_tag iterator_category;
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:     typedef const value_type& reference;
Chris@16:     typedef const value_type* pointer;
Chris@16:     typedef std::ptrdiff_t difference_type; // Not used
Chris@16: 
Chris@16:     // No argument constructor, set to terminating condition
Chris@16:     sorted_unique_rmat_iterator()
Chris@16:       : gen(), values(sort_pair<vertices_size_type>()), done(true) { }
Chris@16: 
Chris@16:     // Initialize for edge generation
Chris@16:     sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
Chris@16:                                 edges_size_type m, double a, double b, double c,
Chris@16:                                 double d, bool bidirectional = false,
Chris@16:                                 bool permute_vertices = true,
Chris@16:                                 EdgePredicate ep = keep_all_edges())
Chris@16:       : gen(), bidirectional(bidirectional),
Chris@16:         values(sort_pair<vertices_size_type>()), done(false)
Chris@16: 
Chris@16:     {
Chris@16:       // BOOST_ASSERT(boost::test_tools::check_is_close(a + b + c + d, 1., 1.e-5));
Chris@16: 
Chris@16:       this->gen.reset(new uniform_01<RandomGenerator>(gen));
Chris@16: 
Chris@16:       std::vector<vertices_size_type> vertexPermutation;
Chris@16:       if (permute_vertices)
Chris@16:         generate_permutation_vector(gen, vertexPermutation, n);
Chris@16: 
Chris@16:       int SCALE = int_log2(n);
Chris@16: 
Chris@16:       std::map<value_type, bool> edge_map;
Chris@16: 
Chris@16:       edges_size_type edges = 0;
Chris@16:       do {
Chris@16: 
Chris@16:         vertices_size_type u, v;
Chris@16:         boost::tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);
Chris@16: 
Chris@16:         if (bidirectional) {
Chris@16:           if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
Chris@16:             edge_map[std::make_pair(u, v)] = true;
Chris@16:             edge_map[std::make_pair(v, u)] = true;
Chris@16: 
Chris@16:             if (ep(u, v)) {
Chris@16:               if (permute_vertices) {
Chris@16:                 values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
Chris@16:                 values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u]));
Chris@16:               } else {
Chris@16:                 values.push(std::make_pair(u, v));
Chris@16:                 values.push(std::make_pair(v, u));
Chris@16:               }
Chris@16:            }
Chris@16: 
Chris@16:             ++edges;
Chris@16:           }
Chris@16:         } else {
Chris@16:           // Lowest vertex number always comes first
Chris@16:           // (this means we don't have to worry about i->j and j->i being in the edge list)
Chris@16:           if (u > v && is_same<directed_category, undirected_tag>::value)
Chris@16:             std::swap(u, v);
Chris@16: 
Chris@16:           if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
Chris@16:             edge_map[std::make_pair(u, v)] = true;
Chris@16: 
Chris@16:             if (permute_vertices) {
Chris@16:               if (ep(vertexPermutation[u], vertexPermutation[v]))
Chris@16:                 values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
Chris@16:             } else {
Chris@16:               if (ep(u, v))
Chris@16:                 values.push(std::make_pair(u, v));
Chris@16:             }
Chris@16: 
Chris@16:             ++edges;
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:       } while (edges < m);
Chris@16:       // NGE - Asking for more than n^2 edges will result in an infinite loop here
Chris@16:       //       Asking for a value too close to n^2 edges may as well
Chris@16: 
Chris@16:       current = values.top();
Chris@16:       values.pop();
Chris@16:     }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16: 
Chris@16:     sorted_unique_rmat_iterator& operator++()
Chris@16:     {
Chris@16:       if (!values.empty()) {
Chris@16:         current = values.top();
Chris@16:         values.pop();
Chris@16:       } else
Chris@16:         done = true;
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     sorted_unique_rmat_iterator operator++(int)
Chris@16:     {
Chris@16:       sorted_unique_rmat_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const sorted_unique_rmat_iterator& other) const
Chris@16:     {
Chris@16:       return values.empty() && other.values.empty() && done && other.done;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const sorted_unique_rmat_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private:
Chris@16: 
Chris@16:     // Parameters
Chris@16:     shared_ptr<uniform_01<RandomGenerator> > gen;
Chris@16:     bool             bidirectional;
Chris@16: 
Chris@16:     // Internal data structures
Chris@16:     std::priority_queue<value_type, std::vector<value_type>,
Chris@16:                         sort_pair<vertices_size_type> > values;
Chris@16:     value_type current;
Chris@16:     bool       done;
Chris@16:   };
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #ifdef BOOST_GRAPH_USE_MPI
Chris@16: #include <boost/graph/distributed/rmat_graph_generator.hpp>
Chris@16: #endif // BOOST_GRAPH_USE_MPI
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_RMAT_GENERATOR_HPP