sorted_erdos_renyi_iterator

template<typename RandomGenerator, typename Graph>
class sorted_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;

  sorted_erdos_renyi_iterator();
  sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                              double probability = 0.0, bool allow_self_loops = false);

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

此类模板实现了一个 Erdös-Renyi 图的生成器，适用于使用基于迭代器的初始化来初始化 adjacency_list 或其他图形结构。一个 Erdös-Renyi 图 G = (n, p) 是一个具有 n 个顶点的图，使得在 G 中存在边 (u, v) 的概率为 p，对于任何顶点 u 和 v 来说。 通常，没有自环，但生成器可以选择性地以概率 p 引入自环。

Erdös-Renyi 图通常表现出很少的结构。因此，它们很少用于模拟现实世界中的问题。 但是，它们通常用于确定复杂图形算法的理论复杂度。

定义位置

boost/graph/erdos_renyi_generator.hpp

构造函数

sorted_erdos_renyi_iterator();

构造一个超出末尾的迭代器。

sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                            double probability = 0.0, bool allow_self_loops = false);

构造一个 Erdös-Renyi 生成器迭代器，该迭代器创建一个具有n个顶点和给定的概率的简单图可能拥有的总边数。随机顶点和边是使用随机数生成器选择的。gen中抽取。自环仅在allow_self_loops是true.

示例

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

版权 © 2005

Jeremiah Willcock, Indiana University () Doug Gregor, Indiana University () Andrew Lumsdaine, Indiana University ()