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 unique 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-unique-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 unique 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_unique_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_unique_rmat_iterator(); 31 sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 32 edges_size_type m, double a, double b, double c, 33 double d, bool bidirectional = true, 34 bool permute_vertices = true, 35 EdgePredicate ep = keep_all_edges()); 36 // Iterator operations 37 reference operator*() const; 38 pointer operator->() const; 39 sorted_unique_rmat_iterator& operator++(); 40 sorted_unique_rmat_iterator operator++(int); 41 bool operator==(const sorted_unique_rmat_iterator& other) const; 42 bool operator!=(const sorted_unique_rmat_iterator& other) const; 43}; 44</pre> 45<p>This class template implements a generator for R-MAT graphs <a class="citation-reference" href="#czf04" id="id1">[CZF04]</a>, 46suitable for initializing an adjacency_list or other graph structure 47with iterator-based initialization. An R-MAT graph has a scale-free 48distribution w.r.t. vertex degree and is implemented using 49Recursive-MATrix partitioning. The output of this generator is sorted 50for use with a <a class="reference external" href="http://www.boost.org/libs/graph/doc/compressed_sparse_row.html">compressed sparse row graph</a>. The edge list produced by 51this iterator is guaranteed not to contain parallel edges.</p> 52<div class="section" id="where-defined"> 53<h1>Where Defined</h1> 54<p><<tt class="docutils literal"><span class="pre">boost/graph/rmat_graph_generator.hpp</span></tt>></p> 55</div> 56<div class="section" id="constructors"> 57<h1>Constructors</h1> 58<pre class="literal-block"> 59sorted_unique_rmat_iterator(); 60</pre> 61<p>Constructs a past-the-end iterator.</p> 62<pre class="literal-block"> 63sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 64 edges_size_type m, double a, double b, double c, 65 double d, bool bidirectional = false, 66 bool permute_vertices = true, 67 EdgePredicate ep = keep_all_edges()); 68</pre> 69<p>Constructs an R-MAT generator iterator that creates a graph with <tt class="docutils literal"><span class="pre">n</span></tt> 70vertices 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 71the probability that a generated edge is placed of each of the 4 72quadrants of the partitioned adjacency matrix. Probabilities are 73drawn from the random number generator <tt class="docutils literal"><span class="pre">gen</span></tt>. Vertex indices are 74permuted to eliminate locality when <tt class="docutils literal"><span class="pre">permute_vertices</span></tt> is true. 75When <tt class="docutils literal"><span class="pre">bidirectional</span></tt> is <tt class="docutils literal"><span class="pre">true</span></tt> for every edge s-t, the 76corresponding anti-edge t-s is added as well, these anti-edges are not 77counted towards <tt class="docutils literal"><span class="pre">m</span></tt>. <tt class="docutils literal"><span class="pre">ep</span></tt> allows the user to specify which edges 78are retained, this is useful in the case where the user wishes to 79refrain from storing remote edges locally during generation to reduce 80memory consumption.</p> 81</div> 82<div class="section" id="example"> 83<h1>Example</h1> 84<pre class="literal-block"> 85#include <boost/graph/distributed/mpi_process_group.hpp> 86#include <boost/graph/compressed_sparse_row_graph.hpp> 87#include <boost/graph/rmat_graph_generator.hpp> 88#include <boost/random/linear_congruential.hpp> 89 90using boost::graph::distributed::mpi_process_group; 91 92typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property, 93 distributedS<mpi_process_group> > Graph; 94typedef keep_local_edges<boost::parallel::variant_distribution<mpi_process_group>, 95 mpi_process_group::process_id_type> EdgeFilter; 96typedef boost::sorted_unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen; 97 98int main() 99{ 100 boost::minstd_rand gen; 101 mpi_process_group pg; 102 103 int N = 100; 104 105 boost::parallel::variant_distribution<ProcessGroup> distrib 106 = boost::parallel::block(pg, N); 107 108 mpi_process_group::process_id_type id = process_id(pg); 109 110 // Create graph with 100 nodes and 400 edges 111 Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true, 112 true, EdgeFilter(distrib, id)), 113 RMATGen(), N, pg, distrib); 114 return 0; 115} 116</pre> 117</div> 118<div class="section" id="bibliography"> 119<h1>Bibliography</h1> 120<table class="docutils citation" frame="void" id="czf04" rules="none"> 121<colgroup><col class="label" /><col /></colgroup> 122<tbody valign="top"> 123<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 124Model for Graph Mining. In Proceedings of 4th International Conference 125on Data Mining, pages 442--446, 2004.</td></tr> 126</tbody> 127</table> 128<hr class="docutils" /> 129<p>Copyright (C) 2009 The Trustees of Indiana University.</p> 130<p>Authors: Nick Edmonds and Andrew Lumsdaine</p> 131</div> 132</div> 133<div class="footer"> 134<hr class="footer" /> 135Generated on: 2009-05-31 00:21 UTC. 136Generated 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. 137 138</div> 139</body> 140</html> 141
