| <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: Douglas Gregor |
| Jeremiah Willcock |
| 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>erdos_renyi_iterator</tt> |
| |
| <br> |
| |
| <PRE> |
| 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; |
| }; |
| </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>. This generator will not |
| produce any parallel edges and will produce edges in sorted order (as |
| required by, e.g., the <a |
| href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>).</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> |
| |
| <p>If you want the possibility of generating parallel edges and don't |
| care about sorted order, use the <a |
| href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a>.</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>erdos_renyi_iterator();</pre> |
| <blockquote> |
| Constructs a past-the-end iterator. |
| </blockquote> |
| |
| <pre> |
| erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, |
| double fraction = 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>fraction</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> |
| |
| <pre> |
| erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, |
| edges_size_type m, bool allow_self_loops = false); |
| </pre> |
| <blockquote> |
| Constructs an Erdös-Renyi generator iterator that creates a |
| graph with <tt>n</tt> vertices and <tt>m</tt> edges. |
| <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::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> |
| <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> |