Re: [Boost][BGL] "is_straight_line_drawing()" is buggy for large graphs

From: hermann_at_[hidden]
Date: 2024-10-04 18:08:19

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_at_7950x:~$ NOSTAT=1 randomgraph 1000000 -o t.u -s 745734
hermann_at_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_at_7950x:~$ cat intersect.txt
b
1295644 587425
709884 1658
709885 1659
1295644 587425
hermann_at_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.