Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
C++ Boost small_world_iterator
template<typename RandomGenerator, typename Graph>
class small_world_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;

  small_world_iterator();
  small_world_iterator(RandomGenerator& gen, vertices_size_type n,
                       vertices_size_type k, double probability,
                       bool allow_self_loops = false);
  // Iterator operations
  reference operator*() const;
  pointer operator->() const;
  small_world_iterator& operator++();
  small_world_iterator operator++(int);
  bool operator==(const small_world_iterator& other) const;
  bool operator!=(const small_world_iterator& other) const;
}; 

This class template implements a generator for small-world graphs, suitable for initializing an adjacency_list or other graph structure with iterator-based initialization. A small-world graph consists of a ring graph (where each vertex is connected to its k nearest neighbors). Edges in the graph are randomly rewired to different vertices with a probability p. Small-world graphs exhibit a high clustering coefficient (because vertices are always connected to their closest neighbors), but rewiring ensures a small diameter.

Where Defined

boost/graph/small_world_generator.hpp

Constructors

small_world_iterator();
Constructs a past-the-end iterator.
small_world_iterator(RandomGenerator& gen, vertices_size_type n,
                     vertices_size_type k, double probability,
                     bool allow_self_loops = false);
Constructs a small-world generator iterator that creates a graph with n vertices, each connected to its k nearest neighbors. Probabilities are drawn from the random number generator gen. Self-loops are permitted only when allow_self_loops is true.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>

typedef boost::adjacency_list<> Graph;
typedef boost::small_world_iterator<boost::minstd_rand, Graph> SWGen;

int main()
{
  boost::minstd_rand gen;
  // Create graph with 100 nodes 
  Graph g(SWGen(gen, 100, 6, 0.03), SWGen(), 100);
  return 0;
}


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