On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
is there any interest in including an algorithm for solving the shortest path problem with resource constraints (SPPRC) in the Boost Graph library?
Yes!
I've implemented an exact algorithm for this NP-hard problem. The algorithm is basically a label-setting algorithm based on dynamic programming. It is parameterized on the graph type (of course) and the type of the resource container (data structures specifying what resources there are and how they are to be managed in the course of the algorithm).
Interesting. We're always interested in growing the BGL with new and interesting algorithms. When you think your implementation is ready to go into Boost, please send it to the list or to me privately. We usually go through a quick round of review (or two) to make sure it fits well with the BGL style, then it'll go in the next release. I'm looking forward to seeing this algortihm! Cheers, Doug