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-13 13:34:06

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:

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<std::pair<graph_traits<Graph>::vertex_descriptor,
std::size_t> > accumulate_stack;
if (v != graph_traits<Graph>::null_vertex())
    accumulate_stack.push_back(std::make_pair(v, 0));

while(!accumulate_stack.empty())
{
    std::pair<graph_traits<Graph>::vertex_descriptor, std::size_t>
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