https://svn.boost.org/trac10/ticket/11300 <p> The documentation for 1.58.0 (<a href="http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/r_c_shortest_paths.html">http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/r_c_shortest_paths.html</a>) correctly states that: </p> <blockquote class="citation"> <p> 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). </p> </blockquote> <p> But, later on, it says: </p> <blockquote class="citation"> <p> If ref models the <a class="missing wiki">ResourceExtensionFunction</a> concept, and if the type Resource_Container models the <a class="missing wiki">ResourceContainer</a> concept, after the call </p> <p> ref( const Graph&amp; g, </p> <blockquote> <p> Resource_Container&amp; new_cont, const Resource_Container&amp; old_cont, graph_traits&lt;Graph&gt;::edge_descriptor ) </p> </blockquote> <p> the expression old_cont &lt;= new_cont evaluates to true. </p> <p> This is because, as stated above, the implementation is a label-setting algorithm. Therefore, the Less-Than operator for <a class="missing wiki">ResourceContainer</a> 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. </p> </blockquote> <p> Now, saying that "old_cont &lt;= new_cont" is much stricter than it should be. The correct requirement (first quote) is that there is <strong>at least one</strong> resource whose consumption monotonically doesn't decrease. What "old_cont &lt;= new_cont" requires, is that <strong>all</strong> resources' consumptions are monotonically non-decreasing. These two things are equivalent iff the label only has one resource. </p> <p> 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 <em>assert</em>-ed in the code? </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/11300 Trac 1.4.3 Daniel James Thu, 14 Jan 2016 00:04:12 GMT https://svn.boost.org/trac10/ticket/11300#comment:1 https://svn.boost.org/trac10/ticket/11300#comment:1 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Matias Capeletto</span> to <span class="trac-author">Jeremiah Willcock</span> </li> <li><strong>component</strong> <span class="trac-field-old">Documentation</span> → <span class="trac-field-new">graph</span> </li> </ul> Ticket