...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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; };

This class template implements a generator for scale-free graphs
using the Power Law Out Degree (PLOD) algorithm
[63], suitable for
initializing an `adjacency_list` 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.

The Power Law Out Degree (PLOD) algorithm generates a scale-free
graph from three parameters, *n*, *alpha*, and
*beta*, 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:
*beta*x ^{-alpha}*, where

plod_iterator();

Constructs a past-the-end iterator.

plod_iterator(RandomGenerator& gen, vertices_size_type n, double alpha, double beta, bool allow_self_loops = false);

Constructs a PLOD generator iterator that creates a graph withnvertices. Probabilities are drawn from the random number generatorgen. Self-loops are permitted only whenallow_self_loopsistrue.

#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; }

Copyright © 2005 |
Doug Gregor, Indiana University () Andrew Lumsdaine, Indiana University () |