1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Sorted R-MAT generator</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-sorted-r-mat-generator"> 12<h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Sorted R-MAT generator</h1> 13 14<!-- Copyright (C) 2004-2009 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19 template<typename RandomGenerator, typename Graph, 20 typename EdgePredicate = keep_all_edges> 21 class sorted_rmat_iterator 22 { 23 public: 24 typedef std::input_iterator_tag iterator_category; 25 typedef std::pair<vertices_size_type, vertices_size_type> value_type; 26 typedef const value_type& reference; 27 typedef const value_type* pointer; 28 typedef void difference_type; 29 30 sorted_rmat_iterator(); 31 sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 32 edges_size_type m, double a, double b, double c, 33 double d, bool permute_vertices = true); 34 // Iterator operations 35 reference operator*() const; 36 pointer operator->() const; 37 sorted_rmat_iterator& operator++(); 38 sorted_rmat_iterator operator++(int); 39 bool operator==(const sorted_rmat_iterator& other) const; 40 bool operator!=(const sorted_rmat_iterator& other) const; 41}; 42</pre> 43<p>This class template implements a generator for R-MAT graphs <a class="citation-reference" href="#czf04" id="id1">[CZF04]</a>, 44suitable for initializing an adjacency_list or other graph structure 45with iterator-based initialization. An R-MAT graph has a scale-free 46distribution w.r.t. vertex degree and is implemented using 47Recursive-MATrix partitioning. The output of this generator is sorted 48for use with <a class="reference external" href="http://www.boost.org/libs/graph/doc/compressed_sparse_row.html">compressed sparse row graph</a>.</p> 49<div class="section" id="where-defined"> 50<h1>Where Defined</h1> 51<p><<tt class="docutils literal"><span class="pre">boost/graph/rmat_graph_generator.hpp</span></tt>></p> 52</div> 53<div class="section" id="constructors"> 54<h1>Constructors</h1> 55<pre class="literal-block"> 56sorted_rmat_iterator(); 57</pre> 58<p>Constructs a past-the-end iterator.</p> 59<pre class="literal-block"> 60sorted_rmat_iterator(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 EdgePredicate ep = keep_all_edges()); 64</pre> 65<p>Constructs an R-MAT generator iterator that creates a graph with <tt class="docutils literal"><span class="pre">n</span></tt> 66vertices and <tt class="docutils literal"><span class="pre">m</span></tt> edges. <tt class="docutils literal"><span class="pre">a</span></tt>, <tt class="docutils literal"><span class="pre">b</span></tt>, <tt class="docutils literal"><span class="pre">c</span></tt>, and <tt class="docutils literal"><span class="pre">d</span></tt> represent 67the probability that a generated edge is placed of each of the 4 68quadrants of the partitioned adjacency matrix. Probabilities are 69drawn from the random number generator <tt class="docutils literal"><span class="pre">gen</span></tt>. Vertex indices are 70permuted to eliminate locality when <tt class="docutils literal"><span class="pre">permute_vertices</span></tt> is true. 71<tt class="docutils literal"><span class="pre">ep</span></tt> allows the user to specify which edges are retained, this is 72useful in the case where the user wishes to refrain from storing 73remote edges locally during generation to reduce memory consumption.</p> 74</div> 75<div class="section" id="example"> 76<h1>Example</h1> 77<pre class="literal-block"> 78#include <boost/graph/compressed_sparse_row_graph.hpp> 79#include <boost/graph/rmat_graph_generator.hpp> 80#include <boost/random/linear_congruential.hpp> 81 82typedef boost::compressed_sparse_row_graph<> Graph; 83typedef boost::sorted_rmat_iterator<boost::minstd_rand, Graph> 84 RMATGen; 85 86int main() 87{ 88 boost::minstd_rand gen; 89 // Create graph with 100 nodes and 400 edges 90 Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05), 91 RMATGen(), 100); 92 return 0; 93} 94</pre> 95</div> 96<div class="section" id="bibliography"> 97<h1>Bibliography</h1> 98<table class="docutils citation" frame="void" id="czf04" rules="none"> 99<colgroup><col class="label" /><col /></colgroup> 100<tbody valign="top"> 101<tr><td class="label"><a class="fn-backref" href="#id1">[CZF04]</a></td><td>D Chakrabarti, Y Zhan, and C Faloutsos. R-MAT: A Recursive 102Model for Graph Mining. In Proceedings of 4th International Conference 103on Data Mining, pages 442--446, 2004.</td></tr> 104</tbody> 105</table> 106<hr class="docutils" /> 107<p>Copyright (C) 2009 The Trustees of Indiana University.</p> 108<p>Authors: Nick Edmonds and Andrew Lumsdaine</p> 109</div> 110</div> 111<div class="footer"> 112<hr class="footer" /> 113Generated on: 2009-05-31 00:21 UTC. 114Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. 115 116</div> 117</body> 118</html> 119
