From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-09-29 17:27:59
On Sep 26, 2006, at 12:08 PM, Michael Drexl wrote:
> I promptly received two positive responses, so on the 27th of
> I put the code in the Boost File Vault (Home/Algorithms/Graph). Up to
> now, there have been 89 downloads (as the site indicates).
I've just finished reviewing this implementation, and it looks great.
Few minor changes I believe it is ready to go into Boost 1.35.0. My
comments follow. It looks like a long list, but everything here is
I'm also attaching an updated version of the source files, where I
fixed a few minor bits that were triggering errors in GCC 4.0.0,
which is much more picky about C++ syntax than MSVC 7.1.
- Could we rename "espprc" to something more meaningful? Like
- The Vertex_Num_Map vertex_num_map is usually called the
VertexIndexMap in the BGL (for consistency). We should do the same
for Arc_Num_map (EdgeIndexMap).
- "o" and "d" are often "s" (source) and "t" (target) in the BGL
(but it doesn't matter that much).
- I'm unfamiliar with "pareto" in "pareto_optimal_solutions". Should
there be a one-sentence explanation in the documentation?
- The boolean parameter b_all_pareto_optimal_solutions tells whether
we're emitting one result or all results. If we're only emitting
one result, couldn't we just pass references to the vector of edge
descriptors (for the path) and to the resource container?
What I'm getting at is that I think it would be better to
eliminate the b_all_pareto_optimal_solutions parameter, and
instead provide two overloads of espprc:
+ The overload that returns a single solution:
essprc(..., vector<edge_descriptor>& pareto_optimal_solution,
+ The overload that returns all solutions looks like the current
essprc, but without the b_all_pareto_optimal_solutions.
This way, the user doesn't need to create a vector of vectors that
could hold all solutions unless she actually wants to receive all
- With the Label_Allocator, we could allow the user to provide any
allocator (for any value type), then rebind it to
espprc_label<Graph, ResourceContainer>; it would make the
interface a little simpler.
- The DominanceFunction concept is a refinement of the
BinaryPredicate concept (on resource containers), with some added
invariants. It might be easier for users reading through the
parameter list if "dominance" we just a BinaryPredicate with extra
semantics stated inside the description of the parameter.
- I was a little surprised to see "Default" in the concept name
"DefaultESPPRCVisitor". Perhaps the name should just be
"ESPPRCVisitor" or, since prefer longer names to acronyms,
- check_path will either need some tests (I fixed a few minor
compilation bugs in the template definition, probably due to
Boostification of the source) or should be removed.
- Everything will need to be under the Boost Software License before
we can integrate the code into CVS.
- The examples look good. Could you make a standalone test file that
runs the algorithm on a known problem and checks correctness of
the output? This is important for our regression-testing system.
- The default arguments for, e.g., Visitor and Label_Allocator won't
help much, because they'll only work when the user explicitly
specifies template arguments for espprc. The way we usually
approach this issue is to provide multiple overloads of the
algorithm, each of which takes a different number of
arguments. This would help because some parameters (especially the
allocator and visitor) won't be overridden all that often.
- As you know, we'll need to have the documentation in HTML to add
your implementation into Boost.
- Should the "ref" and "dominance" parameters be const references
instead of non-const references?
- I think the allocator should be passed by-value or as a const
reference, not by non-const reference.
- Why do we need the ks_smart_pointer class? It's a thin wrapper
over a pointer that doesn't really add any functionality, and it
comes from something that probably doesn't have a Boost-compatible
license... I suggest making it a raw (non-const) pointer.
This will be a great algorithm to include in the BGL. Thank you!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk