From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-06-23 02:06:16
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
> 1) The objects color, u, ei, and ei_end are only
> created/destroyed once instead of at every level of
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
> 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
> Here are some pseudo-FAQ's to explain some other
> 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
> 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk