id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
11300,I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct,a.santini@…,Jeremiah Willcock,"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?",Bugs,new,To Be Determined,graph,Boost 1.58.0,Not Applicable,,"bgl,graph",jewillco@…