Re: [Boost-users] [boost] BGL - cycles in an undirected graph

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2006-07-20 19:09:03

On 7/20/06, Michal <simecek_at_[hidden]> wrote:
> my task is to find cycles in an undirected graph and to assign a cycle id
> to each
> vertex in this cycle. It is still a bit more complicated, because I do not
> need just the simple cycles, but all simple cycles which are sharing
> edges, must
> get the same cycle id.
>
> I think this problem is already solved somewhere, but I cann not find the
> right
> approach, thus I am asking here if somebody have an idea how to solve it
> best
> with BGL.

Michal,

If you want to label the edges of a graph such that
(1) any two edges that are on a simple cycle together get the same label, and
(2) any two edges not on any cycle together get distinct labels
then you simply want to find the biconnected components of the graph - there's
a way to do this in linear time using depth-first search, and the
algorithm is in
the BGL:

http://www.boost.org/libs/graph/doc/biconnected_components.html

However, the fact that you said that you want to label all vertices in the
graph with a distinct label subject to condition (1) above is a little
confusing - you can have two cycles that don't meet in any edges but
share a common vertex, and in that case, which of the two labels would
you want to use for that vertex?

Aaron