Identify cycles in a undirected graph
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 ? Thanks by advance
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
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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, Feb 10, 2012 at 2:45 AM, NsPx <nspx.roronoa@gmail.com> wrote:
Thanks a lot Jeremiah, it works as expected !
NsPx, Detecting cycles, and identifying the vertices in cycles is a perfect size problem for an example! It would be a great service to future users if you would post a compilable example of doing these things here: http://programmingexamples.net/wiki/Boost/BGL Slowly these examples are getting cleaned up and moved into the Boost repository. Thanks! David
David Doria <daviddoria <at> gmail.com> writes:
Thanks a lot Jeremiah, it works as expected !
Detecting cycles, and identifying the vertices in cycles is a perfect size problem for an example!
Hello all - did anyone come up with an example that uses both vertex visitors and predecessor_recorder? I'm having a hard time getting that wired up. This seems like it would be a common need, I would love to see it in the docs or wiki.
participants (1)
-
David Doria -
Jeremiah Willcock -
Michael Behrns-Miller -
NsPx