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 17:27:40

#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@…>):

 I've been unable in several attempts to reproduce the problem. There needs
 to be a lot of boilerplate to get the indirect referencing of values, such
 that other values than the current (top()) can be changed.


 I have, however, found a possible related problem, that appears when
 entries "move past each other" in priority. In this case it is possible I
 did something wrong; maybe missed some requirement for elements? The
 following example have an array of numbers. I indirectly add increasing
 values (+5 each) to the heap. The highest value, also the "rightmost",
 gets picked first. Before removing it, I increase the value to the left
 and update the heap. I tested for 4 different scenarios:

 Use Update and increment by 5: Works correct.
 Use Increase and increment by 5: Works correct.
 Use Update and increment by 15: Correct sum. But wrong reason. The entries
 in the heap have been corrupted.
 Use Increase and increment by 15: Core dump!


 {{{
 #include <iostream>
 #include <boost/heap/fibonacci_heap.hpp>
 #include <boost/heap/pairing_heap.hpp>

 using namespace boost::heap;

 struct EntryLocation;

 typedef fibonacci_heap<EntryLocation> HeapType;

 struct Entry
 {
         int num;
         HeapType::handle_type handle;
         Entry() : num(0) {}
         Entry(int number) : num(number) {}
         bool operator<(const Entry& rhs) const {
                 return num < rhs.num;
         }
 };

 struct EntryLocation {
         int index;
         std::vector<Entry>* entries;
         EntryLocation() = delete;
         EntryLocation(int i, std::vector<Entry>* e) : index(i), entries(e)
 {}
         Entry& getEntry() const {
                 return entries->at(index);
         }
         bool operator<(const EntryLocation& rhs) const {
                 return getEntry() < rhs.getEntry();
         }
 };

 int main(int argc, char const *argv[])
 {
         int size = 5;
         auto heap = HeapType();
         std::vector<Entry> entries(size);

         //Create entries
         for (int i=0; i < size; i++) {
                 entries[i] = Entry(i * 10);
                 EntryLocation location(i, &entries);
                 auto handle = heap.push(location);
                 entries[i].handle = handle;
         }

         //Do weird sum
         int sum = 0;
         while (!heap.empty()) {
                 auto& location = heap.top();
                 auto& entry = location.getEntry();
                 sum += entry.num;

                 std::cout << "Index: " << location.index << " has value: "
 << entry.num << std::endl;

                 //Modify entry to the "left"
                 if (location.index > 0) {
                         auto& leftEntry = entries[location.index - 1];
                         leftEntry.num += 5; // <<<<<<<< HERE. Try changing
 to 15.
                         heap.update(leftEntry.handle);
                 }

                 heap.pop();
         }

         std::cout << sum << std::endl;
         return 0;
 }
 }}}

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