Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / erdos_renyi_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_ERDOS_RENYI_GENERATOR_HPP
10 #define BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP
11
12 #include <iterator>
13 #include <utility>
14 #include <boost/random/uniform_int.hpp>
15 #include <boost/graph/graph_traits.hpp>
16 #include <boost/type_traits/is_base_and_derived.hpp>
17 #include <boost/type_traits/is_same.hpp>
18
19 namespace boost {
20
21   template<typename RandomGenerator, typename Graph>
22   class erdos_renyi_iterator
23   {
24     typedef typename graph_traits<Graph>::directed_category directed_category;
25     typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
26     typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
27
28     BOOST_STATIC_CONSTANT
29       (bool,
30        is_undirected = (is_base_and_derived<undirected_tag,
31                                             directed_category>::value
32                         || is_same<undirected_tag, directed_category>::value));
33
34   public:
35     typedef std::input_iterator_tag iterator_category;
36     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
37     typedef const value_type& reference;
38     typedef const value_type* pointer;
39     typedef void difference_type;
40
41     erdos_renyi_iterator() : gen(0), n(0), edges(0), allow_self_loops(false) {}
42     erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 
43                          double prob = 0.0, bool allow_self_loops = false)
44       : gen(&gen), n(n), edges(edges_size_type(prob * n * n)),
45         allow_self_loops(allow_self_loops)
46     { 
47       if (is_undirected) edges = edges / 2;
48       next(); 
49     }
50
51     reference operator*() const { return current; }
52     pointer operator->() const { return &current; }
53     
54     erdos_renyi_iterator& operator++()
55     { 
56       --edges;
57       next();
58       return *this;
59     }
60
61     erdos_renyi_iterator operator++(int)
62     {
63       erdos_renyi_iterator temp(*this);
64       ++(*this);
65       return temp;
66     }
67
68     bool operator==(const erdos_renyi_iterator& other) const
69     { return edges == other.edges; }
70
71     bool operator!=(const erdos_renyi_iterator& other) const
72     { return !(*this == other); }
73
74   private:
75     void next()
76     {
77       uniform_int<vertices_size_type> rand_vertex(0, n-1);
78       current.first = rand_vertex(*gen);
79       do {
80         current.second = rand_vertex(*gen);
81       } while (current.first == current.second && !allow_self_loops);
82     }
83
84     RandomGenerator* gen;
85     vertices_size_type n;
86     edges_size_type edges;
87     bool allow_self_loops;
88     value_type current;
89   };
90
91 } // end namespace boost
92
93 #endif // BOOST_GRAPH_ERDOS_RENYI_GENERATOR_HPP