7

BGL の depth_first_search アルゴリズムは、グラフに循環がない場合でも、訪問者に対して back_edge() を呼び出すことがあります。バック エッジの定義により、また Boost のDFS Visitor Documentationによると、これは発生しないはずです。これは、listS が頂点とエッジの両方の表現として使用されている場合にのみ再現可能であることに注意してください。

以下のコード例 (そのままコンパイルする必要があります) は、2 つのノードと 1 つのエッジを持つグラフを作成します。「後端」が正しく印刷されません。私はここで何か悪いことをしていますか? それともこれはバグですか？

#include <iostream>
using namespace std;

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
using namespace boost;

typedef boost::property<boost::vertex_index_t,std::size_t> VertexProperties;
typedef boost::adjacency_list<boost::listS,
                              boost::listS,
                              boost::bidirectionalS,
                              VertexProperties> Graph;  // Graph object type

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

class VisitorClass : public dfs_visitor<> {
 public:
  VisitorClass() {}

  template <typename Edge, typename Graph>
  void back_edge(Edge, const Graph&) const {
    cout << "back edge" << endl;
  }
};

int
main() {
  Graph g;
  Vertex v = add_vertex(g);
  Vertex u = add_vertex(g);

  bool inserted;
  tie(tuples::ignore, inserted) = add_edge(v, u, g);
  assert(inserted);

  VisitorClass vst;
  depth_first_search(g, visitor(vst));
  // Should not print "back edge", but does.

  return 0;
}

Mac OS 10.7 で i686-apple-darwin11-llvm-g++-4.2 を使用して Boost 1.46.1 でテスト済み。
Debian 2.6.32-34squeeze1 で gcc 4.4.5 を使用して Boost 1.42.0 でテスト済み。

4

1 に答える 1

4

あなたはバグを報告しましたが、そこにフォローアップしませんでした。

その後まもなく、あなたは答えを得ました：

グラフの vertex_index プロパティを初期化していません。次のようなコードを追加してみてください。

graph_traits::vertices_size_type i = 0;

BGL_FORALL_VERTICES(v, グラフ, グラフ) put(頂点インデックス, g, v, i++);

私はこれを試しました（タイプミスを修正しました）が、うまくいきます：

#include <boost/graph/iteration_macros.hpp>

int main() {
  Graph g;   
  Vertex v = add_vertex(g);   
  Vertex u = add_vertex(g);

  graph_traits<Graph>::vertices_size_type i = 0;  
  BGL_FORALL_VERTICES(v, g, Graph) put(vertex_index, g, v, i++);

  bool inserted;   
  tie(tuples::ignore, inserted) = add_edge(v, u, g); 
  assert(inserted);

  VisitorClass vst;   
  depth_first_search(g, visitor(vst));
// Should not print "back edge", but does.

  return 0;
  }

（少なくとも、「後端」は印刷されなくなりました）

于 2011-11-09T22:20:28.830 に答える