williamr@2: // Copyright 2004 The Trustees of Indiana University.
williamr@2: 
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: //  Authors: Douglas Gregor
williamr@2: //           Andrew Lumsdaine
williamr@2: #ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP
williamr@2: #define BOOST_GRAPH_PLOD_GENERATOR_HPP
williamr@2: 
williamr@2: #include <iterator>
williamr@2: #include <utility>
williamr@2: #include <boost/random/uniform_int.hpp>
williamr@2: #include <boost/shared_ptr.hpp>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <vector>
williamr@2: #include <map>
williamr@2: #include <cmath>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   template<typename RandomGenerator, typename Graph>
williamr@2:   class plod_iterator
williamr@2:   {
williamr@2:     typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
williamr@2:     typedef typename graph_traits<Graph>::directed_category directed_category;
williamr@2: 
williamr@2:   public:
williamr@2:     typedef std::input_iterator_tag iterator_category;
williamr@2:     typedef std::pair<std::size_t, std::size_t> value_type;
williamr@2:     typedef const value_type& reference;
williamr@2:     typedef const value_type* pointer;
williamr@2:     typedef void difference_type;
williamr@2: 
williamr@2:     plod_iterator() 
williamr@2:       : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
williamr@2: 
williamr@2:     plod_iterator(RandomGenerator& gen, std::size_t n,  
williamr@2:                   double alpha, double beta, bool allow_self_loops = false)
williamr@2:       : gen(&gen), n(n), out_degrees(new out_degrees_t),
williamr@2:         degrees_left(0), allow_self_loops(allow_self_loops)
williamr@2:     {
williamr@2:       using std::pow;
williamr@2: 
williamr@2:       uniform_int<std::size_t> x(0, n-1);
williamr@2:       for (std::size_t i = 0; i != n; ++i) {
williamr@2:         std::size_t xv = x(gen);
williamr@2:     std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
williamr@2:     if (degree != 0) {
williamr@2:       out_degrees->push_back(std::make_pair(i, degree));
williamr@2:     }
williamr@2:         degrees_left += degree;
williamr@2:       }
williamr@2: 
williamr@2:       next(directed_category());
williamr@2:     }
williamr@2: 
williamr@2:     reference operator*() const { return current; }
williamr@2:     pointer operator->() const { return &current; }
williamr@2:     
williamr@2:     plod_iterator& operator++()
williamr@2:     { 
williamr@2:       next(directed_category());
williamr@2:       return *this;
williamr@2:     }
williamr@2: 
williamr@2:     plod_iterator operator++(int)
williamr@2:     {
williamr@2:       plod_iterator temp(*this);
williamr@2:       ++(*this);
williamr@2:       return temp;
williamr@2:     }
williamr@2: 
williamr@2:     bool operator==(const plod_iterator& other) const
williamr@2:     { 
williamr@2:       return degrees_left == other.degrees_left; 
williamr@2:     }
williamr@2: 
williamr@2:     bool operator!=(const plod_iterator& other) const
williamr@2:     { return !(*this == other); }
williamr@2: 
williamr@2:   private:
williamr@2:     void next(directed_tag)
williamr@2:     {
williamr@2:       uniform_int<std::size_t> x(0, out_degrees->size()-1);
williamr@2:       std::size_t source;
williamr@2:       do {
williamr@2:         source = x(*gen);
williamr@2:       } while ((*out_degrees)[source].second == 0);
williamr@2:       current.first = (*out_degrees)[source].first;
williamr@2:       do {
williamr@2:         current.second = x(*gen);
williamr@2:       } while (current.first == current.second && !allow_self_loops);
williamr@2:       --degrees_left;
williamr@2:       if (--(*out_degrees)[source].second == 0) {
williamr@2:         (*out_degrees)[source] = out_degrees->back();
williamr@2:         out_degrees->pop_back();
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     void next(undirected_tag)
williamr@2:     {
williamr@2:       std::size_t source, target;
williamr@2:       while (true) {
williamr@2:         /* We may get to the point where we can't actually find any
williamr@2:            new edges, so we just add some random edge and set the
williamr@2:            degrees left = 0 to signal termination. */
williamr@2:         if (out_degrees->size() < 2) {
williamr@2:           uniform_int<std::size_t> x(0, n);
williamr@2:           current.first  = x(*gen);
williamr@2:           do {
williamr@2:             current.second = x(*gen);
williamr@2:           } while (current.first == current.second && !allow_self_loops);
williamr@2:           degrees_left = 0;
williamr@2:           out_degrees->clear();
williamr@2:           return;
williamr@2:         }
williamr@2: 
williamr@2:         uniform_int<std::size_t> x(0, out_degrees->size()-1);
williamr@2: 
williamr@2:         // Select source vertex
williamr@2:         source = x(*gen);
williamr@2:         if ((*out_degrees)[source].second == 0) {
williamr@2:           (*out_degrees)[source] = out_degrees->back();
williamr@2:           out_degrees->pop_back();
williamr@2:           continue;
williamr@2:         } 
williamr@2: 
williamr@2:         // Select target vertex
williamr@2:         target = x(*gen);
williamr@2:         if ((*out_degrees)[target].second == 0) {
williamr@2:           (*out_degrees)[target] = out_degrees->back();
williamr@2:           out_degrees->pop_back();
williamr@2:           continue;
williamr@2:         } else if (source != target 
williamr@2:                    || (allow_self_loops && (*out_degrees)[source].second > 2)) {
williamr@2:           break;
williamr@2:         }
williamr@2:       }
williamr@2: 
williamr@2:       // Update degree counts
williamr@2:       --(*out_degrees)[source].second;
williamr@2:       --degrees_left;
williamr@2:       --(*out_degrees)[target].second;
williamr@2:       --degrees_left;
williamr@2:       current.first  = (*out_degrees)[source].first;
williamr@2:       current.second = (*out_degrees)[target].first;
williamr@2:     }
williamr@2: 
williamr@2:     RandomGenerator* gen;
williamr@2:     std::size_t n;
williamr@2:     shared_ptr<out_degrees_t> out_degrees;
williamr@2:     std::size_t degrees_left;
williamr@2:     bool allow_self_loops;
williamr@2:     value_type current;
williamr@2:   };
williamr@2: 
williamr@2: } // end namespace boost
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP