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: John Lilley (john.lilley_at_[hidden])
Date: 2013-02-20 12:12:34

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]<mailto: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

_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]<mailto:Boost-users_at_[hidden]>
http://lists.boost.org/mailman/listinfo.cgi/boost-users