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

From: Simon Buchan (simon_at_[hidden])
Date: 2005-09-23 03:44:38

Andrea Olgiati wrote:
> Giulio,
> 
> Here's an idea. You say you want to list all the vertices that make up
> any one of the (potentially very numerours) cycles that originate on a
> vertex X. If  _any_ cycle will do, how about the shortest? You can use
> Dijkstra. From
> http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html: "Also
> you can record the shortest paths tree in a predecessor map: for each
> vertex u in V, p[u] will be the predecessor of u in the shortest paths
> tree (unless p[u] = u, in which case u is either the source or a vertex
> unreachable from the source)."
> 
> I don't think Dijkstra will work on a path that looks like V->X->Y->U->V
> (ie, a cycle). But, to get around this, you do know that U->V is an
> edge, so you can compute the shortest path between V and U, and know
> that there's an edge between U and V.
> 
> HTH,
> Andrea
> 
> --
> Andrea Olgiati - Elixent - Castlemead, Lwr Castle St., Bristol BS1 3AG,
> UK
> andrea.olgiati_at_[hidden]                             ++44 (0)117
> 9175612 
<snip>
Nice trick! (just remember to snip long quotes) That could probably be 
generalised with a bit of effort, may be useful to someone (like the 
poor OP :D).