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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
