Bug in update method for fibonacci heap.

[Søren Enevoldsen <senevo10@…>]

There appears to be a bug in the update method for handles in the fibonacci heap. Calling update with a handle is supposed to rearrange the corresponding element in the heap. However, it does not properly increase the priority in the fibonacci heap. The pairing heap does not suffer from this problem.

The following example shows the problem. I made my original problem as minimal as possible. I was unable to create a smaller example from scratch. The example finds the minimum path from the topleft (0,0) of a matrix to the bottom right, using djikstra's algorithm.

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

using namespace boost::heap;

struct VertexRef;

struct Position {
	int x;
	int y;
	explicit Position(int ax, int ay) : x(ax), y(ay) {};
};

struct Vertex {
	int cost;
	int dist;
	Position position;
	fibonacci_heap<VertexRef>::handle_type handle;
	explicit Vertex(Position pos, int c) : 
		cost{c}, position{pos} {};
};

struct MatrixGrid {
	explicit MatrixGrid(int w, int h) : m_width{w}, m_height{h} {
		unsigned int size = w * h;
		this->vertices.reserve(size);
	}

	void putVertex(const Vertex& vertex) {
		this->vertices[indexForPos(vertex.position)] = vertex;
	}

	Vertex& getVertex(Position pos) {
		return this->vertices[indexForPos(pos)];
	}

	template<typename Func>
	void withNeighbours(Vertex& vertex, Func f) {
		Position pos(vertex.position);
		if (pos.x > 0) f(getVertex(Position(pos.x-1, pos.y)));
		if (pos.y > 0) f(getVertex(Position(pos.x, pos.y-1)));
		if (pos.x < m_width-1) f(getVertex(Position(pos.x+1, pos.y)));
		if (pos.y < m_height-1) f(getVertex(Position(pos.x, pos.y+1)));
	}

	int width() const {
		return m_width;
	}

	int height() const {
		return m_height;
	}

private:
	int m_width;
	int m_height;
	std::vector<Vertex> vertices{};

	unsigned int indexForPos(const Position& pos) {
		assert(pos.x < m_width && pos.y < m_height && pos.x >= 0 && pos.y >= 0);
		return pos.y * m_width + pos.x;
	}
};

struct VertexRef
{
	Vertex& vertex;
	bool operator<(const VertexRef& rhs) const {
		return vertex.dist > rhs.vertex.dist;
	}
	VertexRef(Vertex& aVertex) : vertex(aVertex) {}
};

MatrixGrid get_predictable_matrix(int width, int height) {
	auto grid = MatrixGrid(width, height);
	for (int y=0; y < height; ++y) {
		for (int x=0; x < width; ++x) {
			Position pos(x, y);
			grid.putVertex(Vertex(pos, y*width+x));
		}
	}
	return grid;
}

void run_dijkstra(MatrixGrid& grid, const Position& startPosition) {
	auto queue = fibonacci_heap<VertexRef>();
	int maxDist = std::numeric_limits<int>::max();
	//Set initial node properly
	{
		for (int y=0; y < grid.height(); ++y) {
			for (int x=0; x < grid.width(); x++) {
				auto& vertex = grid.getVertex(Position(x, y));
				if (x == startPosition.x && y == startPosition.y) {
					vertex.dist = vertex.cost;
				} else {
					vertex.dist = maxDist;
				}
				auto handle = queue.push(vertex);
				vertex.handle = handle;
			}
		}
	}

	while (!queue.empty()) {
		auto& current = queue.top().vertex;

		auto checkNeighbour = [&queue, &current](Vertex& neighbour) {
			//dist is max int.. Can overflow
			int64_t candidateDist = static_cast<int64_t>(current.dist) + static_cast<int64_t>(neighbour.cost);
			if (candidateDist < static_cast<int64_t>(neighbour.dist)) {
				neighbour.dist = candidateDist;
				queue.increase(neighbour.handle);
			}
		};
		grid.withNeighbours(current, checkNeighbour);
		queue.pop();
	}
}

int main(int argc, char const *argv[])
{
	auto grid = get_predictable_matrix(10, 10);
	Position start(0, 0);
	Position end(9, 9);

	run_dijkstra(grid, start);

	std::cout << "Final Dist: " << grid.getVertex(end).dist << std::endl;
	/*
		Fibonacci(increase) = 576
		Fibonacci(update) = 585

		Pairing(increase) = 576
		Pairing(update) = 576
	*/
	return 0;
}

Using a pairing heap for the program, the answer is correct regardless whether using increase or update in djikstra method. However, by using fibonacci heap, only the increase call is correct. Update acts the same as if decrease or not calling it at all.

[timblechmann]

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

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

[timblechmann]

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

[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?

[timblechmann]

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.