Re: [boost] Boost Graph library - r_c_shortest_paths

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
> 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_at_[hidden]