Re: [Boost-users] Detecting cycles in graph

From: Abde Ali Kagalwalla (abdeali.iitb_at_[hidden])
Date: 2008-06-27 11:40:56

Hi,

So, basically I want to find the number of cycles in an undirected graph.
Now the vertices of the
graph are colored red or green. As soon as I locate a cycle, I want to count
the number of red and black vertices in the cycle.
I want to find all possible cycles and the number of red and black vertices
for each cycle.

I was thinking of using BFS but it is ok if I can find the solution using
DFS or some other method.

Thanks,

Abde Ali

On Fri, Jun 27, 2008 at 2:32 PM, Dmitry Bufistov <dmitry_at_[hidden]> wrote:

> David Abrahams wrote:
>
>> Vladimir Prus wrote:
>>
>>> Abde Ali Kagalwalla wrote:
>>>
>>>  Hi,
>>>>
>>>> I want to use the BFS to detect cycles in a graph I constructed using
>>>> bundled vertex properties. I want a feature that as soon as I detect a
>>>> cycle, I can do some processing on the cycle path and then go back to
>>>> look
>>>> for other cycles in the main graph.
>>>>
>>> So, you want to do something for each cycle in the graph? Not for each
>>> strongly connected component? There are algorithms for enumerate all
>>> cycles in a graph, but those algorithms are not included in BGL, and
>>> a far from easy.
>>>
>>
>> Maybe I'm missing something, but isn't this as easy as hooking back_edge
>> on a DFSVisitor and using depth_first_search?
>>
>>
> Yep, looks very simple, taking into account the complexity of DFS is linear
> in the respect of the edges number while the number of simple cycles in a
> digraph potentially can be exponential large.
>
> Ali, please describe your original problem. The tedious cycles enumeration
> often can be avoided :-)
>
> Dmitry
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>