Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

C++ Boost erdos_renyi_iterator
template<typename RandomGenerator, typename Graph>
class erdos_renyi_iterator
{
public:
  typedef std::input_iterator_tag iterator_category;
  typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  typedef const value_type& reference;
  typedef const value_type* pointer;
  typedef void difference_type;

  erdos_renyi_iterator();
  erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                       double fraction = 0.0, bool allow_self_loops = false);
  erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                       edges_size_type m, bool allow_self_loops = false);

  // Iterator operations
  reference operator*() const;
  pointer operator->() const;
  erdos_renyi_iterator& operator++();
  erdos_renyi_iterator operator++(int);
  bool operator==(const erdos_renyi_iterator& other) const;
  bool operator!=(const erdos_renyi_iterator& other) const;
};

This class template implements a generator for Erdös-Renyi graphs, suitable for initializing an adjacency_list or other graph structure with iterator-based initialization. An Erdös-Renyi graph G = (n, p) is a graph with n vertices that. The probability of having an edge (u, v) in G is p for any vertices u and v. Typically, there are no self-loops, but the generator can optionally introduce self-loops with probability p. This generator will not produce any parallel edges and will produce edges in sorted order (as required by, e.g., the compressed_sparse_row_graph).

Erdös-Renyi graphs typically exhibit very little structure. For this reason, they are rarely useful in modeling real-world problems. However, they are often used when determining the theoretical complexity of complex graph algorithms.

If you want the possibility of generating parallel edges and don't care about sorted order, use the erdos_renyi_iterator.

Where Defined

boost/graph/erdos_renyi_generator.hpp

Constructors

erdos_renyi_iterator();
Constructs a past-the-end iterator.
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                     double fraction = 0.0, bool allow_self_loops = false);
Constructs an Erdös-Renyi generator iterator that creates a graph with n vertices and a given fraction of the total number of edges that a simple graph may have. probability. Random vertices and edges are selected using the random number generator gen. Self-loops are permitted only when allow_self_loops is true.
erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                     edges_size_type m, bool allow_self_loops = false);
Constructs an Erdös-Renyi generator iterator that creates a graph with n vertices and m edges. probability. Random vertices and edges are selected using the random number generator gen. Self-loops are permitted only when allow_self_loops is true.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>

typedef boost::adjacency_list<> Graph;
typedef boost::erdos_renyi_iterator<boost::minstd_rand, Graph> ERGen;

int main()
{
  boost::minstd_rand gen;
  // Create graph with 100 nodes and edges with probability 0.05
  Graph g(ERGen(gen, 100, 0.05), ERGen(), 100);
  return 0;
}


Copyright © 2005 Doug Gregor, Indiana University ()
Andrew Lumsdaine, Indiana University ()