Modify

Ticket #8428 (closed Bugs: fixed)

Opened 13 months ago

Last modified 13 months ago

BGL Johnson's algorithm has undocumented "subtractability" requirement on DistanceMap value type

Reported by: Luis G. Torres <lgtorres42@…> Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.53.0 Severity: Problem
Keywords: BGL, johnson, apsp Cc:

Description

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

Attachments

Change History

comment:1 Changed 13 months ago by jewillco

(In [83845]) Flipped arguments to combine calls to match documentation; refs #8428

comment:2 Changed 13 months ago by jewillco

  • Status changed from new to assigned

comment:3 Changed 13 months ago by jewillco

  • Status changed from assigned to closed
  • Resolution set to fixed

(In [83857]) Fixed documentation to be correct; fixes #8428

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.