[Boost-bugs] [Boost C++ Libraries] #8428: BGL Johnson's algorithm has undocumented "subtractability" requirement on DistanceMap value type

Subject: [Boost-bugs] [Boost C++ Libraries] #8428: BGL Johnson's algorithm has undocumented "subtractability" requirement on DistanceMap value type
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-04-11 00:30:45

#8428: BGL Johnson's algorithm has undocumented "subtractability" requirement on
DistanceMap value type
---------------------------------------------------+------------------------
 Reporter:  Luis G. Torres <lgtorres42@…>          |       Owner:  jewillco
     Type:  Bugs                                   |      Status:  new     
Milestone:  To Be Determined                       |   Component:  graph   
  Version:  Boost 1.53.0                           |    Severity:  Problem 
 Keywords:  BGL, johnson, apsp                     |  
---------------------------------------------------+------------------------
 In the reweighting step of Johnson's algorithm, the implementation assumes
 that subtraction has been defined on DistanceMap's value type, e.g.


 {{{
 put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b))));
 }}}

 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).

 If this algorithm indeed requires a subtraction/inverse operation on
 DistanceMap value types, then for consistency it might make sense to
 include a named parameter for another functor, e.g. distance_subtract.

 Another, related issue: the documentation states that distance_combine is
 a binary function with the 1st parameter as a DistanceMap value type, and
 the 2nd argument as a WeightMap value type. However, in the following
 line:

 {{{
 put(w_hat, *e, combine(get(w, *e), (get(h, a) - get(h, b))));
 }}}

 the distance_combine functor is being applied with the arguments in
 reverse order.

 (P.S. I know I've been submitting lots of reports; I really appreciate the
 hard work that makes BGL awesome!)

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