Boost C++ Libraries

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

Constructors

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);

#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;
}