Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/plod_generator.html @ 45

Last change on this file since 45 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 4.6 KB
Line 
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<!--
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>plod_iterator</tt>
32
33<br>
34
35<PRE>
36template&lt;typename RandomGenerator, typename Graph&gt;
37class plod_iterator
38{
39public:
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
60using the Power Law Out Degree (PLOD) algorithm
61  [<a href="bibliography.html#palmer2000">63</a>], suitable for
62initializing an <a
63href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph
64structure with iterator-based initialization. A scale-free graph
65typically has a very skewed degree distribution, where few vertices
66have a very high degree and a large number of vertices have a very
67small degree. Many naturally evolving networks, such as the World
68Wide Web, are scale-free graphs, making these graphs a good model for
69certain networking problems.</p>
70
71<p>The Power Law Out Degree (PLOD) algorithm generates a scale-free
72graph from three parameters, <em>n</em>, <em>alpha</em>, and
73<em>beta</em>, by allocating a certain number of degree "credits" to
74each vertex, drawn from a power-law distribution. It then creates
75edges between vertices, deducting a credit from each involved vertex
76(in the undirected case) or the source vertex (in the directed
77case). 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
79between 0 and <em>n-1</em>. The value of <em>beta</em> controls the
80y-intercept of the curve, so that increasing <em>beta</em> increases
81the average degree of vertices. The value of <em>alpha</em> controls
82how steeply the curve drops off, with larger values indicating a
83steeper curve. The web graph, for instance, has <em>alpha ~
842.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>
95Constructs a past-the-end iterator.
96</blockquote>
97
98<pre>
99plod_iterator(RandomGenerator&amp; gen, vertices_size_type n,
100              double alpha, double beta, bool allow_self_loops = false);
101</pre>
102<blockquote>
103Constructs a PLOD generator iterator that creates a
104graph with <tt>n</tt> vertices. Probabilities are drawn from the
105random number generator <tt>gen</tt>. Self-loops are permitted only
106when <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
116typedef boost::adjacency_list&lt;&gt; Graph;
117typedef boost::plod_iterator&lt;boost::minstd_rand, Graph&gt; SFGen;
118
119int 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="../../../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>,
135Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
136</TD></TR></TABLE>
137
138</BODY>
139</HTML> 
Note: See TracBrowser for help on using the repository browser.