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

On Fri, May 13, 2011 at 7:51 PM, Jeremiah Willcock wrote:

On Fri, 13 May 2011, Aaron Windsor wrote:

...

On Fri, May 13, 2011 at 12:47 PM, Nishchal Devnur 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@lists.boost.org 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