1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
<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>
|
