Subject: [Boost-commit] svn:boost r63559 - in branches/release: . boost boost/algorithm/string boost/archive boost/bimap boost/config boost/detail boost/filesystem boost/functional/hash boost/fusion boost/gil boost/graph boost/integer boost/interprocess boost/intrusive boost/iostreams boost/math boost/msm boost/numeric/ublas boost/program_options boost/property_tree boost/python boost/range boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/thread boost/tr1 boost/type_traits boost/unordered boost/utility boost/uuid boost/variant boost/wave doc libs libs/array/doc libs/array/test libs/bimap libs/config libs/filesystem libs/functional/hash libs/fusion libs/graph/doc libs/graph/test libs/graph_parallel libs/integer libs/interprocess libs/intrusive libs/iostreams libs/math libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/msm libs/numeric/ublas libs/numeric/ublas/doc libs/program_options libs/property_tree libs/python libs/python/doc/v2 libs/range libs/range/doc libs/regex libs/serialization libs/signals libs/signals2 libs/spirit libs/spirit/classic/example libs/spirit/doc libs/spirit/example libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/statechart libs/static_assert libs/system libs/thread libs/timer libs/tr1 libs/type_traits libs/unordered libs/utility libs/utility/swap/test libs/uuid libs/wave more more/getting_started status tools tools/bcp tools/boostbook tools/build/v2 tools/build/v2/tools tools/inspect tools/jam tools/quickbook tools/regression tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2010-07-03 15:56:36
Author: jewillco
Date: 2010-07-03 15:56:35 EDT (Sat, 03 Jul 2010)
New Revision: 63559
URL: http://svn.boost.org/trac/boost/changeset/63559
Log:
Merged r63557 from trunk
Added:
branches/release/libs/graph/doc/random_spanning_tree.html
- copied unchanged from r63557, /trunk/libs/graph/doc/random_spanning_tree.html
Properties modified:
branches/release/ (props changed)
branches/release/INSTALL (props changed)
branches/release/Jamroot (props changed)
branches/release/LICENSE_1_0.txt (props changed)
branches/release/boost/ (props changed)
branches/release/boost-build.jam (props changed)
branches/release/boost.css (props changed)
branches/release/boost.png (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/array.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/config.hpp (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/detail/endian.hpp (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/functional/hash/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/gil/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/integer/ (props changed)
branches/release/boost/interprocess/ (props changed)
branches/release/boost/intrusive/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/msm/ (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/numeric/ublas/functional.hpp (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/serialization/factory.hpp (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/karma/ (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/statechart/ (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/thread/ (props changed)
branches/release/boost/thread.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/boost/utility/ (props changed)
branches/release/boost/utility/value_init.hpp (props changed)
branches/release/boost/uuid/ (props changed)
branches/release/boost/variant/ (props changed)
branches/release/boost/version.hpp (props changed)
branches/release/boost/wave/ (props changed)
branches/release/bootstrap.bat (props changed)
branches/release/bootstrap.sh (props changed)
branches/release/doc/ (props changed)
branches/release/index.htm (props changed)
branches/release/index.html (props changed)
branches/release/libs/ (props changed)
branches/release/libs/array/doc/array.xml (props changed)
branches/release/libs/array/test/array0.cpp (props changed)
branches/release/libs/array/test/array2.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/functional/hash/ (props changed)
branches/release/libs/fusion/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/integer/ (props changed)
branches/release/libs/interprocess/ (props changed)
branches/release/libs/intrusive/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/msm/ (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/numeric/ublas/doc/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/python/doc/v2/args.html (props changed)
branches/release/libs/python/doc/v2/return_internal_reference.html (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/range/doc/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/doc/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/statechart/ (props changed)
branches/release/libs/static_assert/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/thread/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/type_traits/ (props changed)
branches/release/libs/unordered/ (props changed)
branches/release/libs/utility/ (props changed)
branches/release/libs/utility/swap.html (props changed)
branches/release/libs/utility/swap/test/std_bitset.cpp (props changed)
branches/release/libs/utility/value_init.htm (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/uuid/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/more/ (props changed)
branches/release/more/getting_started/ (props changed)
branches/release/rst.css (props changed)
branches/release/status/ (props changed)
branches/release/status/Jamfile.v2 (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/build/v2/tools/ (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/jam/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/graph/loop_erased_random_walk.hpp | 9 ++++
branches/release/boost/graph/random_spanning_tree.hpp | 76 +++++++++++++++++++++------------------
branches/release/libs/graph/doc/bibliography.html | 8 +++
branches/release/libs/graph/doc/table_of_contents.html | 5 ++
branches/release/libs/graph/test/random_spanning_tree_test.cpp | 6 +-
5 files changed, 64 insertions(+), 40 deletions(-)
Modified: branches/release/boost/graph/loop_erased_random_walk.hpp
==============================================================================
--- branches/release/boost/graph/loop_erased_random_walk.hpp (original)
+++ branches/release/boost/graph/loop_erased_random_walk.hpp 2010-07-03 15:56:35 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: branches/release/boost/graph/random_spanning_tree.hpp
==============================================================================
--- branches/release/boost/graph/random_spanning_tree.hpp (original)
+++ branches/release/boost/graph/random_spanning_tree.hpp 2010-07-03 15:56:35 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: branches/release/libs/graph/doc/bibliography.html
==============================================================================
--- branches/release/libs/graph/doc/bibliography.html (original)
+++ branches/release/libs/graph/doc/bibliography.html 2010-07-03 15:56:35 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 & 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 Bruce 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>
Modified: branches/release/libs/graph/doc/table_of_contents.html
==============================================================================
--- branches/release/libs/graph/doc/table_of_contents.html (original)
+++ branches/release/libs/graph/doc/table_of_contents.html 2010-07-03 15:56:35 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: branches/release/libs/graph/test/random_spanning_tree_test.cpp
==============================================================================
--- branches/release/libs/graph/test/random_spanning_tree_test.cpp (original)
+++ branches/release/libs/graph/test/random_spanning_tree_test.cpp 2010-07-03 15:56:35 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;