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