5

私はBGL（ブーストグラフライブラリ）が初めてです。私はbreadth_first_searchインターフェースを学んでいますが、便利そうです。ただし、私のアプリケーションでは、検索空間ノード数が最大値に達した場合など、他の終了条件が満たされた場合に、breadth_first_search をカットする必要があります。

BFSVisitors で新しい終了条件を追加できますか、それとも他のトリックはありますか?

ありがとう！

4

1 に答える 1

4

@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 つのテンプレート引数を取ります。

  1. への各呼び出しに適用される頂点述語discover_vertex(頂点ごとに最大 1 回)
  2. 各呼び出しに適用されるエッジ述語 (エッジごとexamine_edgeに最大 1 回)
  3. 継承する実際の訪問者の実装

それを構築するには、ベース ビジターと 2 つの述語を初期化するだけです。

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

これで、2 つのコールバックを簡単に定義できます。

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

Coliruのライブ デモを利用して、すべての部品の動作を確認できます。

于 2016-10-28T13:43:01.703 に答える