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
>> 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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk