[Boost-bugs] [Boost C++ Libraries] #11300: I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct

Subject: [Boost-bugs] [Boost C++ Libraries] #11300: I think the invariant in ResourceExtensionFunction for r_c_shortest_paths is not correct
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-05-13 19:17:25

#11300: I think the invariant in ResourceExtensionFunction for r_c_shortest_paths
is not correct
------------------------------+----------------------------
 Reporter:  a.santini@…       |      Owner:  matias
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  Documentation
  Version:  Boost 1.58.0      |   Severity:  Not Applicable
 Keywords:  bgl,graph         |
------------------------------+----------------------------
 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?

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11300>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.