Detect cycles in undirected graph using boost graph library

I've been stuck since yesterday with this problem. Unfortunately/fortunately this problem makes only about 0.5% of the my super huge (for me, a c++ newbie) algorithm thus the need for a library of existing code that one can just adapt and get things working.

I'll like to detect and give out all the circles in an undirected graph. My edges are not weighted. Yes, what I need is really all the cycles i.e. somthing like all the hamiltonian cycles of a directed graph

I've been playing aroung with boost graph library, the DFS algorithm seemed very promissing, however, it visits the vertices only once and as such cannot give all hamiltonian circles.

For the moment, I just need the code to work, so that I can continue my algorithm design, afterwards I may consider performance issues. Even a solution with 5-nested for loops is welcome.

Here is a code I got and played around with from boost but I don't know how to record and access my predecessors of back_edges and even if that was solve, boost DFS will visit vertices only once:

struct detect_loops : public boost::dfs_visitor<>
{
   template <class Edge, class Graph>
   void back_edge(Edge e, const Graph& g) {
      std::cout << source(e, g)
        << " -- "
        << target(e, g) << "\n";
   }
};

int main(int,char*[])
{
    typedef std::pair<int,int> Edge;
    std::vector<Edge> edges;
    edges.push_back(Edge(0,1));
    edges.push_back(Edge(1,2));
    edges.push_back(Edge(2,3));
    edges.push_back(Edge(3,1));
    edges.push_back(Edge(4,5));
    edges.push_back(Edge(5,0));
    edges.push_back(Edge(4,0));
    edges.push_back(Edge(5,6));
    edges.push_back(Edge(2,6));

    typedef adjacency_list<
       vecS, vecS, undirectedS, no_property,
       property<edge_color_t, default_color_type>
    > graph_t;
    typedef graph_traits<graph_t>::vertex_descriptor vertex_t;

    graph_t g(edges.begin(), edges.end(), 7);

    std::cout << "back edges:\n";
    detect_loops vis;
    undirected_dfs(g, root_vertex(vertex_t(0)).visitor(vis).edge_color_map(get(edge_color, g)));
    std::cout << std::endl;

    return 0;
}

The example above says there are only 3 cycles normally I'll expect more than 4 whereby a single vertex may appear in multiple cycles. And secondly even, I cannot even access all the three the cycles that boost's back_edge() gives me like this std::vector<uInt32> fCycle1, fCycle2,fCycle3. All I get from back_edge() is just the source and target vertices.

I'll be grateful for any help and tips. So far, all the examples here will just detect the presence of a cycle or a number thereof but none has shown how to list all of the cycles present.

Recommended topics

Hot tags