即使图中没有循环,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, 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; }
(至少,它不再打印“后边缘”)
关于Boost 图形库 : Potential Bug,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7047667/