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 williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: namespace boost { williamr@2: williamr@2: template williamr@2: class plod_iterator williamr@2: { williamr@2: typedef std::vector > out_degrees_t; williamr@2: typedef typename graph_traits::directed_category directed_category; williamr@2: williamr@2: public: williamr@2: typedef std::input_iterator_tag iterator_category; williamr@2: typedef std::pair 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 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 ¤t; } 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 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 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 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; 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