[Boost][BGL] "is_straight_line_drawing()" is buggy for large graphs
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@7950x:~$ randomgraph/randomgraph 10000000 -t maximal_planar -o 10000000.u ------------------------------------- malloc: 18 malloc-free: 0 hermann@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@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@7950x:~$ cat intersect.txt a 4143438 86426 4064945 7932 4064944 7931 4143438 86426 hermann@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_point... 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_drawin... 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.
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_drawin...
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
On 2024-10-04 18:06, Seth via Boost wrote:
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.
Thanks for providing the link I missed to add in my previous posting.
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.
And for pointing that out. My code was copied together from many graph/example files and I missed the implicit vertex_index. I tried to come up with a much smaller recreate. I created graph K3 and before "is_straight_line_drawing()" call I stored the coordinates reported. To my surprise this does not recreate the issue. I found another way to reduce the more than 7min recreate time on my AMD 7950X fast CPU. I created random maximal planar graph with "only" 1million vertices, with a different random seed. This time assert much faster: hermann@7950x:~$ NOSTAT=1 randomgraph 1000000 -o t.u -s 745734 hermann@7950x:~$ ./straight_line_graphviz t.u -t read_leda_graph(g, argv[1]); 0.762341 make_connected(g); 0.160589 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 7.32607 make_biconnected_planar(g, &embedding2[0]); 0.282637 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.69938 make_maximal_planar(g, &embedding2[0]); 4.52332 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.66393 assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding)); 6.82302 planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 0.288155 chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); 0.324136 assert(is_straight_line_drawing(g, straight_line_drawing)); straight_line_graphviz: straight_line_graphviz.cpp:173: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed. Aborted (core dumped) hermann@7950x:~$ cat intersect.txt b 1295644 587425 709884 1658 709885 1659 1295644 587425 hermann@7950x:~$ intersect.txt shows similar issue to before, the "b" shows that "the other" of two "return false" was hit this time. Again with edges intersecting at vertex with coordinate (1295644,587425) which should not assert. Regards, Hermann.
On 2024-10-04 20:08, Hermann Stamm-Wilbrandt via Boost wrote:
I tried to come up with a much smaller recreate. I created graph K3 and before "is_straight_line_drawing()" call I stored the coordinates reported. To my surprise this does not recreate the issue.
I looked into this again, and after reversing one add_edge() call the recreate works with 3 vertex graph. New issue has all the details, link to gist and fix options: https://github.com/boostorg/graph/issues/388 Regards, Hermann.
On Fri, Oct 4, 2024, at 8:08 PM, hermann@stamm-wilbrandt.de wrote:
This time assert much faster: hermann@7950x:~$ NOSTAT=1 randomgraph 1000000 -o t.u -s 745734
./deps/randomgraph/randomgraph 100000 -t maximal_planar -o tmp.u -s 15287 ./deps/randomgraph/randomgraph 100000 -t maximal_planar -o tmp.u -s 386430491 ./deps/randomgraph/randomgraph 100000 -t maximal_planar -o tmp.u -s 2267595844 ./deps/randomgraph/randomgraph 100000 -t maximal_planar -o tmp.u -s 2298863223 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 ./deps/randomgraph/randomgraph 25000 -t maximal_planar -o tmp.u -s 3700642498 ./deps/randomgraph/randomgraph 25000 -t maximal_planar -o tmp.u -s 970297520 Assert in 1.4s Generating smaller graphs takes proportionally longer, so I probably wait longer.
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
On Sat, Oct 5, 2024, at 12:17 PM, hermann@stamm-wilbrandt.de 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
On 2024-10-05 13:42, Seth wrote:
[...]
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 :)
Sorry, non-native speaker here. chrobak_payne_straight_line_drawing() creates integer coordinates - so no problem: OUT: PositionMap A Writable LValue Property Map that models the Position Map concept. The Position Map concept requires that the value mapped to be an object that has members x and y. For example, if p models PositionMap and v is a vertex in the graph, p[v].x and p[v].y are valid expressions. The type of x and y must be implicitly convertable to std::size_t. is_straight_line_drawing() works on integer coordinates most time. The problem is the internal call of intersects() with double arguments. So inline bool intersects(double x1, double y1, double x2, double y2, double a1, double b1, double a2, double b2, double epsilon = 0.000001) should be changed to inline bool intersects(T x1, T y1, T x2, T_t y2, T a1, T b1, T a2, T b2) without epsilon, and integer type T. It should be implemented with any of the integer coordinate precision loss free algorithms. Regards, Hermann.
participants (2)
-
hermann＠stamm-wilbrandt.de -
Seth