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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
<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>
|
