bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / scalable_rmat_generator.rst

.. Copyright (C) 2004-2009 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)

===================================
|Logo| Scalable R-MAT generator
===================================

::
 
  template<typename ProcessGroup, typename Distribution, 
           typename RandomGenerator, typename Graph>
  class scalable_rmat_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;

    scalable_rmat_iterator();
    scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
                           RandomGenerator& gen, vertices_size_type n, 
                           edges_size_type m, double a, double b, double c, 
                           double d, bool permute_vertices = true);

    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    scalable_rmat_iterator& operator++();
    scalable_rmat_iterator operator++(int);
    bool operator==(const scalable_rmat_iterator& other) const;
    bool operator!=(const scalable_rmat_iterator& other) const;
 };

This class template implements a generator for R-MAT graphs [CZF04]_,
suitable for initializing an adjacency_list or other graph structure
with iterator-based initialization. An R-MAT graph has a scale-free
distribution w.r.t. vertex degree and is implemented using
Recursive-MATrix partitioning.

Where Defined
-------------
<``boost/graph/rmat_graph_generator.hpp``>

Constructors
------------

::

  scalable_rmat_iterator();

Constructs a past-the-end iterator.

::

  scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
                         RandomGenerator& gen, vertices_size_type n, 
                         edges_size_type m, double a, double b, double c, 
                         double d, bool permute_vertices = true);

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  Inside the ``scalable_rmat_iterator``
processes communicate using ``pg`` to generate their local edges as
defined by ``distrib``.  ``a``, ``b``, ``c``, and ``d`` represent the
probability that a generated edge is placed of each of the 4 quadrants
of the partitioned adjacency matrix.  Probabilities are drawn from the
random number generator ``gen``.  Vertex indices are permuted to
eliminate locality when ``permute_vertices`` is true.

Example
-------

::

  #include <boost/graph/distributed/mpi_process_group.hpp>
  #include <boost/graph/compressed_sparse_row_graph.hpp>
  #include <boost/graph/rmat_graph_generator.hpp>
  #include <boost/random/linear_congruential.hpp>

  using boost::graph::distributed::mpi_process_group;

  typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
                                      distributedS<mpi_process_group> > Graph;
  typedef boost::scalable_rmat_iterator<boost::minstd_rand, Graph> RMATGen;

  int main()
  {
    boost::minstd_rand gen;
    mpi_process_group pg;

    int N = 100;

    boost::parallel::variant_distribution<ProcessGroup> distrib 
      = boost::parallel::block(pg, N);

    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(pg, distrib, gen, N, 400, 0.57, 0.19, 0.19, 0.05), 
            RMATGen(), N, pg, distrib);
    return 0;
  }

Bibliography
------------

.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
  Model for Graph Mining. In Proceedings of 4th International Conference
  on Data Mining, pages 442--446, 2004.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds, Brian Barrett, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Sequential connected components: http://www.boost.org/libs/graph/doc/connected_components.html