Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at