Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / small_world_generator.hpp
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_SMALL_WORLD_GENERATOR_HPP
10 #define BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP
11
12 #include <iterator>
13 #include <utility>
14 #include <boost/random/uniform_01.hpp>
15 #include <boost/random/uniform_int.hpp>
16
17 namespace boost {
18
19   // Assumes undirected
20   template<typename RandomGenerator, typename Graph>
21   class small_world_iterator
22   {
23     typedef typename graph_traits<Graph>::vertices_size_type 
24       vertices_size_type;
25
26   public:
27     typedef std::input_iterator_tag iterator_category;
28     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
29     typedef const value_type& reference;
30     typedef const value_type* pointer;
31     typedef void difference_type;
32
33     small_world_iterator() : gen(0) {}
34     small_world_iterator(RandomGenerator& gen, vertices_size_type n, 
35                          vertices_size_type k, double prob = 0.0, 
36                          bool allow_self_loops = false) 
37       : gen(&gen), n(n), k(k), prob(prob), source(0), 
38         target(allow_self_loops? 0 : 1), 
39         allow_self_loops(allow_self_loops), 
40         current(0, allow_self_loops? 0 : 1)
41     { }
42
43     reference operator*() const { return current; }
44     pointer operator->() const { return &current; }
45     
46     small_world_iterator& operator++()
47     { 
48       target = (target + 1) % n;
49       if (target == (source + k/2 + 1) % n) {
50         ++source;
51         if (allow_self_loops) target = source;
52         else target = (source + 1) % n;
53       }
54       current.first = source;
55
56       uniform_01<RandomGenerator, double> rand01(*gen);
57       uniform_int<vertices_size_type> rand_vertex_gen(0, n-1);
58       double x = rand01();
59       *gen = rand01.base(); // GRRRR
60       if (x < prob) {
61         vertices_size_type lower = (source + n - k/2) % n;
62         vertices_size_type upper = (source + k/2) % n;
63         do {
64           current.second = rand_vertex_gen(*gen);
65         } while (current.second >= lower && current.second <= upper
66                  || (upper < lower 
67                      && (current.second >= lower || current.second <= upper)));
68       } else {
69         current.second = target;
70       }
71       return *this;
72     }
73
74     small_world_iterator operator++(int)
75     {
76       small_world_iterator temp(*this);
77       ++(*this);
78       return temp;
79     }
80
81     bool operator==(const small_world_iterator& other) const
82     {
83       if (!gen && other.gen) return other == *this;
84       else if (gen && !other.gen) return source == n;
85       else if (!gen && !other.gen) return true;
86       return source == other.source && target == other.target;
87     }
88
89     bool operator!=(const small_world_iterator& other) const
90     { return !(*this == other); }
91
92   private:
93     void next()
94     {
95       uniform_int<vertices_size_type> rand_vertex(0, n-1);
96       current.first = rand_vertex(*gen);
97       do {
98         current.second = rand_vertex(*gen);
99       } while (current.first == current.second && !allow_self_loops);
100     }
101
102     RandomGenerator* gen;
103     vertices_size_type n;
104     vertices_size_type k;
105     double prob;
106     vertices_size_type source;
107     vertices_size_type target;
108     bool allow_self_loops;
109     value_type current;
110   };
111
112 } // end namespace boost
113
114 #endif // BOOST_GRAPH_SMALL_WORLD_GENERATOR_HPP