I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct

[a.santini@…]

The documentation for 1.58.0 (http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/r_c_shortest_paths.html) correctly states that:

The implementation is a label-setting algorithm. This means that there must be one or more resources whose cumulated consumption(s) after extension is/are always at least as high as before. This is similar to the Dijkstra algorithm for the SPP without resource constraints where the distance measure must be non-negative. It is sufficient if there is one resource with a non-negative resource consumption along all arcs (for example, non-negative arc lengths or non-negative arc traversal times).

But, later on, it says:

If ref models the ResourceExtensionFunction concept, and if the type Resource_Container models the ResourceContainer concept, after the call

ref( const Graph& g,

Resource_Container& new_cont, const Resource_Container& old_cont, graph_traits<Graph>::edge_descriptor )

the expression old_cont <= new_cont evaluates to true.

This is because, as stated above, the implementation is a label-setting algorithm. Therefore, the Less-Than operator for ResourceContainer must compare one or more resource(s) whose resource consumption(s) along any arc is/are non-decreasing in order for the algorithm to work properly.

Now, saying that "old_cont <= new_cont" is much stricter than it should be. The correct requirement (first quote) is that there is at least one resource whose consumption monotonically doesn't decrease. What "old_cont <= new_cont" requires, is that all resources' consumptions are monotonically non-decreasing. These two things are equivalent iff the label only has one resource.

Also, can someone confirm my first impression (after looking at r_c_shorterst_paths.hpp) that this invariant is mentioned in the documentation, but never checked nor assert-ed in the code?