3 Copyright (c) 2004, 2005 The Trustees of Indiana University
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)
9 Authors: Jeremiah Willcock
14 <Title>Boost Graph Library: Erd
ös-Renyi Generator
</Title>
15 <script language=
"JavaScript" type=
"text/JavaScript">
17 function address(host, user) {
19 var thingy = user+atchar+host;
20 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
21 document.write(thingy);
27 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
29 <IMG SRC=
"../../../boost.png"
30 ALT=
"C++ Boost" width=
"277" height=
"86">
32 <tt>sorted_erdos_renyi_iterator
</tt>
37 template
<typename RandomGenerator, typename Graph
>
38 class sorted_erdos_renyi_iterator
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;
47 sorted_erdos_renyi_iterator();
48 sorted_erdos_renyi_iterator(RandomGenerator
& gen, vertices_size_type n,
49 double probability =
0.0, bool allow_self_loops = false);
51 // Iterator operations
52 reference operator*() const;
53 pointer operator-
>() const;
54 sorted_erdos_renyi_iterator
& operator++();
55 sorted_erdos_renyi_iterator operator++(int);
56 bool operator==(const sorted_erdos_renyi_iterator
& other) const;
57 bool operator!=(const sorted_erdos_renyi_iterator
& other) const;
61 <p> This class template implements a generator for Erd
ös-Renyi
62 graphs, suitable for initializing an
<a
63 href=
"adjacency_list.html"><tt>adjacency_list
</tt></a> or other graph
64 structure with iterator-based initialization. An Erd
ös-Renyi
65 graph
<em>G = (n, p)
</em> is a graph with
<em>n
</em> vertices
66 such that the probability of having an edge
<em>(u, v)
</em> in
<em>G
</em>
67 is
<em>p
</em> for any vertices
<em>u
</em> and
<em>v
</em>. Typically,
68 there are no self-loops, but the generator can optionally introduce
69 self-loops with probability
<em>p
</em>.
</p>
71 <p>Erd
ös-Renyi graphs typically exhibit very little
72 structure. For this reason, they are rarely useful in modeling
73 real-world problems. However, they are often used when determining
74 the theoretical complexity of complex graph algorithms.
</p>
76 <h3>Where Defined
</h3>
78 <a href=
"../../../boost/graph/erdos_renyi_generator.hpp"><tt>boost/graph/erdos_renyi_generator.hpp
</tt></a>
82 <a name=
"default-constructor"/>
83 <pre>sorted_erdos_renyi_iterator();
</pre>
85 Constructs a past-the-end iterator.
89 sorted_erdos_renyi_iterator(RandomGenerator
& gen, vertices_size_type n,
90 double probability =
0.0, bool allow_self_loops = false);
93 Constructs an Erd
ös-Renyi generator iterator that creates a
94 graph with
<tt>n
</tt> vertices and a given
<tt>probability
</tt> of the
95 total number of edges that a simple graph may have.
96 Random vertices and edges are selected using the
97 random number generator
<tt>gen
</tt>. Self-loops are permitted only when
98 <tt>allow_self_loops
</tt> is
<tt>true
</tt>.
104 #include
<boost/graph/adjacency_list.hpp
>
105 #include
<boost/graph/erdos_renyi_generator.hpp
>
106 #include
<boost/random/linear_congruential.hpp
>
108 typedef boost::adjacency_list
<> Graph;
109 typedef boost::sorted_erdos_renyi_iterator
<boost::minstd_rand, Graph
> ERGen;
113 boost::minstd_rand gen;
114 // Create graph with
100 nodes and edges with probability
0.05
115 Graph g(ERGen(gen,
100,
0.05), ERGen(),
100);
124 <TD nowrap
>Copyright
© 2005</TD><TD>
125 Jeremiah Willcock, Indiana University (
<script language=
"Javascript">address(
"cs.indiana.edu",
"jewillco")
</script>)
<br>
127 <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>
128 <A HREF=
"http://www.osl.iu.edu/~lums">Andrew Lumsdaine
</A>,
129 Indiana University (
<script language=
"Javascript">address(
"osl.iu.edu",
"lums")
</script>)