]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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<typename RandomGenerator, typename Graph> | |
37 | class plod_iterator | |
38 | { | |
39 | public: | |
40 | typedef std::input_iterator_tag iterator_category; | |
41 | typedef std::pair<vertices_size_type, vertices_size_type> value_type; | |
42 | typedef const value_type& reference; | |
43 | typedef const value_type* pointer; | |
44 | typedef void difference_type; | |
45 | ||
46 | plod_iterator(); | |
47 | plod_iterator(RandomGenerator& 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->() const; | |
52 | plod_iterator& operator++(); | |
53 | plod_iterator operator++(int); | |
54 | bool operator==(const plod_iterator& other) const; | |
55 | bool operator!=(const plod_iterator& 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& 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 <boost/graph/adjacency_list.hpp> | |
113 | #include <boost/graph/plod_generator.hpp> | |
114 | #include <boost/random/linear_congruential.hpp> | |
115 | ||
116 | typedef boost::adjacency_list<> Graph; | |
117 | typedef boost::plod_iterator<boost::minstd_rand, Graph> 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 © 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> |