<HTML> <!-- Copyright (c) 2004, 2005 The Trustees of Indiana University Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) Authors: Jeremiah Willcock Douglas Gregor Andrew Lumsdaine --> <Head> <Title>Boost Graph Library: Erdös-Renyi Generator</Title> <script language="JavaScript" type="text/JavaScript"> <!-- function address(host, user) { var atchar = '@'; var thingy = user+atchar+host; thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; document.write(thingy); } //--> </script> </head> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <tt>sorted_erdos_renyi_iterator</tt> <br> <PRE> 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; }; </PRE> <p> This class template implements a generator for Erdös-Renyi graphs, suitable for initializing an <a href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph structure with iterator-based initialization. An Erdös-Renyi graph <em>G = (n, p)</em> is a graph with <em>n</em> vertices that. The probability of having an edge <em>(u, v)</em> in <em>G</em> is <em>p</em> for any vertices <em>u</em> and <em>v</em>. Typically, there are no self-loops, but the generator can optionally introduce self-loops with probability <em>p</em>.</p> <p>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.</p> <h3>Where Defined</h3> <a href="../../../boost/graph/erdos_renyi_generator.hpp"><tt>boost/graph/erdos_renyi_generator.hpp</tt></a> <h3>Constructors</h3> <a name="default-constructor"/> <pre>sorted_erdos_renyi_iterator();</pre> <blockquote> Constructs a past-the-end iterator. </blockquote> <pre> sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, double probability = 0.0, bool allow_self_loops = false); </pre> <blockquote> Constructs an Erdös-Renyi generator iterator that creates a graph with <tt>n</tt> vertices and a given <tt>probability</tt> of the total number of edges that a simple graph may have. <tt>probability</tt>. Random vertices and edges are selected using the random number generator <tt>gen</tt>. Self-loops are permitted only when <tt>allow_self_loops</tt> is <tt>true</tt>. </blockquote> <H3>Example</H3> <pre> #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; } </pre> <br> <HR> <TABLE> <TR valign=top> <TD nowrap>Copyright © 2005</TD><TD> Jeremiah Willcock, Indiana University (<script language="Javascript">address("cs.indiana.edu", "jewillco")</script>)<br> <A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br> <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) </TD></TR></TABLE> </BODY> </HTML>