epoc32/include/stdapis/boost/graph/plod_generator.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
williamr@2
     1
// Copyright 2004 The Trustees of Indiana University.
williamr@2
     2
williamr@2
     3
// Distributed under the Boost Software License, Version 1.0.
williamr@2
     4
// (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     5
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     6
williamr@2
     7
//  Authors: Douglas Gregor
williamr@2
     8
//           Andrew Lumsdaine
williamr@2
     9
#ifndef BOOST_GRAPH_PLOD_GENERATOR_HPP
williamr@2
    10
#define BOOST_GRAPH_PLOD_GENERATOR_HPP
williamr@2
    11
williamr@2
    12
#include <iterator>
williamr@2
    13
#include <utility>
williamr@2
    14
#include <boost/random/uniform_int.hpp>
williamr@2
    15
#include <boost/shared_ptr.hpp>
williamr@2
    16
#include <boost/graph/graph_traits.hpp>
williamr@2
    17
#include <vector>
williamr@2
    18
#include <map>
williamr@2
    19
#include <cmath>
williamr@2
    20
williamr@2
    21
namespace boost {
williamr@2
    22
williamr@2
    23
  template<typename RandomGenerator, typename Graph>
williamr@2
    24
  class plod_iterator
williamr@2
    25
  {
williamr@2
    26
    typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
williamr@2
    27
    typedef typename graph_traits<Graph>::directed_category directed_category;
williamr@2
    28
williamr@2
    29
  public:
williamr@2
    30
    typedef std::input_iterator_tag iterator_category;
williamr@2
    31
    typedef std::pair<std::size_t, std::size_t> value_type;
williamr@2
    32
    typedef const value_type& reference;
williamr@2
    33
    typedef const value_type* pointer;
williamr@2
    34
    typedef void difference_type;
williamr@2
    35
williamr@2
    36
    plod_iterator() 
williamr@2
    37
      : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
williamr@2
    38
williamr@2
    39
    plod_iterator(RandomGenerator& gen, std::size_t n,  
williamr@2
    40
                  double alpha, double beta, bool allow_self_loops = false)
williamr@2
    41
      : gen(&gen), n(n), out_degrees(new out_degrees_t),
williamr@2
    42
        degrees_left(0), allow_self_loops(allow_self_loops)
williamr@2
    43
    {
williamr@2
    44
      using std::pow;
williamr@2
    45
williamr@2
    46
      uniform_int<std::size_t> x(0, n-1);
williamr@2
    47
      for (std::size_t i = 0; i != n; ++i) {
williamr@2
    48
        std::size_t xv = x(gen);
williamr@2
    49
    std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
williamr@2
    50
    if (degree != 0) {
williamr@2
    51
      out_degrees->push_back(std::make_pair(i, degree));
williamr@2
    52
    }
williamr@2
    53
        degrees_left += degree;
williamr@2
    54
      }
williamr@2
    55
williamr@2
    56
      next(directed_category());
williamr@2
    57
    }
williamr@2
    58
williamr@2
    59
    reference operator*() const { return current; }
williamr@2
    60
    pointer operator->() const { return &current; }
williamr@2
    61
    
williamr@2
    62
    plod_iterator& operator++()
williamr@2
    63
    { 
williamr@2
    64
      next(directed_category());
williamr@2
    65
      return *this;
williamr@2
    66
    }
williamr@2
    67
williamr@2
    68
    plod_iterator operator++(int)
williamr@2
    69
    {
williamr@2
    70
      plod_iterator temp(*this);
williamr@2
    71
      ++(*this);
williamr@2
    72
      return temp;
williamr@2
    73
    }
williamr@2
    74
williamr@2
    75
    bool operator==(const plod_iterator& other) const
williamr@2
    76
    { 
williamr@2
    77
      return degrees_left == other.degrees_left; 
williamr@2
    78
    }
williamr@2
    79
williamr@2
    80
    bool operator!=(const plod_iterator& other) const
williamr@2
    81
    { return !(*this == other); }
williamr@2
    82
williamr@2
    83
  private:
williamr@2
    84
    void next(directed_tag)
williamr@2
    85
    {
williamr@2
    86
      uniform_int<std::size_t> x(0, out_degrees->size()-1);
williamr@2
    87
      std::size_t source;
williamr@2
    88
      do {
williamr@2
    89
        source = x(*gen);
williamr@2
    90
      } while ((*out_degrees)[source].second == 0);
williamr@2
    91
      current.first = (*out_degrees)[source].first;
williamr@2
    92
      do {
williamr@2
    93
        current.second = x(*gen);
williamr@2
    94
      } while (current.first == current.second && !allow_self_loops);
williamr@2
    95
      --degrees_left;
williamr@2
    96
      if (--(*out_degrees)[source].second == 0) {
williamr@2
    97
        (*out_degrees)[source] = out_degrees->back();
williamr@2
    98
        out_degrees->pop_back();
williamr@2
    99
      }
williamr@2
   100
    }
williamr@2
   101
williamr@2
   102
    void next(undirected_tag)
williamr@2
   103
    {
williamr@2
   104
      std::size_t source, target;
williamr@2
   105
      while (true) {
williamr@2
   106
        /* We may get to the point where we can't actually find any
williamr@2
   107
           new edges, so we just add some random edge and set the
williamr@2
   108
           degrees left = 0 to signal termination. */
williamr@2
   109
        if (out_degrees->size() < 2) {
williamr@2
   110
          uniform_int<std::size_t> x(0, n);
williamr@2
   111
          current.first  = x(*gen);
williamr@2
   112
          do {
williamr@2
   113
            current.second = x(*gen);
williamr@2
   114
          } while (current.first == current.second && !allow_self_loops);
williamr@2
   115
          degrees_left = 0;
williamr@2
   116
          out_degrees->clear();
williamr@2
   117
          return;
williamr@2
   118
        }
williamr@2
   119
williamr@2
   120
        uniform_int<std::size_t> x(0, out_degrees->size()-1);
williamr@2
   121
williamr@2
   122
        // Select source vertex
williamr@2
   123
        source = x(*gen);
williamr@2
   124
        if ((*out_degrees)[source].second == 0) {
williamr@2
   125
          (*out_degrees)[source] = out_degrees->back();
williamr@2
   126
          out_degrees->pop_back();
williamr@2
   127
          continue;
williamr@2
   128
        } 
williamr@2
   129
williamr@2
   130
        // Select target vertex
williamr@2
   131
        target = x(*gen);
williamr@2
   132
        if ((*out_degrees)[target].second == 0) {
williamr@2
   133
          (*out_degrees)[target] = out_degrees->back();
williamr@2
   134
          out_degrees->pop_back();
williamr@2
   135
          continue;
williamr@2
   136
        } else if (source != target 
williamr@2
   137
                   || (allow_self_loops && (*out_degrees)[source].second > 2)) {
williamr@2
   138
          break;
williamr@2
   139
        }
williamr@2
   140
      }
williamr@2
   141
williamr@2
   142
      // Update degree counts
williamr@2
   143
      --(*out_degrees)[source].second;
williamr@2
   144
      --degrees_left;
williamr@2
   145
      --(*out_degrees)[target].second;
williamr@2
   146
      --degrees_left;
williamr@2
   147
      current.first  = (*out_degrees)[source].first;
williamr@2
   148
      current.second = (*out_degrees)[target].first;
williamr@2
   149
    }
williamr@2
   150
williamr@2
   151
    RandomGenerator* gen;
williamr@2
   152
    std::size_t n;
williamr@2
   153
    shared_ptr<out_degrees_t> out_degrees;
williamr@2
   154
    std::size_t degrees_left;
williamr@2
   155
    bool allow_self_loops;
williamr@2
   156
    value_type current;
williamr@2
   157
  };
williamr@2
   158
williamr@2
   159
} // end namespace boost
williamr@2
   160
williamr@2
   161
#endif // BOOST_GRAPH_PLOD_GENERATOR_HPP