boost/graph/plod_generator.hpp

0001 // Copyright 2004-2006 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_PLOD_GENERATOR_HPP
0010 #define BOOST_GRAPH_PLOD_GENERATOR_HPP
0011
0012 #include <iterator>
0013 #include <utility>
0014 #include <boost/random/uniform_int.hpp>
0015 #include <boost/shared_ptr.hpp>
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <vector>
0018 #include <map>
0019 #include <boost/config/no_tr1/cmath.hpp>
0020 #include <boost/mpl/if.hpp>
0021
0022 namespace boost
0023 {
0024 template < typename RandomGenerator > class out_directed_plod_iterator
0025 {
0026 public:
0027     typedef std::forward_iterator_tag iterator_category;
0028     typedef std::pair< std::size_t, std::size_t > value_type;
0029     typedef const value_type& reference;
0030     typedef const value_type* pointer;
0031     typedef std::ptrdiff_t difference_type;
0032
0033     out_directed_plod_iterator() : gen(0), at_end(true) {}
0034
0035     out_directed_plod_iterator(RandomGenerator& gen, std::size_t n,
0036         double alpha, double beta, bool allow_self_loops)
0037     : gen(&gen)
0038     , n(n)
0039     , alpha(alpha)
0040     , beta(beta)
0041     , allow_self_loops(allow_self_loops)
0042     , at_end(false)
0043     , degree(0)
0044     , current(0, 0)
0045     {
0046         using std::pow;
0047
0048         uniform_int< std::size_t > x(0, n - 1);
0049         std::size_t xv = x(gen);
0050         degree = (xv == 0 ? 0 : std::size_t(beta * pow(xv, -alpha)));
0051     }
0052
0053     reference operator*() const { return current; }
0054     pointer operator->() const { return &current; }
0055
0056     out_directed_plod_iterator& operator++()
0057     {
0058         using std::pow;
0059
0060         uniform_int< std::size_t > x(0, n - 1);
0061
0062         // Continue stepping through source nodes until the
0063         // (out)degree is > 0
0064         while (degree == 0)
0065         {
0066             // Step to the next source node. If we've gone past the
0067             // number of nodes we're responsible for, we're done.
0068             if (++current.first >= n)
0069             {
0070                 at_end = true;
0071                 return *this;
0072             }
0073
0074             std::size_t xv = x(*gen);
0075             degree = (xv == 0 ? 0 : std::size_t(beta * pow(xv, -alpha)));
0076         }
0077
0078         do
0079         {
0080             current.second = x(*gen);
0081         } while (current.first == current.second && !allow_self_loops);
0082         --degree;
0083
0084         return *this;
0085     }
0086
0087     out_directed_plod_iterator operator++(int)
0088     {
0089         out_directed_plod_iterator temp(*this);
0090         ++(*this);
0091         return temp;
0092     }
0093
0094     bool operator==(const out_directed_plod_iterator& other) const
0095     {
0096         return at_end == other.at_end;
0097     }
0098
0099     bool operator!=(const out_directed_plod_iterator& other) const
0100     {
0101         return !(*this == other);
0102     }
0103
0104 private:
0105     RandomGenerator* gen;
0106     std::size_t n;
0107     double alpha;
0108     double beta;
0109     bool allow_self_loops;
0110     bool at_end;
0111     std::size_t degree;
0112     value_type current;
0113 };
0114
0115 template < typename RandomGenerator > class undirected_plod_iterator
0116 {
0117     typedef std::vector< std::pair< std::size_t, std::size_t > > out_degrees_t;
0118
0119 public:
0120     typedef std::input_iterator_tag iterator_category;
0121     typedef std::pair< std::size_t, std::size_t > value_type;
0122     typedef const value_type& reference;
0123     typedef const value_type* pointer;
0124     typedef std::ptrdiff_t difference_type;
0125
0126     undirected_plod_iterator()
0127     : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false)
0128     {
0129     }
0130
0131     undirected_plod_iterator(RandomGenerator& gen, std::size_t n, double alpha,
0132         double beta, bool allow_self_loops = false)
0133     : gen(&gen)
0134     , n(n)
0135     , out_degrees(new out_degrees_t)
0136     , degrees_left(0)
0137     , allow_self_loops(allow_self_loops)
0138     {
0139         using std::pow;
0140
0141         uniform_int< std::size_t > x(0, n - 1);
0142         for (std::size_t i = 0; i != n; ++i)
0143         {
0144             std::size_t xv = x(gen);
0145             std::size_t degree
0146                 = (xv == 0 ? 0 : std::size_t(beta * pow(xv, -alpha)));
0147             if (degree == 0)
0148                 degree = 1;
0149             else if (degree >= n)
0150                 degree = n - 1;
0151             out_degrees->push_back(std::make_pair(i, degree));
0152             degrees_left += degree;
0153         }
0154
0155         next();
0156     }
0157
0158     reference operator*() const { return current; }
0159     pointer operator->() const { return &current; }
0160
0161     undirected_plod_iterator& operator++()
0162     {
0163         next();
0164         return *this;
0165     }
0166
0167     undirected_plod_iterator operator++(int)
0168     {
0169         undirected_plod_iterator temp(*this);
0170         ++(*this);
0171         return temp;
0172     }
0173
0174     bool operator==(const undirected_plod_iterator& other) const
0175     {
0176         return degrees_left == other.degrees_left;
0177     }
0178
0179     bool operator!=(const undirected_plod_iterator& other) const
0180     {
0181         return !(*this == other);
0182     }
0183
0184 private:
0185     void next()
0186     {
0187         std::size_t source, target;
0188         while (true)
0189         {
0190             /* We may get to the point where we can't actually find any
0191                new edges, so we just add some random edge and set the
0192                degrees left = 0 to signal termination. */
0193             if (out_degrees->size() < 2)
0194             {
0195                 uniform_int< std::size_t > x(0, n - 1);
0196                 current.first = x(*gen);
0197                 do
0198                 {
0199                     current.second = x(*gen);
0200                 } while (current.first == current.second && !allow_self_loops);
0201                 degrees_left = 0;
0202                 out_degrees->clear();
0203                 return;
0204             }
0205
0206             uniform_int< std::size_t > x(0, out_degrees->size() - 1);
0207
0208             // Select source vertex
0209             source = x(*gen);
0210             if ((*out_degrees)[source].second == 0)
0211             {
0212                 (*out_degrees)[source] = out_degrees->back();
0213                 out_degrees->pop_back();
0214                 continue;
0215             }
0216
0217             // Select target vertex
0218             target = x(*gen);
0219             if ((*out_degrees)[target].second == 0)
0220             {
0221                 (*out_degrees)[target] = out_degrees->back();
0222                 out_degrees->pop_back();
0223                 continue;
0224             }
0225             else if (source != target
0226                 || (allow_self_loops && (*out_degrees)[source].second > 2))
0227             {
0228                 break;
0229             }
0230         }
0231
0232         // Update degree counts
0233         --(*out_degrees)[source].second;
0234         --degrees_left;
0235         --(*out_degrees)[target].second;
0236         --degrees_left;
0237         current.first = (*out_degrees)[source].first;
0238         current.second = (*out_degrees)[target].first;
0239     }
0240
0241     RandomGenerator* gen;
0242     std::size_t n;
0243     shared_ptr< out_degrees_t > out_degrees;
0244     std::size_t degrees_left;
0245     bool allow_self_loops;
0246     value_type current;
0247 };
0248
0249 template < typename RandomGenerator, typename Graph >
0250 class plod_iterator
0251 : public mpl::if_<
0252       is_convertible< typename graph_traits< Graph >::directed_category,
0253           directed_tag >,
0254       out_directed_plod_iterator< RandomGenerator >,
0255       undirected_plod_iterator< RandomGenerator > >::type
0256 {
0257     typedef typename mpl::if_<
0258         is_convertible< typename graph_traits< Graph >::directed_category,
0259             directed_tag >,
0260         out_directed_plod_iterator< RandomGenerator >,
0261         undirected_plod_iterator< RandomGenerator > >::type inherited;
0262
0263 public:
0264     plod_iterator() : inherited() {}
0265
0266     plod_iterator(RandomGenerator& gen, std::size_t n, double alpha,
0267         double beta, bool allow_self_loops = false)
0268     : inherited(gen, n, alpha, beta, allow_self_loops)
0269     {
0270     }
0271 };
0272
0273 } // end namespace boost
0274
0275 #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP