ceph/src/boost/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst

   1 .. Copyright (C) 2004-2009 The Trustees of Indiana University.
   2    Use, modification and distribution is subject to the Boost Software
   3    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4    http://www.boost.org/LICENSE_1_0.txt)
   5
   6 ====================================
   7 |Logo| Sorted unique R-MAT generator
   8 ====================================
   9
  10 ::
  11
  12   template<typename RandomGenerator, typename Graph,
  13            typename EdgePredicate = keep_all_edges>
  14   class sorted_unique_rmat_iterator
  15   {
  16   public:
  17     typedef std::input_iterator_tag iterator_category;
  18     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  19     typedef const value_type& reference;
  20     typedef const value_type* pointer;
  21     typedef void difference_type;
  22
  23     sorted_unique_rmat_iterator();
  24     sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
  25                                 edges_size_type m, double a, double b, double c,
  26                                 double d, bool bidirectional = true,
  27                                 bool permute_vertices = true,
  28                                 EdgePredicate ep = keep_all_edges());
  29     // Iterator operations
  30     reference operator*() const;
  31     pointer operator->() const;
  32     sorted_unique_rmat_iterator& operator++();
  33     sorted_unique_rmat_iterator operator++(int);
  34     bool operator==(const sorted_unique_rmat_iterator& other) const;
  35     bool operator!=(const sorted_unique_rmat_iterator& other) const;
  36  };
  37
  38 This class template implements a generator for R-MAT graphs [CZF04]_,
  39 suitable for initializing an adjacency_list or other graph structure
  40 with iterator-based initialization. An R-MAT graph has a scale-free
  41 distribution w.r.t. vertex degree and is implemented using
  42 Recursive-MATrix partitioning.  The output of this generator is sorted
  43 for use with a `compressed sparse row graph`_. The edge list produced by
  44 this iterator is guaranteed not to contain parallel edges.
  45
  46 Where Defined
  47 -------------
  48 <``boost/graph/rmat_graph_generator.hpp``>
  49
  50 Constructors
  51 ------------
  52
  53 ::
  54
  55   sorted_unique_rmat_iterator();
  56
  57 Constructs a past-the-end iterator.
  58
  59 ::
  60
  61   sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
  62                               edges_size_type m, double a, double b, double c,
  63                               double d, bool bidirectional = false,
  64                               bool permute_vertices = true,
  65                               EdgePredicate ep = keep_all_edges());
  66
  67 Constructs an R-MAT generator iterator that creates a graph with ``n``
  68 vertices and ``m`` edges.  ``a``, ``b``, ``c``, and ``d`` represent
  69 the probability that a generated edge is placed of each of the 4
  70 quadrants of the partitioned adjacency matrix.  Probabilities are
  71 drawn from the random number generator ``gen``.  Vertex indices are
  72 permuted to eliminate locality when ``permute_vertices`` is true.
  73 When ``bidirectional`` is ``true`` for every edge s-t, the
  74 corresponding anti-edge t-s is added as well, these anti-edges are not
  75 counted towards ``m``. ``ep`` allows the user to specify which edges
  76 are retained, this is useful in the case where the user wishes to
  77 refrain from storing remote edges locally during generation to reduce
  78 memory consumption.
  79
  80 Example
  81 -------
  82
  83 ::
  84
  85   #include <boost/graph/distributed/mpi_process_group.hpp>
  86   #include <boost/graph/compressed_sparse_row_graph.hpp>
  87   #include <boost/graph/rmat_graph_generator.hpp>
  88   #include <boost/random/linear_congruential.hpp>
  89
  90   using boost::graph::distributed::mpi_process_group;
  91
  92   typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
  93                                       distributedS<mpi_process_group> > Graph;
  94   typedef keep_local_edges<boost::parallel::variant_distribution<mpi_process_group>,
  95                            mpi_process_group::process_id_type> EdgeFilter;
  96   typedef boost::sorted_unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen;
  97
  98   int main()
  99   {
 100     boost::minstd_rand gen;
 101     mpi_process_group pg;
 102
 103     int N = 100;
 104
 105     boost::parallel::variant_distribution<ProcessGroup> distrib
 106       = boost::parallel::block(pg, N);
 107
 108     mpi_process_group::process_id_type id = process_id(pg);
 109
 110     // Create graph with 100 nodes and 400 edges
 111     Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true,
 112                     true, EdgeFilter(distrib, id)),
 113             RMATGen(), N, pg, distrib);
 114     return 0;
 115   }
 116
 117
 118 Bibliography
 119 ------------
 120
 121 .. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
 122   Model for Graph Mining. In Proceedings of 4th International Conference
 123   on Data Mining, pages 442--446, 2004.
 124
 125 -----------------------------------------------------------------------------
 126
 127 Copyright (C) 2009 The Trustees of Indiana University.
 128
 129 Authors: Nick Edmonds and Andrew Lumsdaine
 130
 131 .. |Logo| image:: pbgl-logo.png
 132             :align: middle
 133             :alt: Parallel BGL
 134             :target: http://www.osl.iu.edu/research/pbgl
 135
 136 .. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html