<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: Power Law Out Degree (PLOD) 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>plod_iterator</tt> <br> <PRE> template<typename RandomGenerator, typename Graph> class plod_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; plod_iterator(); plod_iterator(RandomGenerator& gen, vertices_size_type n, double alpha, double beta, bool allow_self_loops = false); // Iterator operations reference operator*() const; pointer operator->() const; plod_iterator& operator++(); plod_iterator operator++(int); bool operator==(const plod_iterator& other) const; bool operator!=(const plod_iterator& other) const; }; </PRE> <p> This class template implements a generator for scale-free graphs using the Power Law Out Degree (PLOD) algorithm [<a href="bibliography.html#palmer2000">63</a>], suitable for initializing an <a href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph structure with iterator-based initialization. A scale-free graph typically has a very skewed degree distribution, where few vertices have a very high degree and a large number of vertices have a very small degree. Many naturally evolving networks, such as the World Wide Web, are scale-free graphs, making these graphs a good model for certain networking problems.</p> <p>The Power Law Out Degree (PLOD) algorithm generates a scale-free graph from three parameters, <em>n</em>, <em>alpha</em>, and <em>beta</em>, by allocating a certain number of degree "credits" to each vertex, drawn from a power-law distribution. It then creates edges between vertices, deducting a credit from each involved vertex (in the undirected case) or the source vertex (in the directed case). The number of credits assigned to a vertex is: <em>beta*x<sup>-alpha</sup></em>, where <em>x</em> is a random value between 0 and <em>n-1</em>. The value of <em>beta</em> controls the y-intercept of the curve, so that increasing <em>beta</em> increases the average degree of vertices. The value of <em>alpha</em> controls how steeply the curve drops off, with larger values indicating a steeper curve. The web graph, for instance, has <em>alpha ~ 2.72</em>.</p> <h3>Where Defined</h3> <a href="../../../boost/graph/plod_generator.hpp"><tt>boost/graph/plod_generator.hpp</tt></a> <h3>Constructors</h3> <a name="default-constructor"/> <pre>plod_iterator();</pre> <blockquote> Constructs a past-the-end iterator. </blockquote> <pre> plod_iterator(RandomGenerator& gen, vertices_size_type n, double alpha, double beta, bool allow_self_loops = false); </pre> <blockquote> Constructs a PLOD generator iterator that creates a graph with <tt>n</tt> vertices. 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/plod_generator.hpp> #include <boost/random/linear_congruential.hpp> typedef boost::adjacency_list<> Graph; typedef boost::plod_iterator<boost::minstd_rand, Graph> SFGen; int main() { boost::minstd_rand gen; // Create graph with 100 nodes Graph g(SFGen(gen, 100, 2.5, 1000), SFGen(), 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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>) </TD></TR></TABLE> </BODY> </HTML>