#include <boost/random/uniform_01.hpp>
#include <boost/random/uniform_int.hpp>
-namespace boost {
+namespace boost
+{
- // Assumes undirected
- template<typename RandomGenerator, typename Graph>
- class small_world_iterator
- {
- typedef typename graph_traits<Graph>::vertices_size_type
- vertices_size_type;
+// Assumes undirected
+template < typename RandomGenerator, typename Graph > class small_world_iterator
+{
+ typedef
+ typename graph_traits< Graph >::vertices_size_type vertices_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 void difference_type;
small_world_iterator() : gen(0) {}
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double prob = 0.0,
- bool allow_self_loops = false)
- : gen(&gen), n(n), k(k), prob(prob), source(0),
- target(allow_self_loops? 0 : 1),
- allow_self_loops(allow_self_loops),
- current(0, allow_self_loops? 0 : 1)
- { }
+ vertices_size_type k, double prob = 0.0, bool allow_self_loops = false)
+ : gen(&gen)
+ , n(n)
+ , k(k)
+ , prob(prob)
+ , source(0)
+ , target(allow_self_loops ? 0 : 1)
+ , allow_self_loops(allow_self_loops)
+ , current(0, allow_self_loops ? 0 : 1)
+ {
+ }
reference operator*() const { return current; }
pointer operator->() const { return ¤t; }
small_world_iterator& operator++()
{
- target = (target + 1) % n;
- if (target == (source + k/2 + 1) % n) {
- ++source;
- if (allow_self_loops) target = source;
- else target = (source + 1) % n;
- }
- current.first = source;
-
- uniform_01<RandomGenerator, double> rand01(*gen);
- uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);
- double x = rand01();
- *gen = rand01.base(); // GRRRR
- if (x < prob) {
- vertices_size_type lower = (source + n - k/2) % n;
- vertices_size_type upper = (source + k/2) % n;
- do {
- current.second = rand_vertex_gen(*gen);
- } while ((current.second >= lower && current.second <= upper)
- || (upper < lower
- && (current.second >= lower || current.second <= upper)));
- } else {
- current.second = target;
- }
- return *this;
+ target = (target + 1) % n;
+ if (target == (source + k / 2 + 1) % n)
+ {
+ ++source;
+ if (allow_self_loops)
+ target = source;
+ else
+ target = (source + 1) % n;
+ }
+ current.first = source;
+
+ uniform_01< RandomGenerator, double > rand01(*gen);
+ uniform_int< vertices_size_type > rand_vertex_gen(0, n - 1);
+ double x = rand01();
+ *gen = rand01.base(); // GRRRR
+ if (x < prob)
+ {
+ vertices_size_type lower = (source + n - k / 2) % n;
+ vertices_size_type upper = (source + k / 2) % n;
+ do
+ {
+ current.second = rand_vertex_gen(*gen);
+ } while ((current.second >= lower && current.second <= upper)
+ || (upper < lower
+ && (current.second >= lower || current.second <= upper)));
+ }
+ else
+ {
+ current.second = target;
+ }
+ return *this;
}
small_world_iterator operator++(int)
{
- small_world_iterator temp(*this);
- ++(*this);
- return temp;
+ small_world_iterator temp(*this);
+ ++(*this);
+ return temp;
}
bool operator==(const small_world_iterator& other) const
{
- if (!gen && other.gen) return other == *this;
- else if (gen && !other.gen) return source == n;
- else if (!gen && !other.gen) return true;
- return source == other.source && target == other.target;
+ if (!gen && other.gen)
+ return other == *this;
+ else if (gen && !other.gen)
+ return source == n;
+ else if (!gen && !other.gen)
+ return true;
+ return source == other.source && target == other.target;
}
bool operator!=(const small_world_iterator& other) const
- { return !(*this == other); }
+ {
+ return !(*this == other);
+ }
- private:
+private:
void next()
{
- uniform_int<vertices_size_type> rand_vertex(0, n-1);
- current.first = rand_vertex(*gen);
- do {
- current.second = rand_vertex(*gen);
- } while (current.first == current.second && !allow_self_loops);
+ uniform_int< vertices_size_type > rand_vertex(0, n - 1);
+ current.first = rand_vertex(*gen);
+ do
+ {
+ current.second = rand_vertex(*gen);
+ } while (current.first == current.second && !allow_self_loops);
}
RandomGenerator* gen;
vertices_size_type target;
bool allow_self_loops;
value_type current;
- };
+};
} // end namespace boost