153 lines
5.3 KiB
HTML
153 lines
5.3 KiB
HTML
<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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
|
|
Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|