1<HTML> 2<!-- 3 Copyright (c) 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 Andrew Lumsdaine 11 --> 12<Head> 13 <Title>Boost Graph Library: Small World Generator</Title> 14<script language="JavaScript" type="text/JavaScript"> 15<!-- 16function address(host, user) { 17 var atchar = '@'; 18 var thingy = user+atchar+host; 19 thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>'; 20 document.write(thingy); 21} 22//--> 23</script> 24</head> 25 26<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 27 ALINK="#ff0000"> 28<IMG SRC="../../../boost.png" 29 ALT="C++ Boost" width="277" height="86"> 30 31<tt>small_world_iterator</tt> 32 33<br> 34 35<PRE> 36template<typename RandomGenerator, typename Graph> 37class small_world_iterator 38{ 39public: 40 typedef std::input_iterator_tag iterator_category; 41 typedef std::pair<vertices_size_type, vertices_size_type> value_type; 42 typedef const value_type& reference; 43 typedef const value_type* pointer; 44 typedef void difference_type; 45 46 small_world_iterator(); 47 small_world_iterator(RandomGenerator& gen, vertices_size_type n, 48 vertices_size_type k, double probability = 0., 49 bool allow_self_loops = false); 50 // Iterator operations 51 reference operator*() const; 52 pointer operator->() const; 53 small_world_iterator& operator++(); 54 small_world_iterator operator++(int); 55 bool operator==(const small_world_iterator& other) const; 56 bool operator!=(const small_world_iterator& other) const; 57}; 58</PRE> 59 60<p> This class template implements a generator for small-world graphs, 61suitable for initializing an <a 62href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph 63structure with iterator-based initialization. A small-world graph 64consists of a ring graph (where each vertex is connected to its 65<em>k</em> nearest neighbors). Edges in the graph are randomly 66rewired to different vertices with a probability 67<em>p</em>. Small-world graphs exhibit a high clustering coefficient 68(because vertices are always connected to their closest neighbors), 69but rewiring ensures a small diameter.</p> 70 71<h3>Where Defined</h3> 72 73<a href="../../../boost/graph/small_world_generator.hpp"><tt>boost/graph/small_world_generator.hpp</tt></a> 74 75<h3>Constructors</h3> 76 77<a name="default-constructor"/> 78<pre>small_world_iterator();</pre> 79<blockquote> 80Constructs a past-the-end iterator. 81</blockquote> 82 83<pre> 84small_world_iterator(RandomGenerator& gen, vertices_size_type n, 85 vertices_size_type k, double probability = 0., 86 bool allow_self_loops = false); 87</pre> 88<blockquote> 89Constructs a small-world generator iterator that creates a 90graph with <tt>n</tt> vertices, each connected to its <tt>k</tt> 91nearest neighbors. Probabilities are drawn from the 92random number generator <tt>gen</tt>. Self-loops are permitted only 93when <tt>allow_self_loops</tt> is <tt>true</tt>. 94</blockquote> 95 96<H3>Example</H3> 97 98<pre> 99#include <boost/graph/adjacency_list.hpp> 100#include <boost/graph/small_world_generator.hpp> 101#include <boost/random/linear_congruential.hpp> 102 103typedef boost::adjacency_list<> Graph; 104typedef boost::small_world_iterator<boost::minstd_rand, Graph> SWGen; 105 106int main() 107{ 108 boost::minstd_rand gen; 109 // Create graph with 100 nodes 110 Graph g(SWGen(gen, 100, 6, 0.03), SWGen(), 100); 111 return 0; 112} 113</pre> 114 115<br> 116<HR> 117<TABLE> 118<TR valign=top> 119<TD nowrap>Copyright © 2005</TD><TD> 120<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> 121 <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 122Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) 123</TD></TR></TABLE> 124 125</BODY> 126</HTML> 127
