Re: [Boost-users] [boost] BGL - cycles in an undirected graph
On 7/20/06, Michal <simecek@gmx.de> 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
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@gmail.com> wrote:
On 7/20/06, Michal <simecek@gmx.de> 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
participants (7)
-
Aaron Windsor -
Michal Simecek