
Boost : 
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 20060720 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 depthfirst 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk