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.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:18 UTC