Có thể thay đổi điều kiện kết thúc tìm kiếm đầu tiên trong BGL không?

Question

Tôi mới dùng BGL (tăng thư viện biểu đồ). Tôi đang học giao diện breadth_first_search và có vẻ tiện dụng. Tuy nhiên, trong ứng dụng của tôi, tôi cần phải cắt breadth_first_search khi một số điều kiện kết thúc khác được đáp ứng chẳng hạn như số lượng nút tìm kiếm không gian đáp ứng tối đa.

Tôi có thể thêm điều kiện chấm dứt mới với BFSVisitors hoặc có bất kỳ mẹo nào khác không?

Cảm ơn!

Answer 1

Sau (hơi muộn) trên nhận xét @yuyoyuppe, bạn có thể tạo một khách truy cập proxy sẽ bao bọc khách truy cập thực và ném khi một vị từ đã cho được đáp ứng. Việc triển khai tôi đã chọn để giải quyết phiếu mua hàng cho bạn khả năng chạy các biến vị ngữ trên discover_vertex và examine_edge. Trước tiên, chúng tôi xác định biến vị ngữ mặc định luôn trả về false:

namespace details { 

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

Sau đó, bản thân mẫu.

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; 
}; 

Nó sẽ mất 3 mẫu đối số:

1. Một vị đỉnh áp dụng trên mỗi cuộc gọi đến discover_vertex (cùng một lúc nhất cho mỗi đỉnh)
2. Một vị tiến, áp dụng trên mỗi cuộc gọi đến examine_edge (tối đa một lần cho mỗi cạnh)
3. Thực hiện khách truy cập thực tế mà từ đó chúng tôi sẽ kế thừa

Để xây dựng nó, chúng tôi chỉ đơn giản là khởi tạo người truy cập cơ sở và hai vị từ chúng tôi:

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) {} 

Sau đó, chúng ta phải làm một (tư nhân) chức năng proxy để thực hiện các cuộc gọi phù hợp với việc thực hiện cơ sở và kiểm tra ngữ:

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"); 
    } 
} 

Tất nhiên, tôi uể oải dùng std::runtime_error nhưng bạn nên xác định loại ngoại lệ của riêng mình, có nguồn gốc từ std::exception hoặc bất cứ cơ sở ngoại lệ lớp học mà bạn sử dụng.

Bây giờ chúng ta có thể dễ dàng xác định hai callbacks của chúng tôi:

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)); 
} 

Chúng tôi sẽ kiểm tra cơ sở của chúng tôi trên một đỉnh ngữ tùy chỉnh mà trả về true vào việc khám phá ra đỉnh N-thứ.

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; 
}; 

Thực hiện BFS trên một đồ thị nào đó, nó sẽ được dễ dàng:

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; 
} 

Một live demo on Coliru có sẵn để giúp bạn xem tất cả các mảnh trong hành động.