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

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