1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/small_world_generator.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,114 @@
     1.4 +// Copyright 2004 The Trustees of Indiana University.
     1.5 +
     1.6 +// Distributed under the Boost Software License, Version 1.0.
     1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
     1.8 +// http://www.boost.org/LICENSE_1_0.txt)
     1.9 +
    1.10 +//  Authors: Douglas Gregor
    1.11 +//           Andrew Lumsdaine
    1.12 +#ifndef BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
    1.13 +#define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
    1.14 +
    1.15 +#include <iterator>
    1.16 +#include <utility>
    1.17 +#include <boost/random/uniform_01.hpp>
    1.18 +#include <boost/random/uniform_int.hpp>
    1.19 +
    1.20 +namespace boost {
    1.21 +
    1.22 +  // Assumes undirected
    1.23 +  template<typename RandomGenerator, typename Graph>
    1.24 +  class small_world_iterator
    1.25 +  {
    1.26 +    typedef typename graph_traits<Graph>::vertices_size_type 
    1.27 +      vertices_size_type;
    1.28 +
    1.29 +  public:
    1.30 +    typedef std::input_iterator_tag iterator_category;
    1.31 +    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    1.32 +    typedef const value_type& reference;
    1.33 +    typedef const value_type* pointer;
    1.34 +    typedef void difference_type;
    1.35 +
    1.36 +    small_world_iterator() : gen(0) {}
    1.37 +    small_world_iterator(RandomGenerator& gen, vertices_size_type n, 
    1.38 +                         vertices_size_type k, double prob = 0.0, 
    1.39 +                         bool allow_self_loops = false) 
    1.40 +      : gen(&gen), n(n), k(k), prob(prob), source(0), 
    1.41 +        target(allow_self_loops? 0 : 1), 
    1.42 +        allow_self_loops(allow_self_loops), 
    1.43 +        current(0, allow_self_loops? 0 : 1)
    1.44 +    { }
    1.45 +
    1.46 +    reference operator*() const { return current; }
    1.47 +    pointer operator->() const { return &current; }
    1.48 +    
    1.49 +    small_world_iterator& operator++()
    1.50 +    { 
    1.51 +      target = (target + 1) % n;
    1.52 +      if (target == (source + k/2 + 1) % n) {
    1.53 +        ++source;
    1.54 +        if (allow_self_loops) target = source;
    1.55 +        else target = (source + 1) % n;
    1.56 +      }
    1.57 +      current.first = source;
    1.58 +
    1.59 +      uniform_01<RandomGenerator, double> rand01(*gen);
    1.60 +      uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);
    1.61 +      double x = rand01();
    1.62 +      *gen = rand01.base(); // GRRRR
    1.63 +      if (x < prob) {
    1.64 +        vertices_size_type lower = (source + n - k/2) % n;
    1.65 +        vertices_size_type upper = (source + k/2) % n;
    1.66 +        do {
    1.67 +          current.second = rand_vertex_gen(*gen);
    1.68 +        } while (current.second >= lower && current.second <= upper
    1.69 +                 || (upper < lower 
    1.70 +                     && (current.second >= lower || current.second <= upper)));
    1.71 +      } else {
    1.72 +        current.second = target;
    1.73 +      }
    1.74 +      return *this;
    1.75 +    }
    1.76 +
    1.77 +    small_world_iterator operator++(int)
    1.78 +    {
    1.79 +      small_world_iterator temp(*this);
    1.80 +      ++(*this);
    1.81 +      return temp;
    1.82 +    }
    1.83 +
    1.84 +    bool operator==(const small_world_iterator& other) const
    1.85 +    {
    1.86 +      if (!gen && other.gen) return other == *this;
    1.87 +      else if (gen && !other.gen) return source == n;
    1.88 +      else if (!gen && !other.gen) return true;
    1.89 +      return source == other.source && target == other.target;
    1.90 +    }
    1.91 +
    1.92 +    bool operator!=(const small_world_iterator& other) const
    1.93 +    { return !(*this == other); }
    1.94 +
    1.95 +  private:
    1.96 +    void next()
    1.97 +    {
    1.98 +      uniform_int<vertices_size_type> rand_vertex(0, n-1);
    1.99 +      current.first = rand_vertex(*gen);
   1.100 +      do {
   1.101 +        current.second = rand_vertex(*gen);
   1.102 +      } while (current.first == current.second && !allow_self_loops);
   1.103 +    }
   1.104 +
   1.105 +    RandomGenerator* gen;
   1.106 +    vertices_size_type n;
   1.107 +    vertices_size_type k;
   1.108 +    double prob;
   1.109 +    vertices_size_type source;
   1.110 +    vertices_size_type target;
   1.111 +    bool allow_self_loops;
   1.112 +    value_type current;
   1.113 +  };
   1.114 +
   1.115 +} // end namespace boost
   1.116 +
   1.117 +#endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP