[Boost-users] [BGL] I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct

Subject: [Boost-users] [BGL] I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct
From: Alberto Maria Santini (a.santini_at_[hidden])
Date: 2015-05-02 08:43:46

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.

Can someone confirm that my observation makes sense? In this case, I’ll open a ticket and submit a patch for the documentation. Can someone also confirm that this check is *not* enforced in r_c_shortest_paths.hpp?

Thanks,
AS