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

This archive was generated by hypermail 2.1.7 : 2018-02-21 16:39:57 UTC
{"ft_lang_label":"__label__en","ft_lang_prob":0.65111446,"math_prob":0.78486294,"size":2315,"snap":"2023-14-2023-23","text_gpt3_token_len":633,"char_repetition_ratio":0.14798789,"word_repetition_ratio":0.083333336,"special_character_ratio":0.37537798,"punctuation_ratio":0.20873787,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9707724,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-04T20:01:34Z\",\"WARC-Record-ID\":\"<urn:uuid:acb27a11-f0d6-4e56-ae99-386e6adc03f6>\",\"Content-Length\":\"7966\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:eaefcd76-4ea8-4bd8-87e6-cd72c661a236>\",\"WARC-Concurrent-To\":\"<urn:uuid:6244f6c1-722c-44d0-9d09-ea4595051477>\",\"WARC-IP-Address\":\"146.20.110.251\",\"WARC-Target-URI\":\"https://lists.boost.org/boost-bugs/2018/02/50097.php\",\"WARC-Payload-Digest\":\"sha1:FYYD4BFA4GSKKUMSMHZFEFKYULQV2VKD\",\"WARC-Block-Digest\":\"sha1:J2RXRHYQF3CNMK3VHBH6FRP563IIMO7G\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224650264.9_warc_CC-MAIN-20230604193207-20230604223207-00307.warc.gz\"}"}