https://svn.boost.org/trac10/ticket/8428 <p> In the reweighting step of Johnson's algorithm, the implementation assumes that subtraction has been defined on <a class="missing wiki">DistanceMap</a>'s value type, e.g. </p> <pre class="wiki">put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b)))); </pre><p> I've thought about whether the reweighting can be done purely through combine() calls, but it seems that the correctness proof for the reweighting relies on the distance value type having subtraction (or equivalently, an inverse). </p> <p> If this algorithm indeed requires a subtraction/inverse operation on <a class="missing wiki">DistanceMap</a> value types, then for consistency it might make sense to include a named parameter for another functor, e.g. distance_subtract. </p> <p> Another, related issue: the documentation states that distance_combine is a binary function with the 1st parameter as a <a class="missing wiki">DistanceMap</a> value type, and the 2nd argument as a <a class="missing wiki">WeightMap</a> value type. However, in the following line: </p> <pre class="wiki">put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b)))); </pre><p> the distance_combine functor is being applied with the arguments in reverse order. </p> <p> (P.S. I know I've been submitting lots of reports; I really appreciate the hard work that makes BGL awesome!) </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/8428 Trac 1.4.3 Jeremiah Willcock Thu, 11 Apr 2013 17:19:42 GMT https://svn.boost.org/trac10/ticket/8428#comment:2 https://svn.boost.org/trac10/ticket/8428#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket Jeremiah Willcock Fri, 12 Apr 2013 19:54:37 GMT https://svn.boost.org/trac10/ticket/8428#comment:3 https://svn.boost.org/trac10/ticket/8428#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/83857" title="Fixed documentation to be correct; fixes #8428">[83857]</a>) Fixed documentation to be correct; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/8428" title="#8428: Bugs: BGL Johnson's algorithm has undocumented &#34;subtractability&#34; requirement ... (closed: fixed)">#8428</a> </p> Ticket