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

Subject: [Boost-users] Directed cycle detection in a DAG between two nodes
From: Amanullah Yasin (amanyasin_at_[hidden])
Date: 2013-02-20 05:20:01

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