Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net