Re: [Boost-users] Stack over flow error in the Chrobak_Payne_drawing.hpp

Subject: Re: [Boost-users] Stack over flow error in the Chrobak_Payne_drawing.hpp
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2011-05-14 09:51:59

On Fri, May 13, 2011 at 7:51 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Fri, 13 May 2011, Aaron Windsor wrote:
>
>> On Fri, May 13, 2011 at 12:47 PM, Nishchal Devnur
>> <nishchal.devnur_at_[hidden]> wrote:
>>>
>>>> Hi All,
>>>>
>>>> I am trying to use the Chrobak_Payne_straight_line_drawing function to
>>>> get
>>>> a straight line drawing of a biconnected and maximally planar graph. But
>>>> I
>>>> am getting a stackoverflow error in the the Chrobak_Payne_drawing.hpp
>>>> file.
>>>>
>>>> https://docs.google.com/leaf?id=0B4H5FyR7-PhTYTg1ZmFjNDctNmE1ZC00NzYyLWIwM2UtZDljMTQyMzM2MGFh&hl=en
>>>> this is the link to the  screenshot of the stacktrace. The
>>>> accumulate_offset
>>>> in the hpp file is being recursively called and hence the stackoverflow.
>>>> I
>>>> am not sure whats the cause of this error.
>>
>> <snip>
>>
>> Hi Nishchal,
>>
>> It looks like that function (accumulate_offsets) is written
>> recursively, so unfortunately with a large enough graph you will get a
>> stack overflow. But it's a really simple function, I'd recommend
>> re-writing it to use an explicit stack - so instead of:
>
> (snip)
>
> I did the kind of changes that you suggested and checked them into the Boost
> trunk (r71929).  Could you (Aaron and/or Nishchal) please check whether it
> works for you?
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

Hi Jeremiah,

I just tested it out and it looks great - thanks for putting the
change in (and fixing the initial offset bug in the code I originally
suggested!) The test in all_planar_input_files_test.cpp exercises
pretty much all of the code in the BGL associated with planar graphs,
so in general any modification of any of the planar graph code that
keeps that test passing is okay.

-Aaron