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

Question

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

我可以使用 BFSVisitor 添加新的终止条件还是有任何其他技巧？

谢谢!

Answer 1

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

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

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可帮助您查看所有正在运行的部分。