Boost DFS back_edge

Question

I'm trying to find all edges that are part of any cycle in a undirected Graph. Using Boost's depth_first_search and my understanding of back edges, I don't see why the back_edge method is called for both edges in the sample Graph which doesn't contain any cycles.

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::edge_descriptor Edge;

class MyVisitor : public default_dfs_visitor {
    public: void back_edge(Edge e, const Graph& g) const {
        // should only be called when cycle found, right?
        cerr << "back_edge " << e << endl;
        return;
    }
};

int main() {
    Graph g;
    add_edge(0, 1, g);
    add_edge(0, 2, g);

    MyVisitor vis;
    depth_first_search(g, visitor(vis));
    return 0;
}

Answer 1

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() and back_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));
}