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 R-MAT generator
</title>
8 <link rel=
"stylesheet" href=
"../../../../rst.css" type=
"text/css" />
11 <div class=
"document" id=
"logo-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> 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 RandomGenerator, typename Graph
>
23 typedef std::input_iterator_tag iterator_category;
24 typedef std::pair
<vertices_size_type, vertices_size_type
> value_type;
25 typedef const value_type
& reference;
26 typedef const value_type* pointer;
27 typedef void difference_type;
30 rmat_iterator(RandomGenerator
& gen, vertices_size_type n,
31 edges_size_type m, double a, double b, double c,
32 double d, bool permute_vertices = true);
33 // Iterator operations
34 reference operator*() const;
35 pointer operator-
>() const;
36 rmat_iterator
& operator++();
37 rmat_iterator operator++(int);
38 bool operator==(const rmat_iterator
& other) const;
39 bool operator!=(const rmat_iterator
& other) const;
42 <p>This class template implements a generator for R-MAT graphs
<a class=
"citation-reference" href=
"#czf04" id=
"id1">[CZF04]
</a>,
43 suitable for initializing an adjacency_list or other graph structure
44 with iterator-based initialization. An R-MAT graph has a scale-free
45 distribution w.r.t. vertex degree and is implemented using
46 Recursive-MATrix partitioning.
</p>
47 <div class=
"section" id=
"where-defined">
48 <h1>Where Defined
</h1>
49 <p><<tt class=
"docutils literal"><span class=
"pre">boost/graph/rmat_graph_generator.hpp
</span></tt>></p>
51 <div class=
"section" id=
"constructors">
53 <pre class=
"literal-block">
56 <p>Constructs a past-the-end iterator.
</p>
57 <pre class=
"literal-block">
58 rmat_iterator(RandomGenerator
& gen, vertices_size_type n,
59 edges_size_type m, double a, double b, double c,
60 double d, bool permute_vertices = true);
62 <p>Constructs an R-MAT generator iterator that creates a graph with
<tt class=
"docutils literal"><span class=
"pre">n
</span></tt>
63 vertices 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
64 the probability that a generated edge is placed of each of the
4
65 quadrants of the partitioned adjacency matrix. Probabilities are
66 drawn from the random number generator gen. Vertex indices are
67 permuted to eliminate locality when
<tt class=
"docutils literal"><span class=
"pre">permute_vertices
</span></tt> is true.
</p>
69 <div class=
"section" id=
"example">
71 <pre class=
"literal-block">
72 #include
<boost/graph/adjacency_list.hpp
>
73 #include
<boost/graph/rmat_graph_generator.hpp
>
74 #include
<boost/random/linear_congruential.hpp
>
76 typedef boost::adjacency_list
<> Graph;
77 typedef boost::rmat_iterator
<boost::minstd_rand, Graph
> RMATGen;
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);
88 <div class=
"section" id=
"bibliography">
90 <table class=
"docutils citation" frame=
"void" id=
"czf04" rules=
"none">
91 <colgroup><col class=
"label" /><col /></colgroup>
93 <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
94 Model for Graph Mining. In Proceedings of
4th International Conference
95 on Data Mining, pages
442--
446,
2004.
</td></tr>
98 <hr class=
"docutils" />
99 <p>Copyright (C)
2009 The Trustees of Indiana University.
</p>
100 <p>Authors: Nick Edmonds and Andrew Lumsdaine
</p>
104 <hr class=
"footer" />
105 Generated on:
2009-
05-
31 00:
21 UTC.
106 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.