Re: [Boost-users] [BGL] detect cycles in a directed graph

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-09-22 01:19:31

Giulio Veronesi wrote:

> Hi,
> 
> This is my second post for the same problem. Excuse me!
> 
> I think that the problema can be resolved using the EventVisitor Concept
> but I don't understand how use it. I would be extremely grateful for any
> assistance in the following problem: "get all the edges of a cycle".

Of which cycle? 

If you want to get at least one cycle in a graph that has one, then you need
to create a visitor that implements "back_edge" method and use predecessor
map to traverse the cycle in reverse order.

If you want to get all cycles in a graph -- well, the best algorithm is
something like O(n + e) *per cycle* and there could be exponentially many
cycles, and that algorithm is not in Boost. 

- Volodya