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

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: if (v != graph_traits<Graph>::null_vertex()) { x[v] += delta_x[v] + offset; accumulate_offsets(left[v], x[v], g, x, delta_x, left, right); accumulate_offsets(right[v], x[v], g, x, delta_x, left, right); } do something like: std::vector > accumulate_stack; if (v != graph_traits<Graph>::null_vertex()) accumulate_stack.push_back(std::make_pair(v, 0)); while(!accumulate_stack.empty()) { std::pair current = accumulate_stack.back(); accumulate_stack.pop_back(); x[current.first] += delta_x[current.first] + current.second; if (left[current.first] != graph_traits<Graph>::null_vertex()) accumulate_stack.push_back(std::make_pair(left[current.first], x[current.first])); if (right[current.first] != graph_traits<Graph>::null_vertex()) accumulate_stack.push_back(std::make_pair(right[current.first], x[current.first])); } should work (but that's off the top of my head, I haven't tried it.) If you get that working, please contribute it back to the chrobak payne code in the BGL! -Aaron