ceph/src/boost/libs/graph_parallel/doc/html/unique_rmat_generator.html

   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 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-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> Unique R-MAT generator</h1>
  13
  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&lt;typename RandomGenerator, typename Graph&gt;
  20  class unique_rmat_iterator
  21  {
  22  public:
  23    typedef std::input_iterator_tag iterator_category;
  24    typedef std::pair&lt;vertices_size_type, vertices_size_type&gt; value_type;
  25    typedef const value_type&amp; reference;
  26    typedef const value_type* pointer;
  27    typedef void difference_type;
  28
  29    unique_rmat_iterator();
  30    unique_rmat_iterator(RandomGenerator&amp; 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-&gt;() const;
  36    unique_rmat_iterator&amp; operator++();
  37    unique_rmat_iterator operator++(int);
  38    bool operator==(const unique_rmat_iterator&amp; other) const;
  39    bool operator!=(const unique_rmat_iterator&amp; other) const;
  40 };
  41 </pre>
  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.  The edge list produced by this iterator
  47 is guaranteed not to contain parallel edges.</p>
  48 <div class="section" id="where-defined">
  49 <h1>Where Defined</h1>
  50 <p>&lt;<tt class="docutils literal"><span class="pre">boost/graph/rmat_graph_generator.hpp</span></tt>&gt;</p>
  51 </div>
  52 <div class="section" id="constructors">
  53 <h1>Constructors</h1>
  54 <pre class="literal-block">
  55 unique_rmat_iterator();
  56 </pre>
  57 <p>Constructs a past-the-end iterator.</p>
  58 <pre class="literal-block">
  59 unique_rmat_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  60                      edges_size_type m, double a, double b, double c,
  61                      double d, bool permute_vertices = true,
  62                      EdgePredicate ep = keep_all_edges());
  63 </pre>
  64 <p>Constructs an R-MAT generator iterator that creates a graph with <tt class="docutils literal"><span class="pre">n</span></tt>
  65 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
  66 the probability that a generated edge is placed of each of the 4
  67 quadrants of the partitioned adjacency matrix.  Probabilities are
  68 drawn from the random number generator <tt class="docutils literal"><span class="pre">gen</span></tt>.  Vertex indices are
  69 permuted to eliminate locality when <tt class="docutils literal"><span class="pre">permute_vertices</span></tt> is true.
  70 <tt class="docutils literal"><span class="pre">ep</span></tt> allows the user to specify which edges are retained, this is
  71 useful in the case where the user wishes to refrain from storing
  72 remote edges locally during generation to reduce memory consumption.</p>
  73 </div>
  74 <div class="section" id="example">
  75 <h1>Example</h1>
  76 <pre class="literal-block">
  77 #include &lt;boost/graph/adjacency_list.hpp&gt;
  78 #include &lt;boost/graph/rmat_graph_generator.hpp&gt;
  79 #include &lt;boost/random/linear_congruential.hpp&gt;
  80
  81 typedef boost::adjacency_list&lt;&gt; Graph;
  82 typedef boost::unique_rmat_iterator&lt;boost::minstd_rand, Graph&gt; RMATGen;
  83
  84 int main()
  85 {
  86   boost::minstd_rand gen;
  87   // Create graph with 100 nodes and 400 edges
  88   Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05,),
  89           RMATGen(), 100);
  90   return 0;
  91 }
  92 </pre>
  93 </div>
  94 <div class="section" id="bibliography">
  95 <h1>Bibliography</h1>
  96 <table class="docutils citation" frame="void" id="czf04" rules="none">
  97 <colgroup><col class="label" /><col /></colgroup>
  98 <tbody valign="top">
  99 <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
 100 Model for Graph Mining. In Proceedings of 4th International Conference
 101 on Data Mining, pages 442--446, 2004.</td></tr>
 102 </tbody>
 103 </table>
 104 <hr class="docutils" />
 105 <p>Copyright (C) 2009 The Trustees of Indiana University.</p>
 106 <p>Authors: Nick Edmonds and Andrew Lumsdaine</p>
 107 </div>
 108 </div>
 109 <div class="footer">
 110 <hr class="footer" />
 111 Generated on: 2009-05-31 00:22 UTC.
 112 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.
 113
 114 </div>
 115 </body>
 116 </html>