id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
11151,Bug in update method for fibonacci heap.,Søren Enevoldsen <senevo10@…>,timblechmann,"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.",Bugs,closed,To Be Determined,heap,Boost 1.57.0,Problem,fixed,,