Re: [Boost-users] Identify cycles in a undirected graph

Subject: Re: [Boost-users] Identify cycles in a undirected graph
From: NsPx (nspx.roronoa_at_[hidden])
Date: 2012-02-10 02:45:36

Thanks a lot Jeremiah, it works as expected !

Le 08/02/2012 19:17, Jeremiah Willcock a écrit :
> On Wed, 8 Feb 2012, NsPx wrote:
>
>> Hi all,
>>
>> I use undirected_dfs to detect all cycles in a undirected graph.
>> I detect a cycle with DFSVisitor.back_edge(e,g) but how can I get the 
>> list of vertices defining this cycle ?
>
> Keep a predecessor map using predecessor_recorder, then walk the chain 
> of predecessors from the target of the back_edge to its source.  The 
> vertices you iterate through are your cycle.  Reading 
> http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf gives the 
> algorithm and why it works in more detail.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users