Re: [boost] Shortest Path Problem with Resource Constraints

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-09-29 17:27:59

Hello Michael,

On Sep 26, 2006, at 12:08 PM, Michael Drexl wrote:
> I promptly received two positive responses, so on the 27th of  
> December,
> 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  
very minor.

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
     "resource_constrained_shortest_paths"?

   - 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,
                  Resource_Container pareto_optimal_resource_container,
                  ...)

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

   - 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,
     "ResourceConstrainedShortestPathsVisitor"?
   - 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!

        Cheers,
        Doug