]>
Commit | Line | Data |
---|---|---|
1 | <HTML> | |
2 | <!-- | |
3 | Copyright (c) 2004, 2005 The Trustees of Indiana University | |
4 | ||
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) | |
8 | ||
9 | Authors: Douglas Gregor | |
10 | Jeremiah Willcock | |
11 | Andrew Lumsdaine | |
12 | --> | |
13 | <Head> | |
14 | <Title>Boost Graph Library: Erdös-Renyi Generator</Title> | |
15 | <script language="JavaScript" type="text/JavaScript"> | |
16 | <!-- | |
17 | function address(host, user) { | |
18 | var atchar = '@'; | |
19 | var thingy = user+atchar+host; | |
20 | thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; | |
21 | document.write(thingy); | |
22 | } | |
23 | //--> | |
24 | </script> | |
25 | </head> | |
26 | ||
27 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
28 | ALINK="#ff0000"> | |
29 | <IMG SRC="../../../boost.png" | |
30 | ALT="C++ Boost" width="277" height="86"> | |
31 | ||
32 | <tt>erdos_renyi_iterator</tt> | |
33 | ||
34 | <br> | |
35 | ||
36 | <PRE> | |
37 | template<typename RandomGenerator, typename Graph> | |
38 | class erdos_renyi_iterator | |
39 | { | |
40 | public: | |
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; | |
46 | ||
47 | erdos_renyi_iterator(); | |
48 | erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, | |
49 | double fraction = 0.0, bool allow_self_loops = false); | |
50 | erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, | |
51 | edges_size_type m, bool allow_self_loops = false); | |
52 | ||
53 | // Iterator operations | |
54 | reference operator*() const; | |
55 | pointer operator->() const; | |
56 | erdos_renyi_iterator& operator++(); | |
57 | erdos_renyi_iterator operator++(int); | |
58 | bool operator==(const erdos_renyi_iterator& other) const; | |
59 | bool operator!=(const erdos_renyi_iterator& other) const; | |
60 | }; | |
61 | </PRE> | |
62 | ||
63 | <p> This class template implements a generator for Erdös-Renyi | |
64 | graphs, suitable for initializing an <a | |
65 | href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph | |
66 | structure with iterator-based initialization. An Erdös-Renyi | |
67 | graph <em>G = (n, p)</em> is a graph with <em>n</em> vertices | |
68 | that. The probability of having an edge <em>(u, v)</em> in <em>G</em> | |
69 | is <em>p</em> for any vertices <em>u</em> and <em>v</em>. Typically, | |
70 | there are no self-loops, but the generator can optionally introduce | |
71 | self-loops with probability <em>p</em>. This generator will not | |
72 | produce any parallel edges and will produce edges in sorted order (as | |
73 | required by, e.g., the <a | |
74 | href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>).</p> | |
75 | ||
76 | <p>Erdös-Renyi graphs typically exhibit very little | |
77 | structure. For this reason, they are rarely useful in modeling | |
78 | real-world problems. However, they are often used when determining | |
79 | the theoretical complexity of complex graph algorithms.</p> | |
80 | ||
81 | <p>If you want the possibility of generating parallel edges and don't | |
82 | care about sorted order, use the <a | |
83 | href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a>.</p> | |
84 | ||
85 | <h3>Where Defined</h3> | |
86 | ||
87 | <a href="../../../boost/graph/erdos_renyi_generator.hpp"><tt>boost/graph/erdos_renyi_generator.hpp</tt></a> | |
88 | ||
89 | <h3>Constructors</h3> | |
90 | ||
91 | <a name="default-constructor"/> | |
92 | <pre>erdos_renyi_iterator();</pre> | |
93 | <blockquote> | |
94 | Constructs a past-the-end iterator. | |
95 | </blockquote> | |
96 | ||
97 | <pre> | |
98 | erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, | |
99 | double fraction = 0.0, bool allow_self_loops = false); | |
100 | </pre> | |
101 | <blockquote> | |
102 | Constructs an Erdös-Renyi generator iterator that creates a | |
103 | graph with <tt>n</tt> vertices and a given <tt>fraction</tt> of the | |
104 | total number of edges that a simple graph may have. | |
105 | <tt>probability</tt>. Random vertices and edges are selected using the | |
106 | random number generator <tt>gen</tt>. Self-loops are permitted only when | |
107 | <tt>allow_self_loops</tt> is <tt>true</tt>. | |
108 | </blockquote> | |
109 | ||
110 | <pre> | |
111 | erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n, | |
112 | edges_size_type m, bool allow_self_loops = false); | |
113 | </pre> | |
114 | <blockquote> | |
115 | Constructs an Erdös-Renyi generator iterator that creates a | |
116 | graph with <tt>n</tt> vertices and <tt>m</tt> edges. | |
117 | <tt>probability</tt>. Random vertices and edges are selected using the | |
118 | random number generator <tt>gen</tt>. Self-loops are permitted only when | |
119 | <tt>allow_self_loops</tt> is <tt>true</tt>. | |
120 | </blockquote> | |
121 | ||
122 | <H3>Example</H3> | |
123 | ||
124 | <pre> | |
125 | #include <boost/graph/adjacency_list.hpp> | |
126 | #include <boost/graph/erdos_renyi_generator.hpp> | |
127 | #include <boost/random/linear_congruential.hpp> | |
128 | ||
129 | typedef boost::adjacency_list<> Graph; | |
130 | typedef boost::erdos_renyi_iterator<boost::minstd_rand, Graph> ERGen; | |
131 | ||
132 | int main() | |
133 | { | |
134 | boost::minstd_rand gen; | |
135 | // Create graph with 100 nodes and edges with probability 0.05 | |
136 | Graph g(ERGen(gen, 100, 0.05), ERGen(), 100); | |
137 | return 0; | |
138 | } | |
139 | </pre> | |
140 | ||
141 | <br> | |
142 | <HR> | |
143 | <TABLE> | |
144 | <TR valign=top> | |
145 | <TD nowrap>Copyright © 2005</TD><TD> | |
146 | <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> | |
147 | <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, | |
148 | Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) | |
149 | </TD></TR></TABLE> | |
150 | ||
151 | </BODY> | |
152 | </HTML> |