ceph/src/boost/libs/graph/doc/small_world_generator.html

   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 <!--
  16 function 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>
  36 template&lt;typename RandomGenerator, typename Graph&gt;
  37 class small_world_iterator
  38 {
  39 public:
  40   typedef std::input_iterator_tag iterator_category;
  41   typedef std::pair&lt;vertices_size_type, vertices_size_type&gt; value_type;
  42   typedef const value_type&amp; reference;
  43   typedef const value_type* pointer;
  44   typedef void difference_type;
  45
  46   small_world_iterator();
  47   small_world_iterator(RandomGenerator&amp; 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-&gt;() const;
  53   small_world_iterator&amp; operator++();
  54   small_world_iterator operator++(int);
  55   bool operator==(const small_world_iterator&amp; other) const;
  56   bool operator!=(const small_world_iterator&amp; other) const;
  57 };
  58 </PRE>
  59
  60 <p> This class template implements a generator for small-world graphs,
  61 suitable for initializing an <a
  62 href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph
  63 structure with iterator-based initialization. A small-world graph
  64 consists of a ring graph (where each vertex is connected to its
  65 <em>k</em> nearest neighbors). Edges in the graph are randomly
  66 rewired 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),
  69 but 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>
  80 Constructs a past-the-end iterator.
  81 </blockquote>
  82
  83 <pre>
  84 small_world_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  85                      vertices_size_type k, double probability = 0.,
  86                      bool allow_self_loops = false);
  87 </pre>
  88 <blockquote>
  89 Constructs a small-world generator iterator that creates a
  90 graph with <tt>n</tt> vertices, each connected to its <tt>k</tt>
  91 nearest neighbors. Probabilities are drawn from the
  92 random number generator <tt>gen</tt>. Self-loops are permitted only
  93 when <tt>allow_self_loops</tt> is <tt>true</tt>.
  94 </blockquote>
  95
  96 <H3>Example</H3>
  97
  98 <pre>
  99 #include &lt;boost/graph/adjacency_list.hpp&gt;
 100 #include &lt;boost/graph/small_world_generator.hpp&gt;
 101 #include &lt;boost/random/linear_congruential.hpp&gt;
 102
 103 typedef boost::adjacency_list&lt;&gt; Graph;
 104 typedef boost::small_world_iterator&lt;boost::minstd_rand, Graph&gt; SWGen;
 105
 106 int 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 &copy; 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 122 Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 123 </TD></TR></TABLE>
 124
 125 </BODY>
 126 </HTML>