
Boost Users : 
Subject: [Boostusers] [BGL] I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct
From: Alberto Maria Santini (a.santini_at_[hidden])
Date: 20150502 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 labelsetting 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 nonnegative. It is sufficient if there is one resource with a nonnegative resource consumption along all arcs (for example, nonnegative arc lengths or nonnegative 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 labelsetting algorithm. Therefore, the LessThan operator for ResourceContainer must compare one or more resource(s) whose resource consumption(s) along any arc is/are nondecreasing 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 nondecreasing. 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net