1 // Copyright 2004 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP
10 #define BOOST_GRAPH_PLOD_GENERATOR_HPP
14 #include <boost/random/uniform_int.hpp>
15 #include <boost/shared_ptr.hpp>
16 #include <boost/graph/graph_traits.hpp>
23 template<typename RandomGenerator, typename Graph>
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;
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;
37 : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
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)
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)));
51 out_degrees->push_back(std::make_pair(i, degree));
53 degrees_left += degree;
56 next(directed_category());
59 reference operator*() const { return current; }
60 pointer operator->() const { return ¤t; }
62 plod_iterator& operator++()
64 next(directed_category());
68 plod_iterator operator++(int)
70 plod_iterator temp(*this);
75 bool operator==(const plod_iterator& other) const
77 return degrees_left == other.degrees_left;
80 bool operator!=(const plod_iterator& other) const
81 { return !(*this == other); }
84 void next(directed_tag)
86 uniform_int<std::size_t> x(0, out_degrees->size()-1);
90 } while ((*out_degrees)[source].second == 0);
91 current.first = (*out_degrees)[source].first;
93 current.second = x(*gen);
94 } while (current.first == current.second && !allow_self_loops);
96 if (--(*out_degrees)[source].second == 0) {
97 (*out_degrees)[source] = out_degrees->back();
98 out_degrees->pop_back();
102 void next(undirected_tag)
104 std::size_t source, target;
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);
113 current.second = x(*gen);
114 } while (current.first == current.second && !allow_self_loops);
116 out_degrees->clear();
120 uniform_int<std::size_t> x(0, out_degrees->size()-1);
122 // Select source vertex
124 if ((*out_degrees)[source].second == 0) {
125 (*out_degrees)[source] = out_degrees->back();
126 out_degrees->pop_back();
130 // Select target vertex
132 if ((*out_degrees)[target].second == 0) {
133 (*out_degrees)[target] = out_degrees->back();
134 out_degrees->pop_back();
136 } else if (source != target
137 || (allow_self_loops && (*out_degrees)[source].second > 2)) {
142 // Update degree counts
143 --(*out_degrees)[source].second;
145 --(*out_degrees)[target].second;
147 current.first = (*out_degrees)[source].first;
148 current.second = (*out_degrees)[target].first;
151 RandomGenerator* gen;
153 shared_ptr<out_degrees_t> out_degrees;
154 std::size_t degrees_left;
155 bool allow_self_loops;
159 } // end namespace boost
161 #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP