[Graph] New algorithms on graph_devel_1_33_0 branch
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. The interesting algorithms are: - A* search, from Kristopher Beevers and Jufeng Peng - Floyd-Warshall all-pairs shortest paths, from Lauren Foutz and Scott Hill - Fruchterman-Reingold force-directed layout, from Doug Gregor The first two algorithms came out of David Musser's Generic Programming class at RPI. Consider that a challenge for any one else teaching courses in Generic Programming now or in the future: you know who you are :) I'll also be moving (sequential) code from the Parallel BGL project into CVS as soon as it becomes ready, and will batch up messages to list announcing the additions. All of the code has been written or reviewed by me, so you know where to direct comments and complaints :) Doug
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? 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. - Volodya
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
participants (2)
-
Doug Gregor -
Vladimir Prus