On 2024-10-04 18:06, Seth via Boost wrote:
On Fri, Oct 4, 2024, at 3:19 PM, Hermann Stamm-Wilbrandt via Boost wrote:
assert(is_straight_line_drawing(g, straight_line_drawing)); a.out: straight_line.cpp:163: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed. Aborted (core dumped)
I was able to reproduce the assertion failure as described using https://github.com/Hermann-SW/randomgraph.
Thanks for providing the link I missed to add in my previous posting.
I noticed that you're declaring a vertex property tagged `vertex_index_t`, but your graph has an implicit `vertex_index` due to `vecS` vertex container selector.
And for pointing that out. My code was copied together from many graph/example files and I missed the implicit vertex_index. I tried to come up with a much smaller recreate. I created graph K3 and before "is_straight_line_drawing()" call I stored the coordinates reported. To my surprise this does not recreate the issue. I found another way to reduce the more than 7min recreate time on my AMD 7950X fast CPU. I created random maximal planar graph with "only" 1million vertices, with a different random seed. This time assert much faster: hermann@7950x:~$ NOSTAT=1 randomgraph 1000000 -o t.u -s 745734 hermann@7950x:~$ ./straight_line_graphviz t.u -t read_leda_graph(g, argv[1]); 0.762341 make_connected(g); 0.160589 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 7.32607 make_biconnected_planar(g, &embedding2[0]); 0.282637 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.69938 make_maximal_planar(g, &embedding2[0]); 4.52332 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.66393 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding)); 6.82302 planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 0.288155 chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); 0.324136 assert(is_straight_line_drawing(g, straight_line_drawing)); straight_line_graphviz: straight_line_graphviz.cpp:173: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed. Aborted (core dumped) hermann@7950x:~$ cat intersect.txt b 1295644 587425 709884 1658 709885 1659 1295644 587425 hermann@7950x:~$ intersect.txt shows similar issue to before, the "b" shows that "the other" of two "return false" was hit this time. Again with edges intersecting at vertex with coordinate (1295644,587425) which should not assert. Regards, Hermann.