123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Unique R-MAT generator</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-unique-r-mat-generator">
- <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> Unique R-MAT generator</h1>
- <!-- Copyright (C) 2004-2009 The Trustees of Indiana University.
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt) -->
- <pre class="literal-block">
- template<typename RandomGenerator, typename Graph>
- class unique_rmat_iterator
- {
- public:
- typedef std::input_iterator_tag iterator_category;
- typedef std::pair<vertices_size_type, vertices_size_type> value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
- unique_rmat_iterator();
- unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool permute_vertices = true);
- // Iterator operations
- reference operator*() const;
- pointer operator->() const;
- unique_rmat_iterator& operator++();
- unique_rmat_iterator operator++(int);
- bool operator==(const unique_rmat_iterator& other) const;
- bool operator!=(const unique_rmat_iterator& other) const;
- };
- </pre>
- <p>This class template implements a generator for R-MAT graphs <a class="citation-reference" href="#czf04" id="id1">[CZF04]</a>,
- suitable for initializing an adjacency_list or other graph structure
- with iterator-based initialization. An R-MAT graph has a scale-free
- distribution w.r.t. vertex degree and is implemented using
- Recursive-MATrix partitioning. The edge list produced by this iterator
- is guaranteed not to contain parallel edges.</p>
- <div class="section" id="where-defined">
- <h1>Where Defined</h1>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/rmat_graph_generator.hpp</span></tt>></p>
- </div>
- <div class="section" id="constructors">
- <h1>Constructors</h1>
- <pre class="literal-block">
- unique_rmat_iterator();
- </pre>
- <p>Constructs a past-the-end iterator.</p>
- <pre class="literal-block">
- unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool permute_vertices = true,
- EdgePredicate ep = keep_all_edges());
- </pre>
- <p>Constructs an R-MAT generator iterator that creates a graph with <tt class="docutils literal"><span class="pre">n</span></tt>
- 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
- the probability that a generated edge is placed of each of the 4
- quadrants of the partitioned adjacency matrix. Probabilities are
- drawn from the random number generator <tt class="docutils literal"><span class="pre">gen</span></tt>. Vertex indices are
- permuted to eliminate locality when <tt class="docutils literal"><span class="pre">permute_vertices</span></tt> is true.
- <tt class="docutils literal"><span class="pre">ep</span></tt> allows the user to specify which edges are retained, this is
- useful in the case where the user wishes to refrain from storing
- remote edges locally during generation to reduce memory consumption.</p>
- </div>
- <div class="section" id="example">
- <h1>Example</h1>
- <pre class="literal-block">
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/rmat_graph_generator.hpp>
- #include <boost/random/linear_congruential.hpp>
- typedef boost::adjacency_list<> Graph;
- typedef boost::unique_rmat_iterator<boost::minstd_rand, Graph> RMATGen;
- int main()
- {
- boost::minstd_rand gen;
- // Create graph with 100 nodes and 400 edges
- Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05,),
- RMATGen(), 100);
- return 0;
- }
- </pre>
- </div>
- <div class="section" id="bibliography">
- <h1>Bibliography</h1>
- <table class="docutils citation" frame="void" id="czf04" rules="none">
- <colgroup><col class="label" /><col /></colgroup>
- <tbody valign="top">
- <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
- Model for Graph Mining. In Proceedings of 4th International Conference
- on Data Mining, pages 442--446, 2004.</td></tr>
- </tbody>
- </table>
- <hr class="docutils" />
- <p>Copyright (C) 2009 The Trustees of Indiana University.</p>
- <p>Authors: Nick Edmonds and Andrew Lumsdaine</p>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:22 UTC.
- 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.
- </div>
- </body>
- </html>
|