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 20:03:47

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.

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.

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.

> 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.

Andrew Sutton
andrew.n.sutton_at_[hidden]