Simple cycle removing algorithm for a BGL graph

Question

My problem should be pretty simple, given a graph (BGL adjacency_list) is there a simple algorithm to remove cycles? My first attempt was to use the DFS visitor to detect an edge that'd close the cycle and then remove it but I was unable to implement it correctly.

Any suggestions? Code samples would be best.

Answer 1

Boost is great. It has a depth_first_search method that accepts a visitor. You can see more information about it here.

All you need to do is implement a visitor like this:

class CycleTerminator : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) {
        //implement
    }
};

remembering of course that a back edge is an edge that closes a cycle in the graph.