BGL: Loops in undirected graph

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2002-08-19 07:36:10

Is there any "standard best way" of detecting loops in an undirected
graph? I had a look at chapter 4.2 in the book (which does an
implementation for bidirectional graphs), and tried to adapt this
implementation, but with no particular luck :) The graph I've set up in
my test suite looks like this (I hope my mail prog. doesn't screw up the
formatting)

               H15
               |
      H8       C2
        \     /  \
      H9-C0-C1    C3-O7-H14
        /   |     |
      H10   C6    C4
           /  \  /  \
          H11  C5    H13
               |
               H12

I'm working with molecules, so the letters denote the type of atom, but
that's of no importance here. The numbers are the vertex descriptors.

What I'm trying to create is an algorithm that will return the set of
vertices [1, 2, 3, 4, 5, 6] defining.

Now, my first step is (exactly like in the book) to record every back
edge in the graph. As my graph is undirected, and there is allways a
path from any one vertex to any other vertex, I thought I could just do
a DFS from the first vertex in any such graph and record the back edges.
In the above example, starting from 'C0', I'd expect the set of back
edges obtained from a DFS to be 1-2, 2-3, 3-4, 4-5, 5-6 and 6-1, a total
of 6 edges. The actual result obtained however also includes the
following edges: 1-0, 11-6, 12-5, 13-4, 7-3, 14-7, 15-2, 8-0, 9-0 and
10-0. 

Why is this? I'm assuming there's something I missed out on, regarding
graph theory and how the basic DFS works, but I cannot see any logic in
this. If so, how could I modify my DFS visitor to record the (in my
problem domain) "correct" back edges?

This problem also gives me further trouble when trying to detect which
vertices are part of each cycle. Does any of you have any suggestion for
an effective implementation of the "find vertices that are part of each
cycle" part of the algorithm?

Any help appreciated.

Cheers,
-- 
Tarjei Knapstad