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@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@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.