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

From: Seth (bugs_at_[hidden])
Date: 2024-10-05 11:42:05

On Sat, Oct 5, 2024, at 12:17 PM, hermann_at_[hidden] wrote:
> Your 25000 vertices randomgraphs did not assert on my 64bit AMD Ubuntu 
> 22.04.

My bad, checking the logs I found that I had accidentally recompiled the binary during the test-run, giving me the false negative.

> I took the middle one and used its intersection coordinates in the
> minimal C++ code you provided in:
Nice!

> This incorrectly asserts as well — 
[...]
> So edges have vertex (78821, 71094) in common, but have different
> slopes 69141/-69140 and 69142/-69141, and assert proves the bug.

I think I was confused by the wording. The assert failing seemed to imply that you *expected* the predicate to return true for the given line drawing.

I think I now understand that you actually mean that you mean the assert proves a bug in the Chrobak-Paine implementation, which generates just just off-straight data due to rounding issues?

If so, never mind me, I bet everyone else involved immediately got that :)

Cheers,
Seth