bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / graph_parallel / doc / sorted_unique_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| Sorted unique R-MAT generator
====================================

::
 
  template<typename RandomGenerator, typename Graph,
           typename EdgePredicate = keep_all_edges>
  class sorted_unique_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;

    sorted_unique_rmat_iterator();
    sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                                edges_size_type m, double a, double b, double c, 
                                double d, bool bidirectional = true,
                                bool permute_vertices = true,
                                EdgePredicate ep = keep_all_edges());
    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    sorted_unique_rmat_iterator& operator++();
    sorted_unique_rmat_iterator operator++(int);
    bool operator==(const sorted_unique_rmat_iterator& other) const;
    bool operator!=(const sorted_unique_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.  The output of this generator is sorted
for use with a `compressed sparse row graph`_. The edge list produced by
this iterator is guaranteed not to contain parallel edges.

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

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

::

  sorted_unique_rmat_iterator();

Constructs a past-the-end iterator.

::

  sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                              edges_size_type m, double a, double b, double c, 
                              double d, bool bidirectional = false, 
                              bool permute_vertices = true,
                              EdgePredicate ep = keep_all_edges());

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  ``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.
When ``bidirectional`` is ``true`` for every edge s-t, the
corresponding anti-edge t-s is added as well, these anti-edges are not
counted towards ``m``. ``ep`` allows the user to specify which edges
are retained, this is useful in the case where the user wishes to
refrain from storing remote edges locally during generation to reduce
memory consumption.

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 keep_local_edges<boost::parallel::variant_distribution<mpi_process_group>,
                           mpi_process_group::process_id_type> EdgeFilter; 
  typedef boost::sorted_unique_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);

    mpi_process_group::process_id_type id = process_id(pg);

    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true, 
                    true, EdgeFilter(distrib, id)), 
            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 and Andrew Lumsdaine

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

.. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html