boost/graph/small_world_generator.hpp

0001 // Copyright 2004 The Trustees of Indiana University.
0002
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
0010 #define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
0011
0012 #include <iterator>
0013 #include <utility>
0014 #include <boost/graph/graph_traits.hpp>
0015 #include <boost/random/uniform_01.hpp>
0016 #include <boost/random/uniform_int.hpp>
0017
0018 namespace boost
0019 {
0020
0021 // Assumes undirected
0022 template < typename RandomGenerator, typename Graph > class small_world_iterator
0023 {
0024     typedef
0025         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0026
0027 public:
0028     typedef std::input_iterator_tag iterator_category;
0029     typedef std::pair< vertices_size_type, vertices_size_type > value_type;
0030     typedef const value_type& reference;
0031     typedef const value_type* pointer;
0032     typedef void difference_type;
0033
0034     small_world_iterator() : gen(0) {}
0035     small_world_iterator(RandomGenerator& gen, vertices_size_type n,
0036         vertices_size_type k, double prob = 0.0, bool allow_self_loops = false)
0037     : gen(&gen)
0038     , n(n)
0039     , k(k)
0040     , prob(prob)
0041     , source(0)
0042     , target(allow_self_loops ? 0 : 1)
0043     , allow_self_loops(allow_self_loops)
0044     , current(0, allow_self_loops ? 0 : 1)
0045     {
0046     }
0047
0048     reference operator*() const { return current; }
0049     pointer operator->() const { return &current; }
0050
0051     small_world_iterator& operator++()
0052     {
0053         target = (target + 1) % n;
0054         if (target == (source + k / 2 + 1) % n)
0055         {
0056             ++source;
0057             if (allow_self_loops)
0058                 target = source;
0059             else
0060                 target = (source + 1) % n;
0061         }
0062         current.first = source;
0063
0064         uniform_01< RandomGenerator, double > rand01(*gen);
0065         uniform_int< vertices_size_type > rand_vertex_gen(0, n - 1);
0066         double x = rand01();
0067         *gen = rand01.base(); // GRRRR
0068         if (x < prob)
0069         {
0070             vertices_size_type lower = (source + n - k / 2) % n;
0071             vertices_size_type upper = (source + k / 2) % n;
0072             do
0073             {
0074                 current.second = rand_vertex_gen(*gen);
0075             } while ((current.second >= lower && current.second <= upper)
0076                 || (upper < lower
0077                     && (current.second >= lower || current.second <= upper)));
0078         }
0079         else
0080         {
0081             current.second = target;
0082         }
0083         return *this;
0084     }
0085
0086     small_world_iterator operator++(int)
0087     {
0088         small_world_iterator temp(*this);
0089         ++(*this);
0090         return temp;
0091     }
0092
0093     bool operator==(const small_world_iterator& other) const
0094     {
0095         if (!gen && other.gen)
0096             return other == *this;
0097         else if (gen && !other.gen)
0098             return source == n;
0099         else if (!gen && !other.gen)
0100             return true;
0101         return source == other.source && target == other.target;
0102     }
0103
0104     bool operator!=(const small_world_iterator& other) const
0105     {
0106         return !(*this == other);
0107     }
0108
0109 private:
0110     void next()
0111     {
0112         uniform_int< vertices_size_type > rand_vertex(0, n - 1);
0113         current.first = rand_vertex(*gen);
0114         do
0115         {
0116             current.second = rand_vertex(*gen);
0117         } while (current.first == current.second && !allow_self_loops);
0118     }
0119
0120     RandomGenerator* gen;
0121     vertices_size_type n;
0122     vertices_size_type k;
0123     double prob;
0124     vertices_size_type source;
0125     vertices_size_type target;
0126     bool allow_self_loops;
0127     value_type current;
0128 };
0129
0130 } // end namespace boost
0131
0132 #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP