Re: [Boost-users] Detecting cycles in graph

From: Vladimir Prus (vladimir_at_[hidden])
Date: 2008-06-27 08:24:07

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?

This will allow you to identify back edges -- that is edges that
are surely part of some cycle. Given that a given edge can be a
part of 2^|V| cycles, knowing that a given edge is a back edge is
clearly not a solution for "enumerate all cycles" problem. A brute-force
algorithm is not hard to write, but the point of algorithm running
in exponential time and requiring exponential memory is questionable.

So, there exist algorithms that allow to iterate over all cycles,
where the complexity of getting the next cycle is linear-or-something.
I'd suggest to take a look of them before trying to write your own
algorithm :-).

- Volodya