BGL: cycles in undirected graph

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-02-06 09:54:14

(Disclaimer: My knowledge of graph theory isn't too broad, so have me
excused if this is completely trivial...)

I'm struggling a bit with finding cycles in an undirected graph. Doing a
DFS/BFS and recording back edges, thus detecting the number of cycles
and a connected vertex pair for each one is simple enough. However, I'd
also like to find the sequence(s) of vertices that make up the cycle.

There's and example in the book that does this, but relies on a graph
with direction in the second step where a DFS is done from both
back-edge vertices and the results intersected. This won't work in the
case of an undirected graph as every vertex is reachable from any other
(if there's only one "connected component"), so I would just end up with
the complete set of vertices in every case.

My idea is to use BFS and the record_predecessors visitor, but I can't
seem to wrap my head around how to find the sequence of vertices
connecting the cycle(s) from this.

Could anyone offer some pointers? (hopefully not NULL :) )

Regards,
--
Tarjei