[boost] [BGL] Patch for nonrecursive DFS to fix stack overflow

From: B B (dude66_at_[hidden])
Date: 2003-05-30 11:52:45

Here's a patch to depth_first_search.hpp in BGL in version 1.30.0 of boost 
that implements nonrecursive depth first search.  This reduces or eliminates 
the problem of stack overflow that occurs with DFS in large graphs.  There 
also may be a performance gain in some cases.  If anyone has a test suite 
for BGL I'd love to hear the results.  Otherwise, it works exactly the same. 
  The event points
are all the same.

Define the macro BOOST_NONRECURSIVE_DFS in your project to use the 
nonrecursive implementation.  If it is left undefined the orginal recursive 
code will remain in effect.

Some of the details could have been done a little differently. std::stack 
could have been used in place of std::vector.  Instead of storing ei_end on 
the stack, it could have been recalculated using the Vertex value.  But 
saving ei and ei_end together as a pair seemed more straightforward.

Bruce

_________________________________________________________________
Help STOP SPAM with the new MSN 8 and get 2 months FREE*  
http://join.msn.com/?page=features/junkmail