Boost logo

Boost Users :

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2008-06-27 05:02:57

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 :-)


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at