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
#include
int main() {
boost::adjacency_list
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 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.
