是否可以在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可幫助你看到所有工作中的碎片。