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

Question

我是BGL（boost图库）的新手。我正在学习breadth_first_search界面，它看起来很方便。但是，在我的应用程序中，当满足其他一些终止条件时（例如搜索空间节点数达到最大值），我需要切断breadth_first_search。

我可以添加新的终止条件与BFSVisitors或有任何其他技巧？

谢谢！

Answer 1

@yuyoyuppe评论的后续内容（有点晚），您可以创建一个代理访问者来包装实际访问者并在给定谓词满足时抛出。我选择解决的实现为您提供了在discover_vertex和examine_edge上运行谓词的能力。首先，我们定义了一个默认的谓词返回始终为假：

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个模板参数：

1. （每顶点最多一次）施加在每个调用discover_vertex顶点谓词
2. 边缘谓词，施加在每次调用examine_edge（最多一次一次）
3. 我们将继承的实际访客实施

建造它，我们只是初始化基访客，我们两个谓词：

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, Graph>, 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可帮助你看到所有工作中的碎片。