Re: [Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-04-05 21:04:20

#11151: Bug in update method for fibonacci heap.
--------------------------------------------+--------------------------
  Reporter:  Søren Enevoldsen <senevo10@…>  |      Owner:  timblechmann
      Type:  Bugs                           |     Status:  new
 Milestone:  To Be Determined               |  Component:  heap
   Version:  Boost 1.57.0                   |   Severity:  Problem
Resolution:                                 |   Keywords:
--------------------------------------------+--------------------------

Comment (by Søren Enevoldsen <senevo10@…>):

 What makes a handle invalid? Can you not modify handles after the
 corresponding element is removed from the heap? It is the user's
 responsibility to wrap his elements, with perhaps a boolean flag, to
 detect when the elements have been removed from the heap, to avoid using a
 invalid handle. From my first case I thought this was not a problem since
 I do it there, but now I realize that due to the way dijkstra works, it
 appears I only touch "live" handles.

 If that is the case then i'm unsure how to produce a simpler case
 expressing the first actual bug. My attempts with simple cases that only
 manipulate the priority of the top node works fine. The bug seems to only
 manifest itself when there is a significant amount of data, like my 10x10
 matrix, and when the priority is changed for elements other than the
 current (top) one. Do you have any ideas on what kind of algorithmic
 problem that has these properties but is simpler to write a test case for?

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