Boost C++ Libraries: Ticket #11735: A* Out of Range Error on 2D grid if width or height is 1

attachment set

willi+boost@… — Sat, 17 Oct 2015 20:39:08 GMT

attachment → main.cpp

test case triggering the bug

willi+boost@… — Sat, 17 Oct 2015 20:40:35 GMT

Similar test case also on http://melpon.org/wandbox/permlink/sBTZXMRmPWxVezKy

anonymous — Wed, 21 Feb 2018 16:33:26 GMT

A much simpler way to trigger the bug is the following:

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/graph_traits.hpp>
int main ()
{
  using graph_type = boost::grid_graph<2>;
  using graph_traits = boost::graph_traits<graph_type>;
  using vertex_descriptor = typename graph_traits::vertex_descriptor;
  graph_type graph {vertex_descriptor{2,1}};
  assert(num_vertices(graph) == 2);
  assert(num_edges(graph) == 2);
  assert(out_degree(vertex_descriptor{0,0},graph) == 1);
  assert(in_degree(vertex_descriptor{0,0},graph) == 1);
}

grid_graph calculates the number of vertices and edges correctly, but gets the {in|out}_degree (and hence {in|out}_edge_iterators) wrong. There is no reason this should be a restriction, as the fix is trivial:

--- grid_graph.hpp.orig	2017-01-07 11:43:21.000000000 -0700
+++ grid_graph.hpp	2018-02-21 08:48:37.000000000 -0700
@@ -633,7 +633,7 @@
         // wraps or not.
         if ((vertex[dimension_index] == 0) ||
             (vertex[dimension_index] == (length(dimension_index) - 1))) {
-          out_edge_count += (wrapped(dimension_index) ? 2 : 1);
+          out_edge_count += length(dimension_index) == 1 ? 0 : (wrapped(dimension_index) ? 2 : 1);
         }
         else {
           // Next and previous edges, regardless or wrapping

Yes, there may be some runtime cases with wrapping where lengths of 1 make no sense, but that is a misuse of the library by the user. The library should not enforce artificial restrictions that limits legitimate use cases like run-time specified 2x1 grids.

brook@… — Thu, 22 Feb 2018 14:31:45 GMT

An even better patch might be the following. Note that I did not reindent the original code to emphasize the substantive change.

--- boost/graph/grid_graph.hpp.orig	2017-01-07 11:43:21.000000000 -0700
+++ boost/graph/grid_graph.hpp	2018-02-22 07:20:18.000000000 -0700
@@ -630,7 +630,8 @@
         // If the vertex is on the edge of this dimension, then its
         // number of out edges is dependent upon whether the dimension
-        // wraps or not.
+        // wraps or not, but only if the length is > 1.
+	if (length(dimension_index) > 1) {
         if ((vertex[dimension_index] == 0) ||
             (vertex[dimension_index] == (length(dimension_index) - 1))) {
           out_edge_count += (wrapped(dimension_index) ? 2 : 1);
@@ -639,6 +640,7 @@
           // Next and previous edges, regardless or wrapping
           out_edge_count += 2;
         }
+	}
       }
       return (out_edge_count);