Boost Graph Library: Small World Generator

`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 ( )