Re: [boost] [Graph] New algorithms on graph_devel_1_33_0 branch

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-10-16 18:06:07

On Oct 16, 2004, at 3:45 AM, Vladimir Prus wrote:

> On Friday 15 October 2004 19:13, Doug Gregor wrote:
>> I've just checked in some new graph algorithms that have been
>> contributed to the BGL. They're on the branch graph_devel_1_33_0 until
>> we've branched off the 1.32.0 release, at which point they will go 
>> into
>> the trunk.
>
> What's the point of the branch? If the algorithms are merged now, will 
> that
> change any existing code, possibly leading to problems?

There are also some changes to Bellman-Ford suggested by the authors of 
the Floyd-Warshall algorithm. They aren't big changes (just fixing the 
addition/subtraction when one of the values is infinity), but they 
could upset something and it's way too late to make sure changes. Even 
new algorithms would need to be stabilized for all platforms, and I 
just don't think we can do it that fast.

> On a related note, do you have an opinion about my dag_shortest_paths 
> patch?
> I'd like to commit the change to the trunk the next week.

Sorry, I was waiting to review the patch until after the release, but 
I've looked at it now.

The changes to dag_shortest_paths and the addition of the new 
depth_first_visitor overload both look fine. Go ahead and check those 
into the branch, please, or wait until the release branch has been made 
and I merge everything back into the trunk.

For the suggested change to closed_plus, I don't think we can assume 
that std::numeric_limits<T>::max() is always the value of infinity (in 
fact, I'd much rather it *not* be infinity for types that have an 
actual value for infinity, but that's for another day). So for this 
issue, I prefer to use the solution that's on the branch: see the uses 
of inf_combine in Bellman-Ford, because I think it does exactly what 
dag_shortest_paths will need.

        Doug