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

From: hermann_at_[hidden]
Date: 2024-10-05 10:17:42

On 2024-10-05 02:10, Seth wrote:
> All assert in 3.8s for me
> 
> ./deps/randomgraph/randomgraph 75000 -t maximal_planar -o tmp.u -s 
> 2302401110
> ./deps/randomgraph/randomgraph 75000 -t maximal_planar -o tmp.u -s 
> 481485811
> ./deps/randomgraph/randomgraph 75000 -t maximal_planar -o tmp.u -s 
> 2791097217
> 
> Assert in 2.9s
> 
Your 25000 vertices randomgraphs did not assert on my 64bit AMD Ubuntu 
22.04.
But your 75000 vertices randomgraphs do.

I took the middle one and used its intersection coordinates in the
minimal C++ code you provided in:
https://github.com/boostorg/graph/issues/388#issuecomment-2394869835

hermann_at_7950x:~$ cat sehe.min.cpp
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/is_straight_line_drawing.hpp>

int main() {
     boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> 
g;
     add_edge(0, 1, g);
     add_edge(2, 0, g);
     add_edge(1, 2, g);

     struct coord_t { size_t x, y; };
     std::vector<coord_t> coordinates{{78821, 71094}, {147961, 1953}, 
{147962, 1952}};
     assert(is_straight_line_drawing(g, coordinates.data())); // FAILS
}
hermann_at_7950x:~$

This incorrectly asserts as well — but the coordinates show that the
"is_straight_line_drawing()" bug is real for "small" number of vertices
and small coordinate values:

dx01=78821-147961=-69140
dy01=71094-1953=69141

dx20=78821-147962=-69141
dy20=71094-1952=69142

So edges have vertex (78821, 71094) in common, but have different
slopes 69141/-69140 and 69142/-69141, and assert proves the bug.

Regards,

Hermann.