I don't know exactly what the reason for heap allocation is. If you need ordered construction and destruction, wouldn't a stack (or recursion on the execution stack) work? Is the goal to have a bunch of lists with shared tails?
If you do decide to keep label objects, the Label concept should just be a
prototype of the structure if there is only one type that is allowed to be used in that position; a concept that can only ever have one model is usually unnecessary.
They do get passed to visitors, but I do not see them going into the output either. Do labels even need numbers or any kind of unique identifier? They appear to just be information about paths and partial paths (effectively a linked list). BTW, what is the point of a priority_queue on pointers? That ordering is not generally useful for algorithms. The pseudocode in the docs shows EXTRACTMIN as well; perhaps there is some other distance metric that is intended as the comparison in the priority_queue?
I just realized that I messed up a change to the implementation by removing the smart_pointer class. It was delegating comparisons to its dereferenced object (*ptr). That priority queue should be parameterized over (minimally) indirect_less. I'll have to go through and make sure that I haven't removed any other comparisons. Somehow, the tests still passed with the ptr comparisons....
There's one less function and template parameter in the new version. I'm
pretty sure we'd break something without a new name or module.
Yes, most likely. The full name resource_constrained_shortest_paths would work, though, and fits with BGL conventions.
I like it, but I think the documentation sites an algorithm, which suggests to me that there might be others. Should we consider using the author's name in a module called resource_constrained_shortest_paths.hpp?
One other issue I saw is that there are a bunch of loops like:
for(int i = 0; i < static_cast<int>(num_vertices(g)); ++i)
I had planned to address these in a later pass. I'll go thru and and back out the smart pointer change (sort of) and start taking a closer looks at static_casts. Andrew Sutton andrew.n.sutton@gmail.com