Hi Bruce, Bruce Barr wrote: > 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.
And I'm glad you're willing to polish your patch! > 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. I think that for 'u', you might have two invocations of copy constructor: when pushing to the stack and when popping ;-) But that's not every level of recursion anyway. > 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. Agree. > 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. There's another question: why store "u" at all. I'm guessing "source(*ei, g)" might be more efficient? I'm thinking we have some technical questions left to apply your patch. 1. It needs license from you. Either the standard one: // (C) Copyright Bruce Barr, 2003 // Permission to copy, use, modify, sell and distribute this software // is granted provided this copyright notice appears in all copies. // This software is provided "as is" without express or implied // warranty, and with no claim as to its suitability for any purpose. which, I belive, is preferred, or any one you like, which meets Boost guidelines. 2. Once you decide on 1) I'll commit your patch, making nonrecursive dfs default. I plan to retain the old version for a while, because it would be desirable to compare performance. 3. Maybe, the FAQ, either fully or partically, must be added too. That's up to you, though. Thanks, Volodya _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
