Subject: [Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-03-29 19:31:42
#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
Keywords: |
-------------------------------------------+--------------------------
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, ¤t](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.
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/11151> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:18 UTC