Bug in Boost BGL graph traversal

[public@…]

Using listS as the representation for both vertices and edges, BGL's depth_first_search sometimes calls back_edge() on visitors even if there are no cycles in the graph.

Code example: ​http://static.ali01.com/bgl.cc

The above program should not print "back edge", but does.

[public@…]

code example of bug

[Jeremiah Willcock]

You are not initializing the vertex_index property of your graph. Try adding some code such as:

graph_traits<Graph>::vertices_size_type i = 0;
BGL_FORALL_VERTICES(v, graph, Graph) put(vertex_index, g, v, i++);

before your call to depth_first_search (filling in the types for your code, and #includeing <boost/graph/iteration_macros.hpp>).