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

From: Seth (bugs_at_[hidden])
Date: 2024-10-04 16:06:25

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.

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.

Here's a modernized version of the code that also shows line numbers with the timing trace output. It still reproduces the same observation: https://gist.github.com/sehe/1222fda20771b857ff605a1d05d2e652

Note that with -DREDUNDANT the added assertions prove that the redundant vertex property wasn't used. Still, I'd remove it for clarity of intent.

I might be running some more tests later,
Seth

> 1)
> I want to create a BGL issue on this, is that OK?
> At least the doc does not state any limit on graph sizes:
> https://www.boost.org/doc/libs/1_86_0/libs/graph/doc/is_straight_line_drawing.html

Looks like a valid issue to me

> 2)
> I want to create a pull request with new implementation for
> "intersects()" with integer coordinates.
>
> 2 days ago I created pull requests with 7 commits ahead
> on new "planar_vertex_six_coloring()":
> https://github.com/boostorg/graph/pull/387

I'll have a look later. Note: I'm not a maintainer, but I can provide feedback/endorsement

> Do I have to wait until that pull request was decided on?
> Or can I submit separate pull request not interfering with that request 
> on my graph fork?

You can make independent PRs, but prefer to always base them on the `develop` branch directly

Seth