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
|
<HTML>
<!--
-- Copyright (c) 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
-- Andrew Lumsdaine
-->
<Head>
<Title>Boost Graph Library: Small World 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>small_world_iterator</tt>
<br>
<PRE>
template<typename RandomGenerator, typename Graph>
class small_world_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;
small_world_iterator();
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
vertices_size_type k, double probability,
bool allow_self_loops = false);
// Iterator operations
reference operator*() const;
pointer operator->() const;
small_world_iterator& operator++();
small_world_iterator operator++(int);
bool operator==(const small_world_iterator& other) const;
bool operator!=(const small_world_iterator& other) const;
};
</PRE>
<p> This class template implements a generator for small-world graphs,
suitable for initializing an <a
href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph
structure with iterator-based initialization. A small-world graph
consists of a ring graph (where each vertex is connected to its
<em>k</em> nearest neighbors). Edges in the graph are randomly
rewired to different vertices with a probability
<em>p</em>. Small-world graphs exhibit a high clustering coefficient
(because vertices are always connected to their closest neighbors),
but rewiring ensures a small diameter.</p>
<h3>Where Defined</h3>
<a href="../../../boost/graph/small_world_generator.hpp"><tt>boost/graph/small_world_generator.hpp</tt></a>
<h3>Constructors</h3>
<a name="default-constructor"/>
<pre>small_world_iterator();</pre>
<blockquote>
Constructs a past-the-end iterator.
</blockquote>
<pre>
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
vertices_size_type k, double probability,
bool allow_self_loops = false);
</pre>
<blockquote>
Constructs a small-world generator iterator that creates a
graph with <tt>n</tt> vertices, each connected to its <tt>k</tt>
nearest neighbors. Probabilities are drawn from 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/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>
typedef boost::adjacency_list<> Graph;
typedef boost::small_world_iterator<boost::minstd_rand, Graph> SWGen;
int main()
{
boost::minstd_rand gen;
// Create graph with 100 nodes
Graph g(SWGen(gen, 100, 6, 0.03), SWGen(), 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>
|
