Michael Drexl said: (by the date of Tue, 26 Sep 2006 18:08:00 +0200)

Hi,

quite some time ago, on the 6th of December last year, I posted a mail to this group asking whether there was any interest in a code for solving the shortest path problem with resource constraints (SPPRC) to be added to the Boost Graph library.

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

during that time IIRC the download counter has been reset at least twice due to some server problems.

However, I have not received any feedback whatsoever since then, no "great code, we'll put it in the next BGL release", no "well, er, you ought to change this and that and maybe it's not good/fast/generic enough anyway", not even a "this is cr.., find yourself a different hobby".

Incidentally I've been reading BGL docs yesterday and I find it as a very good and interesting library. I started looking at it because I wanted to simulate a toy neural network with it (the non-layered variant with memory etc, so vectors and matrices wouldn't work). But after investigating BGL I'm considering using it in my current project: yade. That's because interactions (between elements) in yade are stored in a similar data structure that BGL offers. And BGL's data structure is much more mature. This is very tempting, although I haven't decided yet. Perhaps a simple try the code and benchmark it will answer that :> Above it was a bit off-topic, but I just wanted to underline the fact that extending BGL with new algorithms is better than not. Maybe you should just mail directly to the library authors? -- Janek Kozicki |

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