[BGL] detect cycles in a directed graph
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". Thanks a lot in advance, Giulio
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
Vladimir Prus ha scritto:
Giulio Veronesi wrote:
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.
Yes! Only one cycle. Please, could you give me a pratical example (just
the pseudo code)? I've very little experience with BGL. Do you intend
something like this?
template
participants (2)
-
Giulio Veronesi
-
Vladimir Prus