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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-06-21 00:20:33

Bruce Barr wrote:
> 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.

Just like Doug,
I think this patch is desirable. But I also think that a little bit of 
additional work is required from Bruce ;-)

At least for me, the algorithm is not 100% clear. When I first say the

  while(ei != ee) {
  }

loop, I though "huh, iteration over all out-edges?" and when I saw:

   vis.finish_vertex(u, g);

I though, "huh, we're only pushed adjacent vertices to stack, why do we call 
finish_vertex". Both problems arise from the fact that ei and u are modified 
in case adjacent vertex is white. I think to avoid confusion in future, 
comment describing what's going on is in order.

- Volodya