From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-06-23 02:06:16
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