Modify

Opened 5 years ago

Closed 5 years ago

#7226 closed Bugs (fixed)

relax() in relax.hpp can return false even if predecessor map is changed

Reported by: Alex Hagen-Zanker <ahh34@…> Owned by: jewillco
Milestone: To Be Determined Component: graph
Version: Boost 1.51.0 Severity: Problem
Keywords: relax, floating point precision Cc:

Description

The relax function in relax.hpp checks whether the distance of an edge really is reduced after relaxation and only returns true if that is the case. (the alternative possibility is that the expected reduction in distance does not take place due to floating point precision).

However, the function updates the predecessor map in any case. It is therefore possible that the predecessor map is changed while the relax function returns false. I suppose this is a bug, even though I did not cause me any trouble.

Attachments (1)

relax.patch (1.2 KB) - added by Alex Hagen-Zanker <ahh34@…> 5 years ago.
patch

Download all attachments as: .zip

Change History (2)

Changed 5 years ago by Alex Hagen-Zanker <ahh34@…>

patch

comment:1 Changed 5 years ago by jewillco

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

(In [80639]) Fixed relax logic to not write predecessor map unless distance was actually changed in memory (although this case will never be hit unless registers have extra precision compared to memory); fixes #7226

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.