首页 文章

Boost Graph Library:潜在的Bug

提问于
浏览
7

BGL 's depth_first_search algorithm sometimes calls back_edge() on visitors even if there are no cycles in the graph. By definition of back edge, and according to Boost' s DFS Visitor Documentation,这不应该发生 . 请注意,仅当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进行测试 .

1 回答

  • 4

    您提交了一个错误,但您没有跟进 .

    不久之后,你得到了答案:

    您没有初始化图形的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;
      }
    

    (至少,它不再打印“后缘”)

相关问题