boost – 是否可以在BGL中更改广度优先搜索终止条件？

概述我是BGL(boost图库)的新手.我正在学习breadth_first_search接口,它看起来很方便.但是,在我的应用程序中,我需要在遇到其他一些终止条件时剪切breadth_first_search,例如搜索空间节点数满足最大值. 我可以在BFSVisitors中添加新的终止条件,还是有其他技巧？ 谢谢！ 关于@yuyoyuppe评论(稍晚),您可以创建一个代理访问者,它将包装一个实际访问 我是BGL(boost图库)的新手.我正在学习breadth_first_search接口,它看起来很方便.但是,在我的应用程序中,我需要在遇到其他一些终止条件时剪切breadth_first_search,例如搜索空间节点数满足最大值.

我可以在BFSVisitors中添加新的终止条件,还是有其他技巧？

谢谢！

解决方法 关于@yuyoyuppe评论(稍晚),您可以创建一个代理访问者,它将包装一个实际访问者并在满足给定谓词时抛出.我选择解决的实现为您提供了在discover_vertex和examine_edge上运行谓词的能力.首先,我们定义一个返回总是false的默认谓词：

namespace details {struct no_halting {    template <typename GraphElement,typename Graph>    bool operator()(GraphElement const&,Graph const&) {        return false;    }};} // namespace details

然后,模板本身.

template <typename VertexPredicate = details::no_halting,typename EdgePredicate = details::no_halting,typename BFSVisitor = boost::default_bfs_visitor>struct bfs_halting_visitor : public BFSVisitor {    // ... Actual implementation ...private:    VertexPredicate vpred;    EdgePredicate epred;};

它将需要3个模板参数：

>每次调用discover_vertex时应用的顶点谓词(每个顶点最多一次)
>边缘谓词,应用于每次调用examine_edge(每个边缘最多一次)
>我们将继承的实际访客实现

要构建它,我们只需初始化基本访问者和我们的两个谓词：

template <typename VPred,typename EPred,typename ... VisArgs>bfs_halting_visitor(VPred&& vpred,EPred&& epred,VisArgs&&... args) :                    BFSVisitor(std::forward<VisArgs>(args)...),vpred(vpred),epred(epred) {}

然后,我们必须创建一个(私有)代理函数来执行对基本实现的适当调用并检查谓词：

template <typename Pred,typename R,typename ... FArgs,typename ... Args>voID throw_on_predicate(R (BFSVisitor::*base_fct)(FArgs...),Pred&& pred,Args&&... args) {    bool result = pred(args...);    (this->*base_fct)(std::forward<Args>(args)...);    if (result) {        throw std::runtime_error("A predicate returned true");    }}

当然,我懒惰地使用了std :: runtime_error但你应该定义自己的异常类型,派生自std :: exception或你使用的任何基类异常类.

现在我们可以轻松定义两个回调：

template <typename Edge,typename Graph>voID examine_edge(Edge&& e,Graph&& g) {    throw_on_predicate(&BFSVisitor::template examine_edge<Edge,Graph>,epred,std::forward<Edge>(e),std::forward<Graph>(g));}template <typename Vertex,typename Graph>voID discover_vertex(Vertex&& v,Graph&& g) {    throw_on_predicate(&BFSVisitor::template discover_vertex<Vertex,vpred,std::forward<Vertex>(v),std::forward<Graph>(g));}

我们将在自定义顶点谓词上测试我们的设施,该谓词在第N个顶点的发现时返回true.

struct VertexCounter {    VertexCounter(std::size_t limit) : count(0),limit(limit) {}    VertexCounter() : VertexCounter(0) {}    template <typename V,typename G>    bool operator()(V&&,G&&) {        return ((++count) > limit);    }private:    std::size_t count;    std::size_t const limit;};

要在给定图表上执行bfs,它将很容易：

Graph graph = get_graph();Vertex start_vertex;bfs_halting_visitor<VertexCounter> vis(VertexCounter(2),details::no_halting());try {    boost::breadth_first_search(graph,start_vertex,boost::visitor(vis));} catch (std::runtime_error& e) {    std::cout << e.what() << std::endl;}

live demo on Coliru可以帮助您查看所有 *** 作.

总结

以上是内存溢出为你收集整理的boost – 是否可以在BGL中更改广度优先搜索终止条件？全部内容，希望文章能够帮你解决boost – 是否可以在BGL中更改广度优先搜索终止条件？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。