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