ceph/src/boost/libs/graph/doc/erdos_renyi_generator.html

   1 <HTML>
   2 <!--
   3      Copyright (c) 2004, 2005 The Trustees of Indiana University
   4
   5      Use, modification and distribution is subject to the Boost Software
   6      License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8
   9       Authors: Douglas Gregor
  10                Jeremiah Willcock
  11                Andrew Lumsdaine
  12   -->
  13 <Head>
  14   <Title>Boost Graph Library: Erd&ouml;s-Renyi Generator</Title>
  15 <script language="JavaScript" type="text/JavaScript">
  16 <!--
  17 function address(host, user) {
  18         var atchar = '@';
  19         var thingy = user+atchar+host;
  20         thingy = '<a hre' + 'f=' + "mai" + "lto:" + thingy + '>' + user+atchar+host + '</a>';
  21         document.write(thingy);
  22 }
  23 //-->
  24 </script>
  25 </head>
  26
  27 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  28         ALINK="#ff0000">
  29 <IMG SRC="../../../boost.png"
  30      ALT="C++ Boost" width="277" height="86">
  31
  32 <tt>erdos_renyi_iterator</tt>
  33
  34 <br>
  35
  36 <PRE>
  37 template&lt;typename RandomGenerator, typename Graph&gt;
  38 class erdos_renyi_iterator
  39 {
  40 public:
  41   typedef std::input_iterator_tag iterator_category;
  42   typedef std::pair&lt;vertices_size_type, vertices_size_type&gt; value_type;
  43   typedef const value_type&amp; reference;
  44   typedef const value_type* pointer;
  45   typedef void difference_type;
  46
  47   erdos_renyi_iterator();
  48   erdos_renyi_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  49                        double fraction = 0.0, bool allow_self_loops = false);
  50   erdos_renyi_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  51                        edges_size_type m, bool allow_self_loops = false);
  52
  53   // Iterator operations
  54   reference operator*() const;
  55   pointer operator-&gt;() const;
  56   erdos_renyi_iterator&amp; operator++();
  57   erdos_renyi_iterator operator++(int);
  58   bool operator==(const erdos_renyi_iterator&amp; other) const;
  59   bool operator!=(const erdos_renyi_iterator&amp; other) const;
  60 };
  61 </PRE>
  62
  63 <p> This class template implements a generator for Erd&ouml;s-Renyi
  64 graphs, suitable for initializing an <a
  65 href="adjacency_list.html"><tt>adjacency_list</tt></a> or other graph
  66 structure with iterator-based initialization. An Erd&ouml;s-Renyi
  67 graph <em>G = (n, p)</em> is a graph with <em>n</em> vertices
  68 that. The probability of having an edge <em>(u, v)</em> in <em>G</em>
  69 is <em>p</em> for any vertices <em>u</em> and <em>v</em>. Typically,
  70 there are no self-loops, but the generator can optionally introduce
  71 self-loops with probability <em>p</em>. This generator will not
  72 produce any parallel edges and will produce edges in sorted order (as
  73 required by, e.g., the <a
  74 href="compressed_sparse_row.html"><tt>compressed_sparse_row_graph</tt></a>).</p>
  75
  76 <p>Erd&ouml;s-Renyi graphs typically exhibit very little
  77 structure. For this reason, they are rarely useful in modeling
  78 real-world problems. However, they are often used when determining
  79 the theoretical complexity of complex graph algorithms.</p>
  80
  81 <p>If you want the possibility of generating parallel edges and don't
  82 care about sorted order, use the <a
  83 href="erdos_renyi_generator.html"><tt>erdos_renyi_iterator</tt></a>.</p>
  84
  85 <h3>Where Defined</h3>
  86
  87 <a href="../../../boost/graph/erdos_renyi_generator.hpp"><tt>boost/graph/erdos_renyi_generator.hpp</tt></a>
  88
  89 <h3>Constructors</h3>
  90
  91 <a name="default-constructor"/>
  92 <pre>erdos_renyi_iterator();</pre>
  93 <blockquote>
  94 Constructs a past-the-end iterator.
  95 </blockquote>
  96
  97 <pre>
  98 erdos_renyi_iterator(RandomGenerator&amp; gen, vertices_size_type n,
  99                      double fraction = 0.0, bool allow_self_loops = false);
 100 </pre>
 101 <blockquote>
 102 Constructs an Erd&ouml;s-Renyi generator iterator that creates a
 103 graph with <tt>n</tt> vertices and a given <tt>fraction</tt> of the
 104 total number of edges that a simple graph may have.
 105 <tt>probability</tt>. Random vertices and edges are selected using the
 106 random number generator <tt>gen</tt>. Self-loops are permitted only when
 107 <tt>allow_self_loops</tt> is <tt>true</tt>.
 108 </blockquote>
 109
 110 <pre>
 111 erdos_renyi_iterator(RandomGenerator&amp; gen, vertices_size_type n,
 112                      edges_size_type m, bool allow_self_loops = false);
 113 </pre>
 114 <blockquote>
 115 Constructs an Erd&ouml;s-Renyi generator iterator that creates a
 116 graph with <tt>n</tt> vertices and <tt>m</tt> edges.
 117 <tt>probability</tt>. Random vertices and edges are selected using the
 118 random number generator <tt>gen</tt>. Self-loops are permitted only when
 119 <tt>allow_self_loops</tt> is <tt>true</tt>.
 120 </blockquote>
 121
 122 <H3>Example</H3>
 123
 124 <pre>
 125 #include &lt;boost/graph/adjacency_list.hpp&gt;
 126 #include &lt;boost/graph/erdos_renyi_generator.hpp&gt;
 127 #include &lt;boost/random/linear_congruential.hpp&gt;
 128
 129 typedef boost::adjacency_list&lt;&gt; Graph;
 130 typedef boost::erdos_renyi_iterator&lt;boost::minstd_rand, Graph&gt; ERGen;
 131
 132 int main()
 133 {
 134   boost::minstd_rand gen;
 135   // Create graph with 100 nodes and edges with probability 0.05
 136   Graph g(ERGen(gen, 100, 0.05), ERGen(), 100);
 137   return 0;
 138 }
 139 </pre>
 140
 141 <br>
 142 <HR>
 143 <TABLE>
 144 <TR valign=top>
 145 <TD nowrap>Copyright &copy; 2005</TD><TD>
 146 <A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University (<script language="Javascript">address("cs.indiana.edu", "dgregor")</script>)<br>
 147   <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 148 Indiana University (<script language="Javascript">address("osl.iu.edu", "lums")</script>)
 149 </TD></TR></TABLE>
 150
 151 </BODY>
 152 </HTML>