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/random/uniform_01.hpp>
0015 #include <boost/random/uniform_int.hpp>
0016
0017 namespace boost
0018 {
0019
0020 // Assumes undirected
0021 template < typename RandomGenerator, typename Graph > class small_world_iterator
0022 {
0023     typedef
0024         typename graph_traits< Graph >::vertices_size_type vertices_size_type;
0025
0026 public:
0027     typedef std::input_iterator_tag iterator_category;
0028     typedef std::pair< vertices_size_type, vertices_size_type > value_type;
0029     typedef const value_type& reference;
0030     typedef const value_type* pointer;
0031     typedef void difference_type;
0032
0033     small_world_iterator() : gen(0) {}
0034     small_world_iterator(RandomGenerator& gen, vertices_size_type n,
0035         vertices_size_type k, double prob = 0.0, bool allow_self_loops = false)
0036     : gen(&gen)
0037     , n(n)
0038     , k(k)
0039     , prob(prob)
0040     , source(0)
0041     , target(allow_self_loops ? 0 : 1)
0042     , allow_self_loops(allow_self_loops)
0043     , current(0, allow_self_loops ? 0 : 1)
0044     {
0045     }
0046
0047     reference operator*() const { return current; }
0048     pointer operator->() const { return &current; }
0049
0050     small_world_iterator& operator++()
0051     {
0052         target = (target + 1) % n;
0053         if (target == (source + k / 2 + 1) % n)
0054         {
0055             ++source;
0056             if (allow_self_loops)
0057                 target = source;
0058             else
0059                 target = (source + 1) % n;
0060         }
0061         current.first = source;
0062
0063         uniform_01< RandomGenerator, double > rand01(*gen);
0064         uniform_int< vertices_size_type > rand_vertex_gen(0, n - 1);
0065         double x = rand01();
0066         *gen = rand01.base(); // GRRRR
0067         if (x < prob)
0068         {
0069             vertices_size_type lower = (source + n - k / 2) % n;
0070             vertices_size_type upper = (source + k / 2) % n;
0071             do
0072             {
0073                 current.second = rand_vertex_gen(*gen);
0074             } while ((current.second >= lower && current.second <= upper)
0075                 || (upper < lower
0076                     && (current.second >= lower || current.second <= upper)));
0077         }
0078         else
0079         {
0080             current.second = target;
0081         }
0082         return *this;
0083     }
0084
0085     small_world_iterator operator++(int)
0086     {
0087         small_world_iterator temp(*this);
0088         ++(*this);
0089         return temp;
0090     }
0091
0092     bool operator==(const small_world_iterator& other) const
0093     {
0094         if (!gen && other.gen)
0095             return other == *this;
0096         else if (gen && !other.gen)
0097             return source == n;
0098         else if (!gen && !other.gen)
0099             return true;
0100         return source == other.source && target == other.target;
0101     }
0102
0103     bool operator!=(const small_world_iterator& other) const
0104     {
0105         return !(*this == other);
0106     }
0107
0108 private:
0109     void next()
0110     {
0111         uniform_int< vertices_size_type > rand_vertex(0, n - 1);
0112         current.first = rand_vertex(*gen);
0113         do
0114         {
0115             current.second = rand_vertex(*gen);
0116         } while (current.first == current.second && !allow_self_loops);
0117     }
0118
0119     RandomGenerator* gen;
0120     vertices_size_type n;
0121     vertices_size_type k;
0122     double prob;
0123     vertices_size_type source;
0124     vertices_size_type target;
0125     bool allow_self_loops;
0126     value_type current;
0127 };
0128
0129 } // end namespace boost
0130
0131 #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP