Boost C++ Libraries: Ticket #11151: Bug in update method for fibonacci heap.

timblechmann — Sun, 05 Apr 2015 00:23:47 GMT

i can see the same result, but would need a test case which is easier to debug. would you be able to provide one? thnx

Sun, 05 Apr 2015 17:27:40 GMT

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;
}

timblechmann — Sun, 05 Apr 2015 20:39:15 GMT

the second one is a user bug: you are modifying an invalid handle

Sun, 05 Apr 2015 21:04:20 GMT

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?

status changed; resolution set

timblechmann — Sun, 05 Apr 2015 21:41:21 GMT

status new → closed
resolution → fixed

a handle will be invalidated once the object has been removed (pop()) from the heap, as some internal data structures are destroyed.

fwiw, i've been able to fix the issue.