Directed cycle detection in a DAG between two nodes
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
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@gmail.com>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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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@lists.boost.org] On Behalf Of Michael Powell Sent: Wednesday, February 20, 2013 5:41 AM To: boost-users@lists.boost.org 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@gmail.com<mailto:amanyasin@gmail.com>> 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@lists.boost.org<mailto:Boost-users@lists.boost.org> http://lists.boost.org/mailman/listinfo.cgi/boost-users
2013/2/20 John Lilley <john.lilley@redpoint.net>
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@lists.boost.org] *On Behalf Of *Michael Powell *Sent:* Wednesday, February 20, 2013 5:41 AM *To:* boost-users@lists.boost.org *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@gmail.com> 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
participants (1)
-
Alain Leblanc -
Amanullah Yasin -
John Lilley -
Michael Powell