Re: [Boost-users] Directed cycle detection in a DAG between two nodes

Subject: Re: [Boost-users] Directed cycle detection in a DAG between two nodes
From: Alain Leblanc (aalebl_at_[hidden])
Date: 2013-02-20 12:34:02

2013/2/20 John Lilley <john.lilley_at_[hidden]>

>  Check out Floyd’s algorithm (http://en.wikipedia.org/wiki/Cycle_detection)
> for a clever approach.  ****
>
> Basically you walk this algorithm starting with each node in turn.  ****
>
> It requires no extra storage, but it will be faster if you track
> already-visited nodes and skip them later.****
>
> If you can make your algorithm intrusive, adding a “bool visited” member
> to your nodes removes the need for an external set.****
>
> john****
>
> ** **
>
> *From:* Boost-users [mailto:boost-users-bounces_at_[hidden]] *On
> Behalf Of *Michael Powell
> *Sent:* Wednesday, February 20, 2013 5:41 AM
> *To:* boost-users_at_[hidden]
> *Subject:* Re: [Boost-users] Directed cycle detection in a DAG between
> two nodes****
>
> ** **
>
> I can't speak to how your graph is wired up, but it seems to me that
> somehow you need to keep track of nodes visited, more than simply nodeInit
> (possibly).
>
> I didn't do this in C++ boost, per se, but I have done something similar
> in C# .NET using PowerCollections Graph. I had different node traversals
> analyzing volumetric flow (pipes, substance, etc) through different
> connectors (valves, and such), and needed to analyze communication between
> volumes.
>
> Enter graph traversal. I ended up keeping track of nodes visited to detect
> my terminal case. Very fast, very clean, if a little inefficient because of
> the overhead needing a collection (list, C++ STL vector if you will). You
> pass in a new vector<> and could be the same one throughout the recursive
> call.
>
> Worked like a charm.
>
> Good hunting!
>
> Regards,
>
> Michael****
>
> On Wed, Feb 20, 2013 at 4:20 AM, Amanullah Yasin <amanyasin_at_[hidden]>
> wrote:****
>
> Hi,****
>
> In Hill Climbing algorithm, before applying an operation "add_edge",
> "reverse_edge" or "remove_edge", I need to check whether the graph will be
> a Directed Acyclic Graph (DAG) or not. So there is recursive function but
> in some cases it goes in infinite loop and gives "stack overflow" error.**
> **
>
> //======= Function =======
> bool myAlgo::remainsADAG(const Node_type& nodeInit, const Node_type&
> node,  const Graph_type& graph)****
>
> {
>   graph_traits<Graph_type>::adjacency_iterator vi, vi_end;
>   tie(vi, vi_end) = adjacent_vertices(node, graph);
>
>   for (; vi != vi_end; ++vi) {
>     if ((*vi == nodeInit) || (!remainsADAG(nodeInit, *vi, graph)))
>       return false;
>   }
>   return true;
> }
> ==============****
>
> e.g. for Graph ****
>
> 12->19->20->23
> 19->24->31->18>19
> 18->32
>
> To test if there is a directed path between v12 and v32****
>
> it goes as:****
>
> 12->19->20->23 ****
>
> 24->31->18>19****
>
> *There is an infinite loop{18->19->20->23, 24->31->18}.*
> =================****
>
> Can some one help me or is there any other easy way to find a directed
> path between two nodes in boost graph?****
>
> Thanks in advance.****
>
> YASIN****
>
>
> Why not just use the boost topological_sort function on your graph. It
will fail if there is a cycle. In that case, catch the exception and then
use the boost depth_first_search function to identify the cycle. I can send
you a code sample if it helps.

a