[Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.

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, &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.

-- 
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.