1<HTML> 2<!-- 3 Copyright (c) 2004, 2005 The Trustees of Indiana University 4 5 Use, modification and distribution is subject to the Boost Software 6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 9 Authors: Douglas Gregor 10 Jeremiah Willcock 11 Andrew Lumsdaine 12 --> 13<Head> 14 <Title>Boost Graph Library: Erdös-Renyi Generator</Title> 15<script language="JavaScript" type="text/JavaScript"> 16<!-- 17function address(host, user) { 18 var atchar = '@'; 19 var thingy = user+atchar+host; 20 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; 21 document.write(thingy); 22} 23//--> 24</script> 25</head> 26 27<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 28 ALINK="#ff0000"> 29<IMG SRC="../../../boost.png" 30 ALT="C++ Boost" width="277" height="86"> 31 32<tt>erdos_renyi_iterator</tt> 33 34<br> 35 36<PRE> 37template<typename RandomGenerator, typename Graph> 38class erdos_renyi_iterator 39{ 40public: 41 typedef std::input_iterator_tag iterator_category; 42 typedef std::pair<vertices_size_type, vertices_size_type> value_type; 43 typedef const value_type& reference; 44 typedef const value_type* pointer; 45 typedef void difference_type; 46 47 erdos_renyi_iterator(); 48 erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 49 double fraction = 0.0, bool allow_self_loops = false); 50 erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 51 edges_size_type m, bool allow_self_loops = false); 52 53 // Iterator operations 54 reference operator*() const; 55 pointer operator->() const; 56 erdos_renyi_iterator& operator++(); 57 erdos_renyi_iterator operator++(int); 58 bool operator==(const erdos_renyi_iterator& other) const; 59 bool operator!=(const erdos_renyi_iterator& other) const; 60}; 61</PRE> 62 63<p> This class template implements a generator for Erdös-Renyi 64graphs, suitable for initializing an <a 65href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph 66structure with iterator-based initialization. An Erdös-Renyi 67graph <em>G = (n, p)</em> is a graph with <em>n</em> vertices 68that. The probability of having an edge <em>(u, v)</em> in <em>G</em> 69is <em>p</em> for any vertices <em>u</em> and <em>v</em>. Typically, 70there are no self-loops, but the generator can optionally introduce 71self-loops with probability <em>p</em>. This generator will not 72produce any parallel edges and will produce edges in sorted order (as 73required by, e.g., the <a 74href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>).</p> 75 76<p>Erdös-Renyi graphs typically exhibit very little 77structure. For this reason, they are rarely useful in modeling 78real-world problems. However, they are often used when determining 79the theoretical complexity of complex graph algorithms.</p> 80 81<p>If you want the possibility of generating parallel edges and don't 82care about sorted order, use the <a 83href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a>.</p> 84 85<h3>Where Defined</h3> 86 87<a href="../../../boost/graph/erdos_renyi_generator.hpp"><tt>boost/graph/erdos_renyi_generator.hpp</tt></a> 88 89<h3>Constructors</h3> 90 91<a name="default-constructor"/> 92<pre>erdos_renyi_iterator();</pre> 93<blockquote> 94Constructs a past-the-end iterator. 95</blockquote> 96 97<pre> 98erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 99 double fraction = 0.0, bool allow_self_loops = false); 100</pre> 101<blockquote> 102Constructs an Erdös-Renyi generator iterator that creates a 103graph with <tt>n</tt> vertices and a given <tt>fraction</tt> of the 104total number of edges that a simple graph may have. 105<tt>probability</tt>. Random vertices and edges are selected using the 106random number generator <tt>gen</tt>. Self-loops are permitted only when 107<tt>allow_self_loops</tt> is <tt>true</tt>. 108</blockquote> 109 110<pre> 111erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, 112 edges_size_type m, bool allow_self_loops = false); 113</pre> 114<blockquote> 115Constructs an Erdös-Renyi generator iterator that creates a 116graph with <tt>n</tt> vertices and <tt>m</tt> edges. 117<tt>probability</tt>. Random vertices and edges are selected using the 118random number generator <tt>gen</tt>. Self-loops are permitted only when 119<tt>allow_self_loops</tt> is <tt>true</tt>. 120</blockquote> 121 122<H3>Example</H3> 123 124<pre> 125#include <boost/graph/adjacency_list.hpp> 126#include <boost/graph/erdos_renyi_generator.hpp> 127#include <boost/random/linear_congruential.hpp> 128 129typedef boost::adjacency_list<> Graph; 130typedef boost::erdos_renyi_iterator<boost::minstd_rand, Graph> ERGen; 131 132int main() 133{ 134 boost::minstd_rand gen; 135 // Create graph with 100 nodes and edges with probability 0.05 136 Graph g(ERGen(gen, 100, 0.05), ERGen(), 100); 137 return 0; 138} 139</pre> 140 141<br> 142<HR> 143<TABLE> 144<TR valign=top> 145<TD nowrap>Copyright © 2005</TD><TD> 146<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> 147 <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 148Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) 149</TD></TR></TABLE> 150 151</BODY> 152</HTML> 153
