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

From: hermann_at_[hidden]
Date: 2024-10-04 13:19:29

A while back I combined all BGL planarity functions
(make_"connected / biconnected_planar / maximal_planar" + 
straight_line_drawing)
prepended with "read_leda_graph()" and writing GraphViz output.
The Graphviz output uses neato engine because that allows for
fixed vertex coordinates with exclamation mark:

2 [pos="3,2!" label="2"]

So GraphViz is just misused to display BGL straight line drawing

Recently I enhanced it to time each relevant BGL function call
in order to verify linear runtime as well as to investigate RAM usage.

In 1993 I created a technical report about creation of random maximal 
planar
graphs and published the code 2 years ago:
https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8

I created maximal planar randomgraphs on 10,000, 100,000, 1million and
10million vertices, and used them as input for above timing code.

All was fine until and including 1million vertex graph.
But for 10million vertex graph final "is_straight_line_drawing()"
incorrectly asserted:

hermann_at_7950x:~$ randomgraph/randomgraph 10000000 -t maximal_planar -o 
10000000.u

-------------------------------------
malloc: 18   malloc-free: 0
hermann_at_7950x:~$ time ./straight_line_graphviz 10000000.u t
read_leda_graph(g, argv[1]); 9.63147
make_connected(g); 1.82002
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
boyer_myrvold_params::embedding = &embedding2[0])); 73.5683
make_biconnected_planar(g, &embedding2[0]); 25.9196
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
boyer_myrvold_params::embedding = &embedding2[0])); 88.7905
make_maximal_planar(g, &embedding2[0]); 42.7211
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
boyer_myrvold_params::embedding = &embedding2[0])); 96.7233
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
boyer_myrvold_params::embedding = embedding)); 68.5428
planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 
24.2465
chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), 
ordering.end(), straight_line_drawing); 4.49772
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)

real	7m25,836s
user	7m15,357s
sys	0m10,356s
hermann_at_7950x:~$

I added code into 
"graph/include/boost/graph/is_straight_line_drawing.hpp" to write
the coordinates of the two edges that intersect:

hermann_at_7950x:~$ cat intersect.txt
a
4143438 86426
4064945 7932
4064944 7931
4143438 86426
hermann_at_7950x:~$

As you can see, both edges share vertex at coordinate "4143438,86426",
but they do not intersect.

Until that point in code the coordinates are std::size_t.
But the called function uses double, causing false report:

inline bool intersects(double x1, double y1, double x2, double y2, 
double a1,
     double b1, double a2, double b2, double epsilon = 0.000001)
{

I played with different epsilon values including 0, but the valid
straight line drawing was always stated to be wrong.

There are several algorithms for segment intersection with integer 
coordinates
that don't need division and are correct for integer coordinates that
are result of

       chrobak_payne_straight_line_drawing(
         g, embedding, ordering.begin(), ordering.end(), 
straight_line_drawing);

https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line_segment

or

https://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf#page=4

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

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

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?

Regards,

Hermann.