| // 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 |