[Boost] runtime+memory evaluation of 6 BGL planar graph algorithms

From: hermann_at_[hidden]
Date: 2024-10-06 12:11:14

Half a year ago I copied together Boost examples making use of:

boost/graph/make_connected.hpp
boost/graph/make_biconnected_planar.hpp
boost/graph/make_maximal_planar.hpp
boost/graph/boyer_myrvold_planar_test.hpp
boost/graph/planar_canonical_ordering.hpp
boost/graph/chrobak_payne_drawing.hpp

I added "read_leda_graph()" for processing graph files.
And added code to write a graphiviz file from the generated
straight line drawing. Use of "layout=neato" with fixated
vertex coordinates with exclamation mark (pos="3,2!")
misuse GraphViz to just draw the BGL determined straight
line drawing.

I did evaluation on random maximal planar graphs
with 10,000 up to 100 million vertices in 10x steps.

In 1993 I wrote a technical report on how to create
maximal planar random graphs. I published the 1994 code
two years ago (self written graph lib, not LEDA nor Boost):
https://github.com/Hermann-SW/randomgraph

All details of the evaluation including runtime table
in this "straight_line_graphviz.cpp" gist comment:
https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8?permalink_comment_id=5221542#gistcomment-5221542

Total runtime factors are 13.5x and 20.9x between 1, 10
and 100 million vertex graphs.

Since the input graphs were maximal planar, the algorithms
make_connected / make_biconnected_planar and
make_maximal_planar did not have much to do.

The resident RAM usage is perfectly linear,
2.8 / 28.1 / 281.4 GB for 1 / 10 / 100 million vertices.

100 million vertices, 300 million edges, edge property,
planar ordering, planar straight line drawing and 8 byte
storage for numbers on 64bit OS cause a factor of 2800
comparing resident RAM used with number of vertices.

Regards,

Hermann.