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