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

From: Michal Simecek (simecek_at_[hidden])
Date: 2006-07-27 03:45:56

Hi,

I think I found an Algo based on DFS which solves my Problem.

Aaron, thanks for your input.

Michal

On Fri, 21 Jul 2006 01:09:03 +0200, Aaron Windsor  
<aaron.windsor_at_[hidden]> wrote:

> 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