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| Scalable R-MAT generator 8=================================== 9 10:: 11 12 template<typename ProcessGroup, typename Distribution, 13 typename RandomGenerator, typename Graph> 14 class scalable_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 scalable_rmat_iterator(); 24 scalable_rmat_iterator(ProcessGroup pg, Distribution distrib, 25 RandomGenerator& gen, vertices_size_type n, 26 edges_size_type m, double a, double b, double c, 27 double d, bool permute_vertices = true); 28 29 // Iterator operations 30 reference operator*() const; 31 pointer operator->() const; 32 scalable_rmat_iterator& operator++(); 33 scalable_rmat_iterator operator++(int); 34 bool operator==(const scalable_rmat_iterator& other) const; 35 bool operator!=(const scalable_rmat_iterator& other) const; 36 }; 37 38This class template implements a generator for R-MAT graphs [CZF04]_, 39suitable for initializing an adjacency_list or other graph structure 40with iterator-based initialization. An R-MAT graph has a scale-free 41distribution w.r.t. vertex degree and is implemented using 42Recursive-MATrix partitioning. 43 44Where Defined 45------------- 46<``boost/graph/rmat_graph_generator.hpp``> 47 48Constructors 49------------ 50 51:: 52 53 scalable_rmat_iterator(); 54 55Constructs a past-the-end iterator. 56 57:: 58 59 scalable_rmat_iterator(ProcessGroup pg, Distribution distrib, 60 RandomGenerator& gen, vertices_size_type n, 61 edges_size_type m, double a, double b, double c, 62 double d, bool permute_vertices = true); 63 64Constructs an R-MAT generator iterator that creates a graph with ``n`` 65vertices and ``m`` edges. Inside the ``scalable_rmat_iterator`` 66processes communicate using ``pg`` to generate their local edges as 67defined by ``distrib``. ``a``, ``b``, ``c``, and ``d`` represent the 68probability that a generated edge is placed of each of the 4 quadrants 69of the partitioned adjacency matrix. Probabilities are drawn from the 70random number generator ``gen``. Vertex indices are permuted to 71eliminate locality when ``permute_vertices`` is true. 72 73Example 74------- 75 76:: 77 78 #include <boost/graph/distributed/mpi_process_group.hpp> 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 using boost::graph::distributed::mpi_process_group; 84 85 typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, 86 distributedS<mpi_process_group> > Graph; 87 typedef boost::scalable_rmat_iterator<boost::minstd_rand, Graph> RMATGen; 88 89 int main() 90 { 91 boost::minstd_rand gen; 92 mpi_process_group pg; 93 94 int N = 100; 95 96 boost::parallel::variant_distribution<ProcessGroup> distrib 97 = boost::parallel::block(pg, N); 98 99 // Create graph with 100 nodes and 400 edges 100 Graph g(RMATGen(pg, distrib, gen, N, 400, 0.57, 0.19, 0.19, 0.05), 101 RMATGen(), N, pg, distrib); 102 return 0; 103 } 104 105Bibliography 106------------ 107 108.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos. R-MAT: A Recursive 109 Model for Graph Mining. In Proceedings of 4th International Conference 110 on Data Mining, pages 442--446, 2004. 111 112----------------------------------------------------------------------------- 113 114Copyright (C) 2009 The Trustees of Indiana University. 115 116Authors: Nick Edmonds, Brian Barrett, and Andrew Lumsdaine 117 118.. |Logo| image:: pbgl-logo.png 119 :align: middle 120 :alt: Parallel BGL 121 :target: http://www.osl.iu.edu/research/pbgl 122 123.. _Sequential connected components: http://www.boost.org/libs/graph/doc/connected_components.html 124
