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 ,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 #include #include #include 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::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 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 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(); int maxDist = std::numeric_limits::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, ¤t](Vertex& neighbour) { //dist is max int.. Can overflow int64_t candidateDist = static_cast(current.dist) + static_cast(neighbour.cost); if (candidateDist < static_cast(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,,