Boost Graph Library: Potential Error

Question

The BGL depth_first_search algorithm sometimes calls back_edge () for visitors, even if there are no loops on the chart. By definition of the trailing edge and in accordance with the Boost DFS Visitor Documentation, this should not happen. Note that this is only reproduced when listS is used as a representation for both vertices and edges.

The code example below (should compile as is) builds a graph with two nodes and one edge. It does not print back edge correctly. Am I doing something wrong here? Or is this a mistake?

#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; } 

Tested with Boost 1.46.1 using i686-apple-darwin11-llvm-g ++ - 4.2 on Mac OS 10.7;
Tested with Boost 1.42.0 using gcc 4.4.5 on Debian 2.6.32-34squeeze1.

Answer 1

You filed an error, but you did not trace there.

Soon after, you received an answer:

You are not initializing the vertex_index property of your chart. Try adding code, for example:

graph_traits :: vertices_size_type i = 0;

BGL_FORALL_VERTICES (v, graph, Graph) put (vertex_index, g, v, i ++);

I tried this (typo correction) and it works fine:

 #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; } 

(at least it no longer prints "trailing edge")