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

Revision 857, 2.9 KB checked in by igarcia, 19 years ago (diff)
Line 
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
19namespace 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
Note: See TracBrowser for help on using the repository browser.