Modify

Ticket #8398 (closed Bugs: fixed)

Opened 13 months ago

Last modified 8 months ago

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

Change History

comment:1 Changed 13 months ago by jewillco

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

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

comment:2 Changed 8 months 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

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.