Since your graph is undirected, any tree edge is also a back edge. The documentation for DFSVisitor doesn't fail to mention this.
For an undirected graph there is some ambiguity between tree edges and back edges since the edge (u,v) and (v,u) are the same edge, but both the
tree_edge()
andback_edge()
functions will be invoked.One way to resolve this ambiguity is to record the tree edges, and then disregard the back-edges that are already marked as tree edges. An easy way to record tree edges is to record predecessors at the tree_edge event point.
Implementing this in the most straightforward manner: Live on Coliru
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
namespace {
using namespace boost;
typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::edge_descriptor Edge;
typedef std::set<Edge> EdgeSet;
}
struct MyVisitor : default_dfs_visitor {
MyVisitor(EdgeSet& tree_edges) : tree_edges(tree_edges) {}
void tree_edge(Edge e, const Graph& g) const {
std::cerr << "tree_edge " << e << std::endl;
tree_edges.insert(e);
}
void back_edge(Edge e, const Graph& g) const {
if (tree_edges.find(e) == tree_edges.end())
std::cerr << "back_edge " << e << std::endl;
}
private:
EdgeSet& tree_edges;
};
int main() {
Graph g;
add_edge(0, 1, g);
add_edge(0, 2, g);
std::set<Edge> tree_edges;
MyVisitor vis(tree_edges);
depth_first_search(g, visitor(vis));
}