Re: [boost] Boost Graph library - r_c_shortest_paths

Subject: Re: [boost] Boost Graph library - r_c_shortest_paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-02-22 20:32:56

On Mon, 22 Feb 2010, Andrew Sutton wrote:

> I'll leave most of the responses for Michael to address, but will try to add
> a few clarifications and comments.
>
> Fourth, and I'm hoping to get Jeremiah's input on this... I'm not a fan of
>>> passing vector<vector<>>& or vector<>& as top-level parameters. It might
>>> be
>>> better to require a template parameter that is essentially a matrix- or
>>> vector-like object. That would simplify the call interface and allow a
>>> little more freedom w.r.t. parameter types. Thoughts?
>>>
>>
>> I am not a fan of them either.  It might be better for the user to provide
>> an output iterator for each output, which the algorithm writes to.  Also,
>> what if the user does not want one of the vector outputs?  Look at
>> libs/graph/doc/mcgregor_common_subgraphs.html for one possible approach to
>> this problem; there, a user-supplied property map is updated with each
>> solution (there, a partial isomorphism between graphs) and a user function
>> is called after the solution is written.
>>
>
> It may be the case that output iterators aren't sufficient for the
> algorithm. It may need random access to the output vectors/matrices. I need
> to look at the implementation more closely at the implementation. Property
> maps may be a viable option in their place, however.

I looked at the code; the only operation done to the two vectors is 
push_back, so an iterator or callback would work.

> What is the point of a label allocator?  Do they need to be full allocators?
>>  Do labels need to be heap-allocated objects at all, or would a value class
>> make more sense (in combination with property maps to express paths)?  It
>> looks like labels may not make sense at all; perhaps there can be property
>> maps for cumulated_resource_consumption, pred_edge, and is_dominated, each
>> indexed by graph vertices?  That would likely improve performance and
>> simplify the algorithm's interface?
>>
>
> Allocators are used to allocate r_c path labels, which have
> Resource_Containers as subobjects, so I'm thinking that value types may not
> be the best solution. On the other hand... If only we had reliable move
> semantics :) I'm not sure if there's a data structure that naturally
> supports the order of construction and destruction, if you get my meaning.

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.
>
>
> I don't think the labels ever appear in the output, but I could be missing a
> parameter's intent.

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?

>> Since it is an existing BGL function, it probably does.  How different are
>> the interfaces between the two versions?
>>
>
> 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.

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)

Why not just use an iterator loop or BGL_FORALL_VERTICES_T?  The code 
would even be somewhat cleaner by just switching to size_t as the counter. 
There are other tests that seem to have static_cast<int> just to quiet 
compiler warnings; some of them (such as 
static_cast<int>(list_labels_cur_vertex.size()) >= 2) are probably 
unnecessary.  Can vec_vertex_labels, 
vec_last_valid_positions_for_dominance, 
vec_last_valid_index_for_dominance, or 
b_vec_vertex_already_checked_for_dominance be property maps instead of 
vectors?  Another style issue: using c.size() as a condition should be 
replaced by !c.empty(), as the latter is often faster (especially for 
std::list, which does not guarantee that size() takes constant time).

-- Jeremiah Willcock