使用 BGL 实现 random_spanning_tree

Question

我在实施 random_spanning_tree 时遇到了一些问题。

如何初始化随机数生成器？

   boost::uniform_int<> rng(0,9);
   boost::random::random_number_generator <boost::uniform_int<>, long> 
                                        gen(rng);

   boost::random_spanning_tree(g, gen,
                          boost::root_vertex(1).predecessor_map(&p[0])
                         ) ;

这是link：https://www.boost.org/doc/libs/1_64_0/libs/graph/doc/random_spanning_tree.html
运行这个函数的 gen 参数的模型应该是什么？
预先感谢您的帮助。

Answer 1

在我看来，您应该只传递一个引擎作为发电机。

示例

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random_spanning_tree.hpp>
#include <random>

int main() {
    using G = boost::adjacency_list<>;

    std::mt19937 gen;
    //std::uniform_int_distribution<> rng(0,9);

    G g(10);
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(2, 6, g);
    add_edge(6, 4, g);
    std::vector<G::vertex_descriptor> p(num_vertices(g));

    boost::random_spanning_tree(g, gen, boost::root_vertex(1).predecessor_map(&p[0])); 
}

这将可预见的失败并出现 boost::loop_erased_random_walk_stuck 异常。

使用 BGL 实现 random_spanning_tree

Implementation of random_spanning_tree using BGL

c++

boost

random-seed