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