[Boost-commit] svn:boost r63557 - in trunk: boost/graph libs/graph/doc libs/graph/test

Subject: [Boost-commit] svn:boost r63557 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2010-07-03 15:50:51

Author: jewillco
Date: 2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
New Revision: 63557
URL: http://svn.boost.org/trac/boost/changeset/63557

Log:
Changed random_spanning_tree to use named parameters; removed separate function name for weighted version; allowed user to specify spanning tree root; added exception for some cases of stuck loop-erased random walks; added documentation for random_spanning_tree()
Added:
   trunk/libs/graph/doc/random_spanning_tree.html
      - copied, changed from r63554, /trunk/libs/graph/doc/depth_first_search.html
Text files modified: 
   trunk/boost/graph/loop_erased_random_walk.hpp       |     9 +                                       
   trunk/boost/graph/random_spanning_tree.hpp          |    76 +++++----                               
   trunk/libs/graph/doc/bibliography.html              |     8                                         
   trunk/libs/graph/doc/random_spanning_tree.html      |   304 +++++++++------------------------------ 
   trunk/libs/graph/doc/table_of_contents.html         |     5                                         
   trunk/libs/graph/test/random_spanning_tree_test.cpp |     6                                         
   6 files changed, 139 insertions(+), 269 deletions(-)

Modified: trunk/boost/graph/loop_erased_random_walk.hpp
==============================================================================
--- trunk/boost/graph/loop_erased_random_walk.hpp	(original)
+++ trunk/boost/graph/loop_erased_random_walk.hpp	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -19,6 +19,13 @@
 
 namespace boost {
 
+  struct loop_erased_random_walk_stuck : public std::exception {
+    virtual ~loop_erased_random_walk_stuck() throw() {}
+    inline virtual const char* what() const throw() {
+      return "Loop-erased random walk found a vertex with no out-edges";
+    }
+  };
+
   // Do a loop-erased random walk from vertex s to any vertex colored black (or
   // actually any color other than white or gray) in the color map.  The color
   // white is for vertices that are not part of the path, while gray is for
@@ -86,6 +93,7 @@
 
     typename gt::edge_descriptor
     operator()(typename gt::vertex_descriptor src, const Graph& g) const {
+      if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck();
       return boost::random_out_edge(g, src, gen);
     }
   };
@@ -102,6 +110,7 @@
 
     typename gt::edge_descriptor
     operator()(typename gt::vertex_descriptor src, const Graph& g) const {
+      if (out_degree(src, g) == 0) throw loop_erased_random_walk_stuck();
       return boost::weighted_random_out_edge(g, src, weight, gen);
     }
   };

Modified: trunk/boost/graph/random_spanning_tree.hpp
==============================================================================
--- trunk/boost/graph/random_spanning_tree.hpp	(original)
+++ trunk/boost/graph/random_spanning_tree.hpp	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -15,6 +15,11 @@
 #include <boost/graph/random.hpp>
 #include <boost/graph/iteration_macros.hpp>
 #include <boost/property_map/property_map.hpp>
+#include <boost/config.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/named_function_params.hpp>
 
 namespace boost {
 
@@ -25,18 +30,17 @@
     // unweighted selection of trees.
     // Algorithm is from http://en.wikipedia.org/wiki/Uniform_spanning_tree
     template <typename Graph, typename PredMap, typename ColorMap, typename NextEdge>
-    void random_spanning_tree_internal(const Graph& g, PredMap pred, ColorMap color, NextEdge next_edge) {
+    void random_spanning_tree_internal(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, PredMap pred, ColorMap color, NextEdge next_edge) {
       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
       typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
-      assert (num_vertices(g) >= 2); // g must also be undirected (or symmetric) and connected
+      assert (num_vertices(g) >= 1); // g must also be undirected (or symmetric) and connected
 
       typedef color_traits<typename property_traits<ColorMap>::value_type> color_gen;
       BGL_FORALL_VERTICES_T(v, g, Graph) put(color, v, color_gen::white());
 
       std::vector<vertex_descriptor> path;
 
-      vertex_descriptor s = *vertices(g).first;
       put(color, s, color_gen::black());
       put(pred, s, graph_traits<Graph>::null_vertex());
 
@@ -55,46 +59,46 @@
     }
   }
 
-  // Compute a uniformly-distributed spanning tree on a graph.
-  template <typename Graph, typename PredMap, typename ColorMap, typename Gen>
-  void random_spanning_tree(const Graph& g, PredMap pred, Gen& gen, ColorMap color) {
+  // Compute a uniformly-distributed spanning tree on a graph.  Use Wilson's algorithm:
+  // @inproceedings{wilson96generating,
+  //    author = {Wilson, David Bruce},
+  //    title = {Generating random spanning trees more quickly than the cover time},
+  //    booktitle = {STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing},
+  //    year = {1996},
+  //    isbn = {0-89791-785-5},
+  //    pages = {296--303},
+  //    location = {Philadelphia, Pennsylvania, United States},
+  //    doi = {http://doi.acm.org/10.1145/237814.237880},
+  //    publisher = {ACM},
+  //    address = {New York, NY, USA},
+  //  }
+  //
+  template <typename Graph, typename Gen, typename PredMap, typename ColorMap>
+  void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root,
+                            PredMap pred, static_property_map<double>, ColorMap color) {
     unweighted_random_out_edge_gen<Graph, Gen> random_oe(gen);
-    detail::random_spanning_tree_internal(g, pred, color, random_oe);
-  }
-
-  // Compute a uniformly-distributed spanning tree on a graph.
-  template <typename Graph, typename PredMap, typename Gen>
-  void random_spanning_tree(const Graph& g, PredMap pred, Gen& gen) {
-    std::vector<default_color_type> color_data(num_vertices(g));
-    random_spanning_tree(g, pred, gen, make_iterator_property_map(color_data.begin(), get(vertex_index, g)));
+    detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
   }
 
   // Compute a weight-distributed spanning tree on a graph.
-  // Weighting works according to:
-  // @article{Mosbah1999263,
-  //   title = "Non-uniform random spanning trees on weighted graphs",
-  //   journal = "Theoretical Computer Science",
-  //   volume = "218",
-  //   number = "2",
-  //   pages = "263--271",
-  //   year = "1999",
-  //   note = "",
-  //   issn = "0304-3975",
-  //   doi = "DOI: 10.1016/S0304-3975(98)00325-9",
-  //   url = "http://www.sciencedirect.com/science/article/B6V1G-3WSV1D9-P/2/06bea092e23163c4884844cde4a5e92c",
-  //   author = "M. Mosbah and N. Saheb"
-  // }
-  template <typename Graph, typename PredMap, typename WeightMap, typename ColorMap, typename Gen>
-  void weighted_random_spanning_tree(const Graph& g, PredMap pred, WeightMap weight, Gen& gen, ColorMap color) {
+  template <typename Graph, typename Gen, typename PredMap, typename WeightMap, typename ColorMap>
+  void random_spanning_tree(const Graph& g, Gen& gen, typename graph_traits<Graph>::vertex_descriptor root,
+                            PredMap pred, WeightMap weight, ColorMap color) {
     weighted_random_out_edge_gen<Graph, WeightMap, Gen> random_oe(weight, gen);
-    detail::random_spanning_tree_internal(g, pred, color, random_oe);
+    detail::random_spanning_tree_internal(g, root, pred, color, random_oe);
   }
 
-  // Compute a weight-distributed spanning tree on a graph.
-  template <typename Graph, typename PredMap, typename WeightMap, typename Gen>
-  void weighted_random_spanning_tree(const Graph& g, PredMap pred, WeightMap weight, Gen& gen) {
-    std::vector<default_color_type> color_data(num_vertices(g));
-    weighted_random_spanning_tree(g, pred, weight, gen, make_iterator_property_map(color_data.begin(), get(vertex_index, g)));
+  template <typename Graph, typename Gen, typename P, typename T, typename R>
+  void random_spanning_tree(const Graph& g, Gen& gen, const bgl_named_params<P, T, R>& params) {
+    using namespace boost::graph::keywords;
+    typedef bgl_named_params<P, T, R> params_type;
+    BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
+    random_spanning_tree(g,
+                         gen,
+                         arg_pack[_root_vertex | *vertices(g).first],
+                         arg_pack[_predecessor_map],
+                         arg_pack[_weight_map | static_property_map<double>(1.)],
+                         boost::detail::color_map_maker<Graph, arg_pack_type>::make_map(g, arg_pack));
   }
 }
 

Modified: trunk/libs/graph/doc/bibliography.html
==============================================================================
--- trunk/libs/graph/doc/bibliography.html	(original)
+++ trunk/libs/graph/doc/bibliography.html	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -352,7 +352,7 @@
 <p></p><dt><a name="fruchterman91">58</a>
 <dd>T. Fruchterman and E. Reingold<br>
   <em>Graph drawing by force-directed placement.</em><br>
-Software--Practice & Experience, 21 (11), pp. 1129-1164, 1991.
+Software--Practice &amp; Experience, 21 (11), pp. 1129-1164, 1991.
 
 <p></p><dt><a name="coleman83">59</a>
 <dd>Thomas F. Coleman and Jorge J. More<br>
@@ -432,6 +432,12 @@
 </em><br>
 Combinatorica 10: 41-51, 1990.
 
+<P></P><DT><A NAME="wilson96generating">73</A>
+<DD>
+David&nbsp;Bruce&nbsp;Wilson
+<BR><em>Generating random spanning trees more quickly than the cover time</em>.
+ACM Symposium on the Theory of Computing, pp. 296-303, 1996.
+
 </dl>
   
 <br>

Copied: trunk/libs/graph/doc/random_spanning_tree.html (from r63554, /trunk/libs/graph/doc/depth_first_search.html)
==============================================================================
--- /trunk/libs/graph/doc/depth_first_search.html	(original)
+++ trunk/libs/graph/doc/random_spanning_tree.html	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -1,13 +1,17 @@
 <HTML>
 <!--
-     Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
-    
+     Copyright 2010 The Trustees of Indiana University.
+     
      Distributed under 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)
+     
+      Authors: Jeremiah Willcock
+               Jeremy Siek (due to adaptation from depth_first_search.html)
+               Andrew Lumsdaine
   -->
 <Head>
-<Title>Boost Graph Library: Depth-First Search</Title>
+<Title>Boost Graph Library: Random Spanning Tree</Title>
 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
         ALINK="#ff0000"> 
 <IMG SRC="../../../boost.png" 
@@ -15,173 +19,78 @@
 
 <BR Clear>
 
-<H1><A NAME="sec:depth-first-search"></A><img src="figs/python.gif" alt="(Python)"/>
-<TT>depth_first_search</TT>
+<TT>random_spanning_tree</TT>
 </H1>
 
 <P>
 <PRE>
 <i>// named parameter version</i>
-template &lt;class Graph, class class P, class T, class R&gt;
-void depth_first_search(Graph&amp; G,
+template &lt;class Graph, class Gen, class class P, class T, class R&gt;
+void random_spanning_tree(Graph&amp; G,
+  Gen&amp; gen,
   const bgl_named_params&lt;P, T, R&gt;&amp; params);
 
-<i>// non-named parameter version</i>
-template &lt;class Graph, class DFSVisitor, class ColorMap&gt;
-void depth_first_search(const Graph&amp; g, DFSVisitor vis, ColorMap color)
-
-template &lt;class Graph, class DFSVisitor, class ColorMap&gt;
-void depth_first_search(const Graph&amp; g, DFSVisitor vis, ColorMap color, 
-                        typename graph_traits&lt;Graph&gt;::vertex_descriptor start)
-
+<i>// non-named parameter versions</i>
+template &lt;class Graph, class Gen, class PredMap, class WeightMap, class ColorMap&gt;
+void random_spanning_tree(const Graph&amp; g, Gen&amp; gen, vertex_descriptor root,
+  PredMap pred, WeightMap weight, ColorMap color);
 </PRE>
 
 <p>
-The <tt>depth_first_search()</tt> function performs a depth-first
-traversal of the vertices in a directed graph.  When
-possible, a depth-first traversal chooses a vertex adjacent to the
-current vertex to visit next. If all adjacent vertices have already
-been discovered, or there are no adjacent vertices, then the algorithm
-backtracks to the last vertex that had undiscovered neighbors. Once
-all reachable vertices have been visited, the algorithm selects from
-any remaining undiscovered vertices and continues the traversal. The
-algorithm finishes when all vertices have been visited. Depth-first
-search is useful for categorizing edges in a graph, and for imposing
-an ordering on the vertices. Section <a
-href="./graph_theory_review.html#sec:dfs-algorithm">Depth-First
-Search</a> describes the various properties of DFS and walks through
-an example.
-</p>
-
-<p>
-Similar to BFS, color markers are used to keep track of which vertices
-have been discovered. White marks vertices that have yet to be
-discovered, gray marks a vertex that is discovered but still has
-vertices adjacent to it that are undiscovered. A black vertex is
-discovered vertex that is not adjacent to any white vertices.
-<p>
-
-<p>
-The <tt>depth_first_search()</tt> function invokes user-defined
-actions at certain event-points within the algorithm. This provides a
-mechanism for adapting the generic DFS algorithm to the many
-situations in which it can be used.  In the pseudo-code below, the
-event points for DFS are the labels on
-the right. The user-defined actions must be provided in the form of a
-visitor object, that is, an object whose type meets the requirements
-for a DFS Visitor. In the pseudo-code
-we show the algorithm computing predecessors <i>p</i>, discover time
-<i>d</i> and finish time <i>t</i>.  By default, the
-<tt>depth_first_search()</tt> function does not compute these
-properties, however there are pre-defined visitors such as <a
-href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
-and time_stamper that can
-be used to do this.
+The <tt>random_spanning_tree()</tt> function generates a random spanning tree
+on a directed or undirected graph.  The algorithm used is Wilson's algorithm (<a
+href="bibliography.html#wilson96generating">73</a>, based on <!-- (FIXME: add
+documentation for loop_erased_random_walk()) <a
+href="loop_erased_random_walk.html"> -->loop-erased random walks<!-- </a> -->.  There must
+be a path from every non-root vertex of the graph to the root;
+the algorithm typically enters an infinite loop when
+given a graph that does not satisfy this property, but may also throw the
+exception <tt>loop_erased_random_walk_stuck</tt> if the search reaches a vertex
+with no outgoing edges.  Both weighted and unweighted versions of
+<tt>random_spanning_tree()</tt> are
+implemented.  In the unweighted version, all spanning trees are equally likely.
+In the weighted version, the probability of a particular spanning tree being
+selected is the product of its edge weights.
+In the non-named-parameter
+version of the algorithm, the unweighted version can be selected by passing an
+object of type <tt>static_property_map&lt;double&gt;</tt> as the weight map.
+In the named-parameter version, leaving off the <tt>weight_map</tt> parameter
+has the same effect.
 </p>
 
-<table>
-<tr>
-<td valign="top">
-<pre>
-DFS(<i>G</i>)
-  <b>for</b> each vertex <i>u in V</i> 
-    <i>color[u] :=</i> WHITE
-    <i>p[u] = u</i> 
-  <b>end for</b>
-  <i>time := 0</i>
-  <b>if</b> there is a starting vertex <i>s</i>
-    <b>call</b> DFS-VISIT(<i>G</i>, <i>s</i>)
-  <b>for</b> each vertex <i>u in V</i> 
-    <b>if</b> <i>color[u] =</i> WHITE
-      <b>call</b> DFS-VISIT(<i>G</i>, <i>u</i>)
-  <b>end for</b>
-  return (<i>p</i>,<i>d_time</i>,<i>f_time</i>) <br>
-DFS-VISIT(<i>G</i>, <i>u</i>) 
-  <i>color[u] :=</i> GRAY
-  <i>d_time[u] := time := time + 1</i> 
-  <b>for</b> each <i>v in Adj[u]</i> 
-    <b>if</b> (<i>color[v] =</i> WHITE)
-      <i>p[v] = u</i> 
-      <b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
-    <b>else if</b> (<i>color[v] =</i> GRAY) 
-      <i>...</i>
-    <b>else if</b> (<i>color[v] =</i> BLACK) 
-      <i>...</i>
-  <b>end for</b>
-  <i>color[u] :=</i> BLACK
-  <i>f_time[u] := time := time + 1</i> 
-<pre>
-</td>
-<td valign="top">
-<pre>
--
--
-initialize vertex <i>u</i>
--
--
--
--
-start vertex <i>s</i>
--
--
-start vertex <i>u</i>
--
--
--
--
-discover vertex <i>u</i>
--
-examine edge <i>(u,v)</i>
--
-<i>(u,v)</i> is a tree edge
--
--
-<i>(u,v)</i> is a back edge
--
-<i>(u,v)</i> is a cross or forward edge
--
-finish vertex <i>u</i>
--
-</pre>
-</td>
-</tr>
-</table>
-
-
-
 <H3>Where Defined</H3>
 
 <P>
-boost/graph/depth_first_search.hpp
+boost/graph/random_spanning_tree.hpp
 
 <h3>Parameters</h3>
 
-IN: <tt>Graph&amp; g</tt>
+IN: <tt>const Graph&amp; g</tt>
 <blockquote>
-  A directed graph. The graph type must
+  An undirected graph. The graph type must
   be a model of Incidence Graph
   and Vertex List Graph.<br>
+</blockquote>
 
-  <b>Python</b>: The parameter is named <tt>graph</tt>.
+IN: <tt>Gen&amp; gen</tt>
+<blockquote>
+  A random number generator. The generator type must
+  be a model of <a
+  href="../../random/doc/reference.html#boost_random.reference.concepts.uniform_random_number_generator">Uniform
+  Random Number Generator</a> or a pointer or reference to such a type.<br>
 </blockquote>
 
 
 <h3>Named Parameters</h3>
 
-IN: <tt>visitor(DFSVisitor vis)</tt>
+IN: <tt>root_vertex(vertex_descriptor root)</tt>
 <blockquote>
-  A visitor object that is invoked inside the algorithm at the
-  event-points specified by the <a href="./DFSVisitor.html">DFS
-  Visitor</a> concept. The visitor object is passed by value <a
-  href="#1">[1]</a>. <br> <b>Default:</b>
-  <tt>dfs_visitor&lt;null_visitor&gt;</tt><br>
-
-  <b>Python</b>: The parameter should be an object that derives from
-  the DFSVisitor type of
-  the graph.
+  This parameter, whose type must be the vertex descriptor type of
+  <tt>Graph</tt>, gives the root of the tree to be generated.  The default is
+  <tt>*vertices(g).first</tt>.<br>
 </blockquote>
 
-UTIL/OUT: <tt>color_map(ColorMap color)</tt>
+UTIL: <tt>color_map(ColorMap color)</tt>
 <blockquote>
   This is used by the algorithm to keep track of its progress through
   the graph. The type <tt>ColorMap</tt> must be a model of <a
@@ -189,24 +98,9 @@
   Property Map</a> and its key type must be the graph's vertex
   descriptor type and the value type of the color map must model
   ColorValue.<br>
-  <b>Default:</b> an <a
-  href="../../property_map/doc/iterator_property_map.html">
-  </tt>iterator_property_map</tt></a> created from a
-  <tt>std::vector</tt> of <tt>default_color_type</tt> of size
+  <b>Default:</b> a <tt>two_bit_color_map</tt> of size
   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
   map.<br>
-
-   <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
-  the graph.
-</blockquote>
-
-IN: <tt>root_vertex(typename
-graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start)</tt>
-<blockquote>
-  This specifies the vertex that the depth-first search should
-  originate from. The type is the type of a vertex descriptor for the
-  given graph.<br>
-  <b>Default:</b> <tt>*vertices(g).first</tt><br>
 </blockquote>
 
 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
@@ -219,82 +113,34 @@
   Map</a>. The value type of the map must be an integer type. The
   vertex descriptor type of the graph needs to be usable as the key
   type of the map.<br>
-
-  <b>Default:</b> <tt>get(vertex_index, g)</tt>.
-    Note: if you use this default, make sure your graph has
-    an internal <tt>vertex_index</tt> property. For example,
-    <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
-    not have an internal <tt>vertex_index</tt> property.<br>
-
-  <b>Python</b>: Unsupported parameter.
 </blockquote>
 
-<P>
-
-<H3><A NAME="SECTION001340300000000000000">
-Complexity</A>
-</H3>
-
-<P>
-The time complexity is <i>O(E + V)</i>.
-
-<P>
-
-<h3>Visitor Event Points</h3>
-
-<ul>
-
-<li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
-  vertex of the graph before the start of the graph search.
-
-<li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
-  vertex once before the start of the search.
-  
-<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked when a vertex
-  is encountered for the first time.
-  
-<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
-  of each vertex after it is discovered.
-
-<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked on each edge as it
-  becomes a member of the edges that form the search tree. If you
-  wish to record predecessors, do so at this event point.
-  
-<li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
-  the graph.
-  
-<li><b><tt>vis.forward_or_cross_edge(e, g)</tt></b> is invoked on
-  forward or cross edges in the graph. In an undirected graph this
-  method is never called.
-  
-<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
-  all of its out edges have been added to the search tree and all of
-  the adjacent vertices have been discovered (but before their
-  out-edges have been examined).
-
-</ul>
-
-
-<H3>Example</H3>
+OUT: <tt>predecessor_map(PredMap pred)</tt>
+<blockquote>
+  This map, on output, will contain the predecessor of each vertex in the graph
+  in the spanning tree.  The value
+  <tt>graph_traits&lt;Graph&gt;::null_vertex()</tt> will be used as the
+  predecessor of the root of the tree.  The type <tt>PredMap</tt> must be a
+  model of
+  <a
+  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+  Map</a>. The key and value types of the map must both be the graph's vertex type.<br>
+</blockquote>
 
-<P>
-The example in <a href="../example/dfs-example.cpp">
-<TT>examples/dfs-example.cpp</TT></a> shows DFS applied to the graph in
-Figure 1.
-
-<h3>See Also</h3>
-
-depth_first_visit
-undirected_dfs
-
-<h3>Notes</h3>
-
-<p><a name="1">[1]</a> 
-  Since the visitor parameter is passed by value, if your visitor
-  contains state then any changes to the state during the algorithm
-  will be made to a copy of the visitor object, not the visitor object
-  passed in. Therefore you may want the visitor to hold this state by
-  pointer or reference.
+IN: <tt>weight_map(WeightMap weight)</tt>
+<blockquote>
+  This map contains the weight of each edge in the graph.  The probability of
+  any given spanning tree being produced as the result of the algorithm is
+  proportional to the product of its edge weights.  If the weight map is
+  omitted, a default that gives an equal weight to each edge will be used; a
+  faster algorithm that relies on constant weights will also be invoked.
+  The type <tt>WeightMap</tt> must be a
+  model of
+  <a
+  href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+  Map</a>. The key type of the map must be the graph's edge type, and the value
+  type must be a real number type (such as <tt>double</tt>).<br>
+</blockquote>
 
 <br>
 <HR>
Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html	(original)
+++ trunk/libs/graph/doc/table_of_contents.html	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -176,6 +176,11 @@
           <LI><A
           href="./prim_minimum_spanning_tree.html"><tt>prim_minimum_spanning_tree</tt></A>
         </OL>
+      <LI>Random Spanning Tree Algorithm
+        <OL>
+          <LI><A
+          href="./random_spanning_tree.html"><tt>random_spanning_tree</tt></A>
+        </OL>
       <LI>Connected Components Algorithms
       <OL>
           <LI>connected_components
Modified: trunk/libs/graph/test/random_spanning_tree_test.cpp
==============================================================================
--- trunk/libs/graph/test/random_spanning_tree_test.cpp	(original)
+++ trunk/libs/graph/test/random_spanning_tree_test.cpp	2010-07-03 15:50:49 EDT (Sat, 03 Jul 2010)
@@ -57,12 +57,12 @@
   BGL_FORALL_EDGES(e, g, graph_type) {put(weight, e, (1. + get(edge_index, g, e)) / num_edges(g));}
 
   mt19937 gen;
-  random_spanning_tree(g, pred, gen);
+  random_spanning_tree(g, gen, predecessor_map(pred));
   // write_spanning_tree(g, pred, constant_property_map<gt::edge_descriptor, double>(1.), "unweight_random_st.dot");
-  random_spanning_tree(g, pred, gen);
+  random_spanning_tree(g, gen, predecessor_map(pred));
   // write_spanning_tree(g, pred, constant_property_map<gt::edge_descriptor, double>(1.), "unweight_random_st2.dot");
 
-  weighted_random_spanning_tree(g, pred, weight, gen);
+  random_spanning_tree(g, gen, predecessor_map(pred).weight_map(weight));
   // write_spanning_tree(g, pred, weight, "weight_random_st.dot");
 
   return 0;