source: NonGTP/Boost/boost/graph/plod_generator.hpp @ 857

Revision 857, 4.7 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]1// Copyright 2004 The Trustees of Indiana University.
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (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 <cmath>
19
20namespace boost {
21
22  template<typename RandomGenerator, typename Graph>
23  class plod_iterator
24  {
25    typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
26    typedef typename graph_traits<Graph>::directed_category directed_category;
27
28  public:
29    typedef std::input_iterator_tag iterator_category;
30    typedef std::pair<std::size_t, std::size_t> value_type;
31    typedef const value_type& reference;
32    typedef const value_type* pointer;
33    typedef void difference_type;
34
35    plod_iterator()
36      : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
37
38    plod_iterator(RandomGenerator& gen, std::size_t n, 
39                  double alpha, double beta, bool allow_self_loops = false)
40      : gen(&gen), n(n), out_degrees(new out_degrees_t(n)),
41        degrees_left(0), allow_self_loops(allow_self_loops)
42    {
43      using std::pow;
44
45      uniform_int<std::size_t> x(0, n-1);
46      for (out_degrees_t::iterator i = out_degrees->begin();
47           i != out_degrees->end(); ++i) {
48        std::size_t xv = x(gen);
49        i->first = i - out_degrees->begin();
50        i->second = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
51        degrees_left += i->second;
52      }
53
54      next(directed_category());
55    }
56
57    reference operator*() const { return current; }
58    pointer operator->() const { return &current; }
59   
60    plod_iterator& operator++()
61    {
62      next(directed_category());
63      return *this;
64    }
65
66    plod_iterator operator++(int)
67    {
68      plod_iterator temp(*this);
69      ++(*this);
70      return temp;
71    }
72
73    bool operator==(const plod_iterator& other) const
74    {
75      return degrees_left == other.degrees_left;
76    }
77
78    bool operator!=(const plod_iterator& other) const
79    { return !(*this == other); }
80
81  private:
82    void next(directed_tag)
83    {
84      uniform_int<std::size_t> x(0, out_degrees->size()-1);
85      std::size_t source;
86      do {
87        source = x(*gen);
88      } while ((*out_degrees)[source].second == 0);
89      current.first = (*out_degrees)[source].first;
90      current.second = x(*gen);
91      --degrees_left;
92      if (--(*out_degrees)[source].second == 0) {
93        (*out_degrees)[source] = out_degrees->back();
94        out_degrees->pop_back();
95      }
96    }
97
98    void next(undirected_tag)
99    {
100      std::size_t source, target;
101      while (true) {
102        /* We may get to the point where we can't actually find any
103           new edges, so we just add some random edge and set the
104           degrees left = 0 to signal termination. */
105        if (out_degrees->size() < 2) {
106          uniform_int<std::size_t> x(0, n);
107          current.first  = x(*gen);
108          do {
109            current.second = x(*gen);
110          } while (current.first == current.second && !allow_self_loops);
111          degrees_left = 0;
112          out_degrees->clear();
113          return;
114        }
115
116        uniform_int<std::size_t> x(0, out_degrees->size()-1);
117
118        // Select source vertex
119        source = x(*gen);
120        if ((*out_degrees)[source].second == 0) {
121          (*out_degrees)[source] = out_degrees->back();
122          out_degrees->pop_back();
123          continue;
124        }
125
126        // Select target vertex
127        target = x(*gen);
128        if ((*out_degrees)[target].second == 0) {
129          (*out_degrees)[target] = out_degrees->back();
130          out_degrees->pop_back();
131          continue;
132        } else if (source != target
133                   || (allow_self_loops && (*out_degrees)[source].second > 2)) {
134          break;
135        }
136      }
137
138      // Update degree counts
139      --(*out_degrees)[source].second;
140      --degrees_left;
141      --(*out_degrees)[target].second;
142      --degrees_left;
143      current.first  = (*out_degrees)[source].first;
144      current.second = (*out_degrees)[target].first;
145    }
146
147    RandomGenerator* gen;
148    std::size_t n;
149    shared_ptr<out_degrees_t> out_degrees;
150    std::size_t degrees_left;
151    bool allow_self_loops;
152    value_type current;
153  };
154
155} // end namespace boost
156
157#endif // BOOST_GRAPH_PLOD_GENERATOR_HPP
Note: See TracBrowser for help on using the repository browser.