123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126 |
- <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 = 0.,
- 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 = 0.,
- 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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|