ceph/src/boost/libs/graph/doc/plod_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: Power Law Out Degree (PLOD) 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>plod_iterator</tt>
  32
  33 <br>
  34
  35 <PRE>
  36 template&lt;typename RandomGenerator, typename Graph&gt;
  37 class plod_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   plod_iterator();
  47   plod_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  48                 double alpha, double beta, bool allow_self_loops = false);
  49   // Iterator operations
  50   reference operator*() const;
  51   pointer operator-&gt;() const;
  52   plod_iterator&amp; operator++();
  53   plod_iterator operator++(int);
  54   bool operator==(const plod_iterator&amp; other) const;
  55   bool operator!=(const plod_iterator&amp; other) const;
  56 };
  57 </PRE>
  58
  59 <p> This class template implements a generator for scale-free graphs
  60 using the Power Law Out Degree (PLOD) algorithm
  61   [<a href="bibliography.html#palmer2000">63</a>], suitable for
  62 initializing an <a
  63 href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph
  64 structure with iterator-based initialization. A scale-free graph
  65 typically has a very skewed degree distribution, where few vertices
  66 have a very high degree and a large number of vertices have a very
  67 small degree. Many naturally evolving networks, such as the World
  68 Wide Web, are scale-free graphs, making these graphs a good model for
  69 certain networking problems.</p>
  70
  71 <p>The Power Law Out Degree (PLOD) algorithm generates a scale-free
  72 graph from three parameters, <em>n</em>, <em>alpha</em>, and
  73 <em>beta</em>, by allocating a certain number of degree "credits" to
  74 each vertex, drawn from a power-law distribution. It then creates
  75 edges between vertices, deducting a credit from each involved vertex
  76 (in the undirected case) or the source vertex (in the directed
  77 case). The number of credits assigned to a vertex is:
  78 <em>beta*x<sup>-alpha</sup></em>, where <em>x</em> is a random value
  79 between 0 and <em>n-1</em>. The value of <em>beta</em> controls the
  80 y-intercept of the curve, so that increasing <em>beta</em> increases
  81 the average degree of vertices. The value of <em>alpha</em> controls
  82 how steeply the curve drops off, with larger values indicating a
  83 steeper curve. The web graph, for instance, has <em>alpha ~
  84 2.72</em>.</p>
  85
  86 <h3>Where Defined</h3>
  87
  88 <a href="../../../boost/graph/plod_generator.hpp"><tt>boost/graph/plod_generator.hpp</tt></a>
  89
  90 <h3>Constructors</h3>
  91
  92 <a name="default-constructor"/>
  93 <pre>plod_iterator();</pre>
  94 <blockquote>
  95 Constructs a past-the-end iterator.
  96 </blockquote>
  97
  98 <pre>
  99 plod_iterator(RandomGenerator&amp; gen, vertices_size_type n,
 100               double alpha, double beta, bool allow_self_loops = false);
 101 </pre>
 102 <blockquote>
 103 Constructs a PLOD generator iterator that creates a
 104 graph with <tt>n</tt> vertices. Probabilities are drawn from the
 105 random number generator <tt>gen</tt>. Self-loops are permitted only
 106 when <tt>allow_self_loops</tt> is <tt>true</tt>.
 107 </blockquote>
 108
 109 <H3>Example</H3>
 110
 111 <pre>
 112 #include &lt;boost/graph/adjacency_list.hpp&gt;
 113 #include &lt;boost/graph/plod_generator.hpp&gt;
 114 #include &lt;boost/random/linear_congruential.hpp&gt;
 115
 116 typedef boost::adjacency_list&lt;&gt; Graph;
 117 typedef boost::plod_iterator&lt;boost::minstd_rand, Graph&gt; SFGen;
 118
 119 int main()
 120 {
 121   boost::minstd_rand gen;
 122   // Create graph with 100 nodes
 123   Graph g(SFGen(gen, 100, 2.5, 1000), SFGen(), 100);
 124   return 0;
 125 }
 126 </pre>
 127
 128 <br>
 129 <HR>
 130 <TABLE>
 131 <TR valign=top>
 132 <TD nowrap>Copyright &copy; 2005</TD><TD>
 133 <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>
 134   <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 135 Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 136 </TD></TR></TABLE>
 137
 138 </BODY>
 139 </HTML>