即使图中没有循环,BGL的depth_first_search算法有时会对访问者调用back_edge().根据后缘的定义,根据Boost的
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进行测试.
解决方法
您提交了一个错误,但您没有跟进.
不久之后,你得到了答案：
You are not initializing the vertex_index property of your graph. Try adding some code such as:
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,i++); bool inserted; tie(tuples::ignore,g); assert(inserted); VisitorClass vst; depth_first_search(g,visitor(vst)); // Should not print "back edge",but does. return 0; }(至少,它不再打印“后缘”)
