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">
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 Scalable R-MAT generator
</title>
8 <link rel=
"stylesheet" href=
"../../../../rst.css" type=
"text/css" />
11 <div class=
"document" id=
"logo-scalable-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> Scalable R-MAT generator
</h1>
14 <!-- Copyright (C) 2004-2009 The Trustees of Indiana University.
15 Use, modification and distribution is subject to the Boost Software
16 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
17 http://www.boost.org/LICENSE_1_0.txt) -->
18 <pre class=
"literal-block">
19 template
<typename ProcessGroup, typename Distribution,
20 typename RandomGenerator, typename Graph
>
21 class scalable_rmat_iterator
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;
30 scalable_rmat_iterator();
31 scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
32 RandomGenerator
& gen, vertices_size_type n,
33 edges_size_type m, double a, double b, double c,
34 double d, bool permute_vertices = true);
36 // Iterator operations
37 reference operator*() const;
38 pointer operator-
>() const;
39 scalable_rmat_iterator
& operator++();
40 scalable_rmat_iterator operator++(int);
41 bool operator==(const scalable_rmat_iterator
& other) const;
42 bool operator!=(const scalable_rmat_iterator
& other) const;
45 <p>This class template implements a generator for R-MAT graphs
<a class=
"citation-reference" href=
"#czf04" id=
"id1">[CZF04]
</a>,
46 suitable for initializing an adjacency_list or other graph structure
47 with iterator-based initialization. An R-MAT graph has a scale-free
48 distribution w.r.t. vertex degree and is implemented using
49 Recursive-MATrix partitioning.
</p>
50 <div class=
"section" id=
"where-defined">
51 <h1>Where Defined
</h1>
52 <p><<tt class=
"docutils literal"><span class=
"pre">boost/graph/rmat_graph_generator.hpp
</span></tt>></p>
54 <div class=
"section" id=
"constructors">
56 <pre class=
"literal-block">
57 scalable_rmat_iterator();
59 <p>Constructs a past-the-end iterator.
</p>
60 <pre class=
"literal-block">
61 scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
62 RandomGenerator
& gen, vertices_size_type n,
63 edges_size_type m, double a, double b, double c,
64 double d, bool permute_vertices = true);
66 <p>Constructs an R-MAT generator iterator that creates a graph with
<tt class=
"docutils literal"><span class=
"pre">n
</span></tt>
67 vertices and
<tt class=
"docutils literal"><span class=
"pre">m
</span></tt> edges. Inside the
<tt class=
"docutils literal"><span class=
"pre">scalable_rmat_iterator
</span></tt>
68 processes communicate using
<tt class=
"docutils literal"><span class=
"pre">pg
</span></tt> to generate their local edges as
69 defined by
<tt class=
"docutils literal"><span class=
"pre">distrib
</span></tt>.
<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 the
70 probability that a generated edge is placed of each of the
4 quadrants
71 of the partitioned adjacency matrix. Probabilities are drawn from the
72 random number generator
<tt class=
"docutils literal"><span class=
"pre">gen
</span></tt>. Vertex indices are permuted to
73 eliminate locality when
<tt class=
"docutils literal"><span class=
"pre">permute_vertices
</span></tt> is true.
</p>
75 <div class=
"section" id=
"example">
77 <pre class=
"literal-block">
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
>
83 using boost::graph::distributed::mpi_process_group;
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;
91 boost::minstd_rand gen;
96 boost::parallel::variant_distribution
<ProcessGroup
> distrib
97 = boost::parallel::block(pg, N);
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);
106 <div class=
"section" id=
"bibliography">
107 <h1>Bibliography
</h1>
108 <table class=
"docutils citation" frame=
"void" id=
"czf04" rules=
"none">
109 <colgroup><col class=
"label" /><col /></colgroup>
111 <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
112 Model for Graph Mining. In Proceedings of
4th International Conference
113 on Data Mining, pages
442--
446,
2004.
</td></tr>
116 <hr class=
"docutils" />
117 <p>Copyright (C)
2009 The Trustees of Indiana University.
</p>
118 <p>Authors: Nick Edmonds, Brian Barrett, and Andrew Lumsdaine
</p>
122 <hr class=
"footer" />
123 Generated on:
2009-
05-
31 00:
21 UTC.
124 Generated 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.