[boost] [BGL] Yet another patch for nonrecursive DFS

From: Bruce Barr (schmoost_at_[hidden])
Date: 2003-06-22 15:52:37

I'm glad Vladimir got me to take another look at this.
 I'm submitting a new patch to replace the one
submitted on May 30.

There are a few things that could have been done
better.

1) There's no reason to move the construction of v and
v_color out of the loop.

2) The order of execution between
vis.discover_vertex(u, g) and out_edges(u, g) changed.
 What if discover_vertex() changed the value of u?  I
corrected the call order, so the result should be
identically weird.

3) The calls to make_pair() should be qualified with
std::.

There are other differences between the recursive and
nonrecursive versions that, in my opinion, are good or
necessary.

1) The objects color, u, ei, and ei_end are only
created/destroyed once instead of at every level of
recursion.

2) The overall number of constructions/destructions
for types Vertex and Iter is different.  It's possible
for client code to depend on something like that, but
I think trying to support that sort of code is going
overboard.

Here are some pseudo-FAQ's to explain some other
details.

Q) Why is the statement
'stack.reserve(num_vertices(g));' commented out?

A) Because premature optimization is bad.  Anyway,
only the library user could know what the ideal
capacity of the stack vector is.  num_vertices(g)
might be way too high.  Maybe the argument for reserve
could be passed in as a parameter someday.

Q) Why use nested pairs for VertexInfo instead of
tuples?

A) Only because out_edges() returns a pair.  Tuples
probably would have been just as good.

Q) Why are the vertex descriptor and the out-edge
iterators pushed on the stack, then immediately popped
back off in the loop?

A) It's actually simpler that way.  Robert Sedgewick
describes something very similar for nonrecursive tree
traversal in "Algorithms in C++", 1992, in the chapter
on recursion.  It is possible to avoid the initial
push and pop, but the code for that is even more
awkward.

Q) Why does the nonrecursive version use 'while (ei !=
ei_end)' when the recursive version uses a for loop?

A) If the nonrecursive version incremented ei in the
header of a for loop instead of in the body of the
while loop, the first out-edge of every new (white)
adjacent vertex would be skipped.  There are some
comments in the code that explain this loop a little
more.

Q) Why is ei incremented just before it is pushed on
the stack in the while loop?

A) If it wasn't, the same out-edge would be
incorrectly reexamined after that value of ei was
popped back off the stack.

Q) What if one of the event point functions changes
its vertex or edge argument?

A) Now that the call order between discover_vertex()
and out_edges() is corrected, the results should be
identically weird.

Q) Why did you change your email address?

A) The spam filter was throwing out good email.  If
you sent me something and got no response, give it
another shot with the new address.

__________________________________
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!
http://sbc.yahoo.com