提升图表库：潜在的错误

即使图中没有循环，BGL的depth_first_search算法有时也会对访问者调用back_edge（）。 根据后沿的定义，根据Boost的DFS访问者文档，这不应该发生。 请注意，只有在使用listS作为顶点和边的表示形式时，才能重现此问题。

下面的代码示例（应按原样编译）构造一个具有两个节点和一个边的图。 它错误地打印“后缘”。 我在这里做错了什么？ 或者这是一个错误？

#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。

---

你提交了一个bug，但你没有跟进。

不久之后，你得到了一个答案：

您没有初始化图形的vertex_index属性。 尝试添加一些代码，如：

graph_traits :: vertices_size_type i = 0;

BGL_FORALL_VERTICES（v，graph，Graph）put（vertex_index，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;
  }

（至少，它不再打印“后边缘”）

链接地址: http://www.djcxy.com/p/9041.html

上一篇: Boost Graph Library: Potential Bug

下一篇: What buffering strategy should I use for my 2D scrolling map?