// Copyright 2004 The Trustees of Indiana University. | |
// Distributed under 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: Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP | |
#define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP | |
#include <iterator> | |
#include <utility> | |
#include <boost/random/uniform_01.hpp> | |
#include <boost/random/uniform_int.hpp> | |
namespace boost { | |
// Assumes undirected | |
template<typename RandomGenerator, typename Graph> | |
class small_world_iterator | |
{ | |
typedef typename graph_traits<Graph>::vertices_size_type | |
vertices_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; | |
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) | |
{ } | |
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; | |
} | |
small_world_iterator operator++(int) | |
{ | |
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; | |
} | |
bool operator!=(const small_world_iterator& other) const | |
{ return !(*this == other); } | |
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); | |
} | |
RandomGenerator* gen; | |
vertices_size_type n; | |
vertices_size_type k; | |
double prob; | |
vertices_size_type source; | |
vertices_size_type target; | |
bool allow_self_loops; | |
value_type current; | |
}; | |
} // end namespace boost | |
#endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP |