c++ - 特定の基準が満たされた場合、特定の深さに沿ってboost::depth_first_searchを停止します

Question

DAGの保存にBGLを使用しています。頂点には状態があります。頂点の1つで状態が変化した場合、依存する頂点を更新したいと思います。これは、boost::depth_first_searchとカスタムビジターを使用して実行できます。

ここでの論理は、検索された頂点と、頂点が特定の状態にある場合にその依存する頂点を更新したくないということです。基本的に、dfsまたはbfsのいずれかで頂点のエンキューを制御したいと思います。BGLでこれを達成するための最良の方法は何ですか。

ありがとう。

Answer 1

boost ::depth_first_searchはこれをサポートしていないようですが、基礎となるboost ::depth_first_visitは、「ターミネーター関数」（TerminatorFunc）を可能にする2番目のオーバーロードを通じてサポートしています。

したがって、boost ::depth_first_searchの実装をコピーし、boost::depth_first_visitに渡されたdetail::nontruth2（）パラメーターを独自の（重要な）ターミネーター関数に置き換えることができます。

Answer 2

深さ優先探索での終了の欠如は、私が今まで見たグラフライブラリの中で最も愚かなことです。

たぶん、これは抜け道かもしれません：filtered_graphのdepth_first_search。どういうわけかstop-vertexをマークすることができ、filtered_graphのfilter-edges関数では、入射エッジを非表示にするだけです。