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