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