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.
Help STOP SPAM with the new MSN 8 and get 2 months FREE*
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk