Boost logo

Boost Users :

Subject: [Boost-users] question regarding Depth First Search algorithm
From: Pablo Fleurquin (pablofleurquin_at_[hidden])
Date: 2011-09-28 06:43:49


Hi,

My name is Pablo Fleurquin.I am a student of M.Sc in Physics at the UIB
(Palma de Mallorca, Spain) and I'm also working in the IFISC institute
(Institute for Interdisciplinary Science and Complex Systems).

I have a question regarding the Depth First Search algorithm. Ihave
beenlooking at the Boost library page but I'm a newbie with this stuff.

*Having a directed graph G (that could be a connected graph or not), I
want my program to find the cycles within the graph and remove all the
edges that are part of them. It doesn't matter which cycle is erased
first as long as the result is the graph G without edge that formely
were part of a cycle (in other words, the remaining edges are those that
doesn´t form cycles) [attached is example1]*

Intuitively, I am sure that using the depth_first_search() function and
recalling it recursively for each "new" graph G "with less" cycles will
finally arrive to graph G with no cycles.
The problem is that I have the idea, but my knowledge of c++ is not so
vast to implement this code.

I would be gratefully, if you could show me a code for this
implementation or a function that does that.

Thank you.
Pablo Fleurquin

P.S: Example 2 is a situation that might happen. If the code can be
implemented to eliminate these 2 cycles that share a link it would be
greate, if not it will work fine as well.






Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net