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| Unique R-MAT generator 8=================================== 9 10:: 11 12 template<typename RandomGenerator, typename Graph> 13 class unique_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 unique_rmat_iterator(); 23 unique_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 unique_rmat_iterator& operator++(); 30 unique_rmat_iterator operator++(int); 31 bool operator==(const unique_rmat_iterator& other) const; 32 bool operator!=(const unique_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. The edge list produced by this iterator 40is guaranteed not to contain parallel edges. 41 42Where Defined 43------------- 44<``boost/graph/rmat_graph_generator.hpp``> 45 46Constructors 47------------ 48 49:: 50 51 unique_rmat_iterator(); 52 53Constructs a past-the-end iterator. 54 55:: 56 57 unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 58 edges_size_type m, double a, double b, double c, 59 double d, bool permute_vertices = true, 60 EdgePredicate ep = keep_all_edges()); 61 62Constructs an R-MAT generator iterator that creates a graph with ``n`` 63vertices and ``m`` edges. ``a``, ``b``, ``c``, and ``d`` represent 64the probability that a generated edge is placed of each of the 4 65quadrants of the partitioned adjacency matrix. Probabilities are 66drawn from the random number generator ``gen``. Vertex indices are 67permuted to eliminate locality when ``permute_vertices`` is true. 68``ep`` allows the user to specify which edges are retained, this is 69useful in the case where the user wishes to refrain from storing 70remote edges locally during generation to reduce memory consumption. 71 72Example 73------- 74 75:: 76 77 #include <boost/graph/adjacency_list.hpp> 78 #include <boost/graph/rmat_graph_generator.hpp> 79 #include <boost/random/linear_congruential.hpp> 80 81 typedef boost::adjacency_list<> Graph; 82 typedef boost::unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen; 83 84 int main() 85 { 86 boost::minstd_rand gen; 87 // Create graph with 100 nodes and 400 edges 88 Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05,), 89 RMATGen(), 100); 90 return 0; 91 } 92 93 94Bibliography 95------------ 96 97.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos. R-MAT: A Recursive 98 Model for Graph Mining. In Proceedings of 4th International Conference 99 on Data Mining, pages 442--446, 2004. 100 101----------------------------------------------------------------------------- 102 103Copyright (C) 2009 The Trustees of Indiana University. 104 105Authors: Nick Edmonds and Andrew Lumsdaine 106 107.. |Logo| image:: pbgl-logo.png 108 :align: middle 109 :alt: Parallel BGL 110 :target: http://www.osl.iu.edu/research/pbgl 111
