Stack over flow error in the Chrobak_Payne_drawing.hpp
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=enthis 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.
Here is the piece of my code :
embedding_storage_t embedding_storage2(num_vertices(tempGraph)); embedding_t embedding2(embedding_storage2.begin(), get(vertex_index,tempGraph)); isplanar = boyer_myrvold_planarity_test(boyer_myrvold_params::graph = tempGraph, boyer_myrvold_params::embedding = &embedding2[0] ); // Find a canonical ordering typedef std::vector<graph_traits<Graph>::vertex_descriptor> ordering_storage_t; ordering_storage_t ordering;
planar_canonical_ordering(tempGraph, embedding2, std::back_inserter(ordering)); ordering_storage_t::iterator oi; for ( oi = ordering.begin();oi!=ordering.end();oi++) cout<<*oi<<endl;
//Set up a property map to hold the mapping from vertices to coord_t's typedef std::vector< planar_coord > straight_line_drawing_storage_t; typedef boost::iterator_property_map <straight_line_drawing_storage_t::iterator,property_map<Graph, vertex_index_t>::type> straight_line_drawing_t;
straight_line_drawing_storage_t straight_line_drawing_storage(num_vertices(tempGraph)); straight_line_drawing_t straight_line_drawing(straight_line_drawing_storage.begin(),get(vertex_index,tempGraph));
chrobak_payne_straight_line_drawing(tempGraph, embedding2, ordering.begin(), ordering.end(), straight_line_drawing );
Also the same code works in some cases when the size of the graphs is small, but as the size of the graph grows I am getting this stackoverflow error. Could anyone kindly letme know why this error occurs and if there is any other extra care I need to take care off ?
Thanks, Nishchal.
-- Nishchal Devanur
On Fri, May 13, 2011 at 12:47 PM, Nishchal Devnur <nishchal.devnur@gmail.com> 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
On Fri, 13 May 2011, Aaron Windsor wrote:
On Fri, May 13, 2011 at 12:47 PM, Nishchal Devnur <nishchal.devnur@gmail.com> 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
On Fri, May 13, 2011 at 7:51 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, 13 May 2011, Aaron Windsor wrote:
On Fri, May 13, 2011 at 12:47 PM, Nishchal Devnur <nishchal.devnur@gmail.com> 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
participants (3)
-
Aaron Windsor
-
Jeremiah Willcock
-
Nishchal Devnur