williamr@2: // Copyright 2004 The Trustees of Indiana University.
williamr@2: 
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: //  Authors: Douglas Gregor
williamr@2: //           Andrew Lumsdaine
williamr@2: #ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
williamr@2: #define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
williamr@2: 
williamr@2: #include <iterator>
williamr@2: #include <utility>
williamr@2: #include <boost/random/uniform_01.hpp>
williamr@2: #include <boost/random/uniform_int.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   // Assumes undirected
williamr@2:   template<typename RandomGenerator, typename Graph>
williamr@2:   class small_world_iterator
williamr@2:   {
williamr@2:     typedef typename graph_traits<Graph>::vertices_size_type 
williamr@2:       vertices_size_type;
williamr@2: 
williamr@2:   public:
williamr@2:     typedef std::input_iterator_tag iterator_category;
williamr@2:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
williamr@2:     typedef const value_type& reference;
williamr@2:     typedef const value_type* pointer;
williamr@2:     typedef void difference_type;
williamr@2: 
williamr@2:     small_world_iterator() : gen(0) {}
williamr@2:     small_world_iterator(RandomGenerator& gen, vertices_size_type n, 
williamr@2:                          vertices_size_type k, double prob = 0.0, 
williamr@2:                          bool allow_self_loops = false) 
williamr@2:       : gen(&gen), n(n), k(k), prob(prob), source(0), 
williamr@2:         target(allow_self_loops? 0 : 1), 
williamr@2:         allow_self_loops(allow_self_loops), 
williamr@2:         current(0, allow_self_loops? 0 : 1)
williamr@2:     { }
williamr@2: 
williamr@2:     reference operator*() const { return current; }
williamr@2:     pointer operator->() const { return &current; }
williamr@2:     
williamr@2:     small_world_iterator& operator++()
williamr@2:     { 
williamr@2:       target = (target + 1) % n;
williamr@2:       if (target == (source + k/2 + 1) % n) {
williamr@2:         ++source;
williamr@2:         if (allow_self_loops) target = source;
williamr@2:         else target = (source + 1) % n;
williamr@2:       }
williamr@2:       current.first = source;
williamr@2: 
williamr@2:       uniform_01<RandomGenerator, double> rand01(*gen);
williamr@2:       uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);
williamr@2:       double x = rand01();
williamr@2:       *gen = rand01.base(); // GRRRR
williamr@2:       if (x < prob) {
williamr@2:         vertices_size_type lower = (source + n - k/2) % n;
williamr@2:         vertices_size_type upper = (source + k/2) % n;
williamr@2:         do {
williamr@2:           current.second = rand_vertex_gen(*gen);
williamr@2:         } while (current.second >= lower && current.second <= upper
williamr@2:                  || (upper < lower 
williamr@2:                      && (current.second >= lower || current.second <= upper)));
williamr@2:       } else {
williamr@2:         current.second = target;
williamr@2:       }
williamr@2:       return *this;
williamr@2:     }
williamr@2: 
williamr@2:     small_world_iterator operator++(int)
williamr@2:     {
williamr@2:       small_world_iterator temp(*this);
williamr@2:       ++(*this);
williamr@2:       return temp;
williamr@2:     }
williamr@2: 
williamr@2:     bool operator==(const small_world_iterator& other) const
williamr@2:     {
williamr@2:       if (!gen && other.gen) return other == *this;
williamr@2:       else if (gen && !other.gen) return source == n;
williamr@2:       else if (!gen && !other.gen) return true;
williamr@2:       return source == other.source && target == other.target;
williamr@2:     }
williamr@2: 
williamr@2:     bool operator!=(const small_world_iterator& other) const
williamr@2:     { return !(*this == other); }
williamr@2: 
williamr@2:   private:
williamr@2:     void next()
williamr@2:     {
williamr@2:       uniform_int<vertices_size_type> rand_vertex(0, n-1);
williamr@2:       current.first = rand_vertex(*gen);
williamr@2:       do {
williamr@2:         current.second = rand_vertex(*gen);
williamr@2:       } while (current.first == current.second && !allow_self_loops);
williamr@2:     }
williamr@2: 
williamr@2:     RandomGenerator* gen;
williamr@2:     vertices_size_type n;
williamr@2:     vertices_size_type k;
williamr@2:     double prob;
williamr@2:     vertices_size_type source;
williamr@2:     vertices_size_type target;
williamr@2:     bool allow_self_loops;
williamr@2:     value_type current;
williamr@2:   };
williamr@2: 
williamr@2: } // end namespace boost
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP