Subject: Re: [boost] Boost Graph library - r_c_shortest_paths
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-02-22 21:07:56
> 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
> 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
>>> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk