Re: [Boost-bugs] [Boost C++ Libraries] #11735: A* Out of Range Error on 2D grid if width or height is 1

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11735: A* Out of Range Error on 2D grid if width or height is 1
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2018-02-21 16:33:26

#11735: A* Out of Range Error on 2D grid if width or height is 1
-------------------------------+-------------------------------
  Reporter:  willi+boost@…     |      Owner:  Jeremiah Willcock
      Type:  Bugs              |     Status:  new
 Milestone:  To Be Determined  |  Component:  graph
   Version:  Boost 1.59.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+-------------------------------

Comment (by anonymous):

 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.

-- 
Ticket URL: <https://svn.boost.org/trac10/ticket/11735#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.