Modify

Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#8398 closed Bugs (fixed)

dijkstra_shortest_paths implicitly requires DistanceMap and WeightMap to be the same

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

Description

The documentation for dijkstra_shortest_paths states that the given distance_compare functor needs to be a BinaryPredicate? where both arguments are of the value type of DistanceMap?. The distance_combine functor needs to be a BinaryFunction? where the first argument is of the DistanceMap? value type and the second argument is of the WeightMap? value type.

However, in line 162 of dijkstra_shortest_paths.hpp, a comparison is made between a value from WeightMap? and a value from DistanceMap? using the distance_compare functor; this violates where the documentation specifies that the distance_compare functor would only need to handle types from DistanceMap?. Effectively, this requires either:

a) the value types of WeightMap? and DistanceMap? are made the same b) the distance_compare functor overloads operator() to have two different types of comparison

I imagine that fixing this issue would require either changing the documentation or changing line 162 to not require this comparison to be made (it seems to only be a way of verifying that there are no negative edges in the graph).

Attachments (0)

Change History (2)

comment:1 Changed 4 years ago by jewillco

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

(In [83772]) Changed test for negative edges per #8398; fixes #8398

comment:2 Changed 4 years ago by jewillco

(In [85386]) Fixed test for negative-weight edges when combine operator is project2nd (as in prim_minimum_spanning_tree); fixes #9012; refs #8398

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain jewillco.
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.