Boost logo

Boost Users :

Subject: Re: [Boost-users] Identify cycles in a undirected graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-02-08 13:17:18

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 gives the algorithm
and why it works in more detail.

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at