1 // Copyright 2004 The Trustees of Indiana University.

     2 

     3 // Distributed under the Boost Software License, Version 1.0.

     4 // (See accompanying file LICENSE_1_0.txt or copy at

     5 // http://www.boost.org/LICENSE_1_0.txt)

     6 

     7 //  Authors: Douglas Gregor

     8 //           Andrew Lumsdaine

     9 #ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP

    10 #define BOOST_GRAPH_PLOD_GENERATOR_HPP

    11 

    12 #include <iterator>

    13 #include <utility>

    14 #include <boost/random/uniform_int.hpp>

    15 #include <boost/shared_ptr.hpp>

    16 #include <boost/graph/graph_traits.hpp>

    17 #include <vector>

    18 #include <map>

    19 #include <cmath>

    20 

    21 namespace boost {

    22 

    23   template<typename RandomGenerator, typename Graph>

    24   class plod_iterator

    25   {

    26     typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;

    27     typedef typename graph_traits<Graph>::directed_category directed_category;

    28 

    29   public:

    30     typedef std::input_iterator_tag iterator_category;

    31     typedef std::pair<std::size_t, std::size_t> value_type;

    32     typedef const value_type& reference;

    33     typedef const value_type* pointer;

    34     typedef void difference_type;

    35 

    36     plod_iterator() 

    37       : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }

    38 

    39     plod_iterator(RandomGenerator& gen, std::size_t n,  

    40                   double alpha, double beta, bool allow_self_loops = false)

    41       : gen(&gen), n(n), out_degrees(new out_degrees_t),

    42         degrees_left(0), allow_self_loops(allow_self_loops)

    43     {

    44       using std::pow;

    45 

    46       uniform_int<std::size_t> x(0, n-1);

    47       for (std::size_t i = 0; i != n; ++i) {

    48         std::size_t xv = x(gen);

    49     std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));

    50     if (degree != 0) {

    51       out_degrees->push_back(std::make_pair(i, degree));

    52     }

    53         degrees_left += degree;

    54       }

    55 

    56       next(directed_category());

    57     }

    58 

    59     reference operator*() const { return current; }

    60     pointer operator->() const { return &current; }

    61     

    62     plod_iterator& operator++()

    63     { 

    64       next(directed_category());

    65       return *this;

    66     }

    67 

    68     plod_iterator operator++(int)

    69     {

    70       plod_iterator temp(*this);

    71       ++(*this);

    72       return temp;

    73     }

    74 

    75     bool operator==(const plod_iterator& other) const

    76     { 

    77       return degrees_left == other.degrees_left; 

    78     }

    79 

    80     bool operator!=(const plod_iterator& other) const

    81     { return !(*this == other); }

    82 

    83   private:

    84     void next(directed_tag)

    85     {

    86       uniform_int<std::size_t> x(0, out_degrees->size()-1);

    87       std::size_t source;

    88       do {

    89         source = x(*gen);

    90       } while ((*out_degrees)[source].second == 0);

    91       current.first = (*out_degrees)[source].first;

    92       do {

    93         current.second = x(*gen);

    94       } while (current.first == current.second && !allow_self_loops);

    95       --degrees_left;

    96       if (--(*out_degrees)[source].second == 0) {

    97         (*out_degrees)[source] = out_degrees->back();

    98         out_degrees->pop_back();

    99       }

   100     }

   101 

   102     void next(undirected_tag)

   103     {

   104       std::size_t source, target;

   105       while (true) {

   106         /* We may get to the point where we can't actually find any

   107            new edges, so we just add some random edge and set the

   108            degrees left = 0 to signal termination. */

   109         if (out_degrees->size() < 2) {

   110           uniform_int<std::size_t> x(0, n);

   111           current.first  = x(*gen);

   112           do {

   113             current.second = x(*gen);

   114           } while (current.first == current.second && !allow_self_loops);

   115           degrees_left = 0;

   116           out_degrees->clear();

   117           return;

   118         }

   119 

   120         uniform_int<std::size_t> x(0, out_degrees->size()-1);

   121 

   122         // Select source vertex

   123         source = x(*gen);

   124         if ((*out_degrees)[source].second == 0) {

   125           (*out_degrees)[source] = out_degrees->back();

   126           out_degrees->pop_back();

   127           continue;

   128         } 

   129 

   130         // Select target vertex

   131         target = x(*gen);

   132         if ((*out_degrees)[target].second == 0) {

   133           (*out_degrees)[target] = out_degrees->back();

   134           out_degrees->pop_back();

   135           continue;

   136         } else if (source != target 

   137                    || (allow_self_loops && (*out_degrees)[source].second > 2)) {

   138           break;

   139         }

   140       }

   141 

   142       // Update degree counts

   143       --(*out_degrees)[source].second;

   144       --degrees_left;

   145       --(*out_degrees)[target].second;

   146       --degrees_left;

   147       current.first  = (*out_degrees)[source].first;

   148       current.second = (*out_degrees)[target].first;

   149     }

   150 

   151     RandomGenerator* gen;

   152     std::size_t n;

   153     shared_ptr<out_degrees_t> out_degrees;

   154     std::size_t degrees_left;

   155     bool allow_self_loops;

   156     value_type current;

   157   };

   158 

   159 } // end namespace boost

   160 

   161 #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP