title: Detect cycles in undirected graph using boost graph library
body: <p>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.</p>
  
  <p>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</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>struct detect_loops : public boost::dfs_visitor&lt;&gt;
  {
     template &lt;class Edge, class Graph&gt;
     void back_edge(Edge e, const Graph&amp; g) {
        std::cout &lt;&lt; source(e, g)
          &lt;&lt; " -- "
          &lt;&lt; target(e, g) &lt;&lt; "\n";
     }
  };
  
  int main(int,char*[])
  {
      typedef std::pair&lt;int,int&gt; Edge;
      std::vector&lt;Edge&gt; 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&lt;
         vecS, vecS, undirectedS, no_property,
         property&lt;edge_color_t, default_color_type&gt;
      &gt; graph_t;
      typedef graph_traits&lt;graph_t&gt;::vertex_descriptor vertex_t;
  
      graph_t g(edges.begin(), edges.end(), 7);
  
      std::cout &lt;&lt; "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 &lt;&lt; std::endl;
  
      return 0;
  } 
  </code></pre>
  
  <p>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 <code>back_edge()</code> gives me like this <code>std::vector&lt;uInt32&gt; fCycle1, fCycle2,fCycle3</code>. All I get from <code>back_edge()</code> is just the source and target vertices.</p>
  
  <p>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.</p>