ceph/src/boost/libs/graph_parallel/doc/sorted_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 R-MAT generator
   8 ===================================
   9
  10 ::
  11
  12   template<typename RandomGenerator, typename Graph,
  13            typename EdgePredicate = keep_all_edges>
  14   class sorted_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_rmat_iterator();
  24     sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
  25                          edges_size_type m, double a, double b, double c,
  26                          double d, bool permute_vertices = true);
  27     // Iterator operations
  28     reference operator*() const;
  29     pointer operator->() const;
  30     sorted_rmat_iterator& operator++();
  31     sorted_rmat_iterator operator++(int);
  32     bool operator==(const sorted_rmat_iterator& other) const;
  33     bool operator!=(const sorted_rmat_iterator& other) const;
  34  };
  35
  36 This class template implements a generator for R-MAT graphs [CZF04]_,
  37 suitable for initializing an adjacency_list or other graph structure
  38 with iterator-based initialization. An R-MAT graph has a scale-free
  39 distribution w.r.t. vertex degree and is implemented using
  40 Recursive-MATrix partitioning.  The output of this generator is sorted
  41 for use with `compressed sparse row graph`_.
  42
  43 Where Defined
  44 -------------
  45 <``boost/graph/rmat_graph_generator.hpp``>
  46
  47 Constructors
  48 ------------
  49
  50 ::
  51
  52   sorted_rmat_iterator();
  53
  54 Constructs a past-the-end iterator.
  55
  56 ::
  57
  58
  59   sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
  60                        edges_size_type m, double a, double b, double c,
  61                        double d, bool permute_vertices = true,
  62                        EdgePredicate ep = keep_all_edges());
  63
  64 Constructs an R-MAT generator iterator that creates a graph with ``n``
  65 vertices and ``m`` edges.  ``a``, ``b``, ``c``, and ``d`` represent
  66 the probability that a generated edge is placed of each of the 4
  67 quadrants of the partitioned adjacency matrix.  Probabilities are
  68 drawn from the random number generator ``gen``.  Vertex indices are
  69 permuted to eliminate locality when ``permute_vertices`` is true.
  70 ``ep`` allows the user to specify which edges are retained, this is
  71 useful in the case where the user wishes to refrain from storing
  72 remote edges locally during generation to reduce memory consumption.
  73
  74 Example
  75 -------
  76
  77 ::
  78
  79   #include <boost/graph/compressed_sparse_row_graph.hpp>
  80   #include <boost/graph/rmat_graph_generator.hpp>
  81   #include <boost/random/linear_congruential.hpp>
  82
  83   typedef boost::compressed_sparse_row_graph<> Graph;
  84   typedef boost::sorted_rmat_iterator<boost::minstd_rand, Graph>
  85     RMATGen;
  86
  87   int main()
  88   {
  89     boost::minstd_rand gen;
  90     // Create graph with 100 nodes and 400 edges
  91     Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05),
  92             RMATGen(), 100);
  93     return 0;
  94   }
  95
  96 Bibliography
  97 ------------
  98
  99 .. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
 100   Model for Graph Mining. In Proceedings of 4th International Conference
 101   on Data Mining, pages 442--446, 2004.
 102
 103 -----------------------------------------------------------------------------
 104
 105 Copyright (C) 2009 The Trustees of Indiana University.
 106
 107 Authors: Nick Edmonds and Andrew Lumsdaine
 108
 109 .. |Logo| image:: pbgl-logo.png
 110             :align: middle
 111             :alt: Parallel BGL
 112             :target: http://www.osl.iu.edu/research/pbgl
 113
 114 .. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html