-
-
Save Hermann-SW/99d151a273d290ee0d843c79b2da26a8 to your computer and use it in GitHub Desktop.
//======================================================================= | |
// Distributed under the Boost Software License, Version 1.0. (See | |
// accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
/* | |
f=straight_line_graphviz | |
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f | |
cpplint --filter=-legal/copyright,-build/namespaces,-runtime/references $f.cpp | |
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config | |
*/ | |
//======================================================================= | |
#include <cassert> | |
#include <cstring> | |
#include <iostream> | |
#include <fstream> | |
#include <vector> | |
#include <boost/graph/adjacency_list.hpp> | |
#include <boost/graph/properties.hpp> | |
#include <boost/graph/graph_traits.hpp> | |
#include <boost/property_map/property_map.hpp> | |
#include <boost/ref.hpp> | |
#include <boost/graph/make_connected.hpp> | |
#include <boost/graph/make_biconnected_planar.hpp> | |
#include <boost/graph/make_maximal_planar.hpp> | |
#include <boost/graph/planar_face_traversal.hpp> | |
#include <boost/graph/boyer_myrvold_planar_test.hpp> | |
#include <boost/graph/planar_canonical_ordering.hpp> | |
#include <boost/graph/is_straight_line_drawing.hpp> | |
#include <boost/graph/chrobak_payne_drawing.hpp> | |
// This example shows how to start with a connected planar graph | |
// and add edges to make the graph maximal planar (triangulated.) | |
// Any maximal planar simple graph on n vertices has 3n - 6 edges and | |
// 2n - 4 faces, a consequence of Euler's formula. | |
using namespace boost; | |
// a class to hold the coordinates of the straight line embedding | |
struct coord_t { | |
std::size_t x; | |
std::size_t y; | |
}; | |
// time measurements | |
clock_t start_; | |
#define __(blk) if (output) std::cerr << #blk << " "; start_ = clock(); blk \ | |
if (output) std::cerr << (clock()-start_)*1.0/CLOCKS_PER_SEC << std::endl; | |
template <class Graph> | |
void read_leda_graph(Graph& g, const char* gname) { | |
int n, m; | |
std::string line; | |
std::ifstream in(gname); | |
assert(in); | |
std::getline(in, line); | |
in >> line >> line >> n; | |
g = Graph(n); | |
for (int i=1; i <= n; ++i) { | |
in >> line; | |
} | |
in >> m; | |
for (int i=1; i <= m; ++i) { | |
int s, t, v; | |
in >> s >> t >> v; | |
add_edge(s-1, t-1, g); | |
} | |
} | |
int main(int argc, char** argv) { | |
typedef adjacency_list< vecS, vecS, undirectedS, | |
no_property, property< edge_index_t, int > > | |
graph; | |
assert((argc >> 1) == 1); | |
bool output = (argc == 3) && strchr(argv[2], 't'); | |
bool dbg = (argc == 3) && strchr(argv[2], 'd'); | |
bool coords = (argc == 3) && strchr(argv[2], 'c'); | |
bool noisld= (argc == 3) && strchr(argv[2], 'n'); | |
graph g; | |
__(read_leda_graph(g, argv[1]);) | |
int edge_count_input = num_edges(g); | |
__(make_connected(g);) | |
// Initialize the interior edge index | |
property_map< graph, edge_index_t >::type e_index = get(edge_index, g); | |
graph_traits< graph >::edges_size_type edge_count = 0; | |
graph_traits< graph >::edge_iterator ei, ei_end; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity; compute the planar embedding as a side-effect | |
typedef std::vector< graph_traits< graph >::edge_descriptor > vec_t; | |
std::vector< vec_t > embedding2(num_vertices(g)); | |
__(assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0]));) | |
__(make_biconnected_planar(g, &embedding2[0]);) | |
// Re-initialize the edge index, since we just added a few edges | |
edge_count = 0; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity again; compute the planar embedding as a side-effect | |
__(assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0]));) | |
__(make_maximal_planar(g, &embedding2[0]);) | |
// Re-initialize the edge index, since we just added a few edges | |
edge_count = 0; | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
put(e_index, *ei, edge_count++); | |
// Test for planarity one final time; compute the planar embedding as a | |
// side-effect | |
__(assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = &embedding2[0]));) | |
typedef std::vector< std::vector< graph_traits< graph >::edge_descriptor > > | |
embedding_storage_t; | |
typedef boost::iterator_property_map< embedding_storage_t::iterator, | |
property_map< graph, vertex_index_t >::type > | |
embedding_t; | |
// Create the planar embedding | |
embedding_storage_t embedding_storage(num_vertices(g)); | |
embedding_t embedding(embedding_storage.begin(), get(vertex_index, g)); | |
__(assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, | |
boyer_myrvold_params::embedding = embedding));) | |
// Find a canonical ordering | |
std::vector< graph_traits< graph >::vertex_descriptor > ordering; | |
__(planar_canonical_ordering(g, embedding, std::back_inserter(ordering));) | |
// Set up a property map to hold the mapping from vertices to coord_t's | |
typedef std::vector< coord_t > straight_line_drawing_storage_t; | |
typedef boost::iterator_property_map< | |
straight_line_drawing_storage_t::iterator, | |
property_map< graph, vertex_index_t >::type > | |
straight_line_drawing_t; | |
straight_line_drawing_storage_t straight_line_drawing_storage( | |
num_vertices(g)); | |
straight_line_drawing_t straight_line_drawing( | |
straight_line_drawing_storage.begin(), get(vertex_index, g)); | |
// Compute the straight line drawing | |
__(chrobak_payne_straight_line_drawing( | |
g, embedding, ordering.begin(), ordering.end(), straight_line_drawing);) | |
if (coords) { | |
std::ofstream out("coords.txt"); | |
BGL_FORALL_VERTICES(v, g, graph) { | |
out << v << " "; | |
out << straight_line_drawing[v].x << " "; | |
out << straight_line_drawing[v].y << std::endl; | |
} | |
} | |
// Verify that the drawing is actually a plane drawing | |
if (!noisld) | |
__(assert(is_straight_line_drawing(g, straight_line_drawing));) | |
if (!output) { | |
std::cout << "graph {" << std::endl; | |
std::cout << " layout=neato" << std::endl; | |
if (dbg) { | |
std::cout << " size=18" << std::endl; | |
std::cout << " node [shape=none,fontsize=24]" << std::endl; | |
} else { | |
std::cout << " node [shape=none]" << std::endl; | |
} | |
// get the property map for vertex indices | |
typedef property_map<graph, vertex_index_t>::type IndexMap; | |
IndexMap index = get(vertex_index, g); | |
graph_traits< graph >::vertex_iterator vi, vi_end; | |
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { | |
coord_t coord(get(straight_line_drawing, *vi)); | |
std::cout << " " << *vi << " [pos=\"" << coord.x << "," << coord.y | |
<< "!\""; | |
if (dbg) | |
std::cout << " label=\"" << *vi <<"\""; | |
std::cout << "]" << std::endl; | |
} | |
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { | |
std::cout << " " << index[source(*ei, g)] | |
<< "--" << index[target(*ei, g)] | |
<< "[style=" << (edge_count_input-- > 0 ? "bold" : "dotted") | |
<< "]" << std::endl; | |
} | |
std::cout << "}" << std::endl; | |
} | |
return 0; | |
} |
Revision 4 replaces fixed input graph code with simple code to read graph in LEDA format.
In addtion original input graph edges are drawn in bold.
Edges added by make_"connected / biconnected_planar / maximal_planar" are drawn dotted.
Here bash echo creates small LEDA graph:
pi@raspberrypi5:~ $ GraphvizFiddle.py chromium-browser <(./straight_line_graphviz <(echo -e "LEDA.GRAPH\nunsigned\nint\n4\n0\n0\n0\n0\n2\n1 2 0\n3 4 0"))
pi@raspberrypi5:~ $
This shows up in GraphvizFiddle — LEDA input graph nodes 1..n get renamed to 0..n-1:
Revision 4 cpplint clean (again).
Revision 5 graph with n+1 vertices, LEDA vertices 1..n keep same, vertex 0 and its edges are just not drawn.
With same command as in previous comment this shows up in GraphvizFiddle:
pi@raspberrypi5:~ $ echo -e "LEDA.GRAPH\nunsigned\nint\n4\n0\n0\n0\n0\n2\n1 2 0\n3 4 0"
LEDA.GRAPH
unsigned
int
4
0
0
0
0
2
1 2 0
3 4 0
pi@raspberrypi5:~ $
Using 30yo code that can generate maximal planar random graphs as well as other types, in this 2yo repo:
https://github.com/Hermann-SW/randomgraph
pi@raspberrypi5:~ $ randomgraph
[3] Format: randomgraph n [-t type] [-o file.[u/bit/bit8/a]] [-s seed] [-no] [-r edges] [-n]( type in {cubic,cubic_Halin,maximal_planar,dual_of_cubic_Halin} )
pi@raspberrypi5:~ $
This creates random maximal planar graph on 8 vertices (with 3*8-6=18 edges) and removes 12 edges randomly, as straight_line_graphviz input:
pi@raspberrypi5:~ $ GraphvizFiddle.py chromium-browser <(./straight_line_graphviz <(randomgraph 8 -o - -r 12 -s 123456))
-------------------------------------
malloc: 19 malloc-free: 0
pi@raspberrypi5:~ $
(GraphvizFiddle share link for opening in browser)
This creates random cubic Halin graph on 8 vertices, as straight_line_graphviz input, with random seed 123456:
pi@raspberrypi5:~ $ GraphvizFiddle.py chromium-browser <(./straight_line_graphviz <(randomgraph 8 -o - -t cubic_Halin -s 123456))
-------------------------------------
malloc: 23 malloc-free: 0
pi@raspberrypi5:~ $
(GraphvizFiddle share link)
I was curious where vertex 0 (that was not drawn) was placed in the temporary maximal planar graph of previous comment.
So I commented out the 3 continue statements temporarily just to see:
(GraphvizFiddle share link for opening in browser)
Associated forum thread:
https://forums.raspberrypi.com/viewtopic.php?t=367391
C60 fullerene was drawn as example graph:
https://forums.raspberrypi.com/viewtopic.php?t=367391#p2204504
It is also called "football fullerene", consists of 20 hexagons and 12 pentagons.
The randomgraph application described before allows to output random maximal planar graphs.
Even more, it creates random maximal planar combinatorial embeddings.
When "-o" output file has a ".a" suffix, the combinatorial embedding is in the written adjacency lists:
hermann@7600x:~$ NOSTAT=1 randomgraph 8 -o x.a -s 123456 && cat x.a
[[1,7,3,5,2,4],[0,4,2,3,6,7],[0,5,3,1,4],[0,7,6,1,2,5],[2,1,0],[3,2,0],[3,7,1],[6,3,0,1]]
hermann@7600x:~$
But the vertices in this representation are 0-based and not 1-based as in LEDA graph format.
New "dbg" option for straight_line_drawing.cpp allows to reduce the graphviz vertex labels by 1 to match the adjacency list output for easy visual inspection of the embedding ordering at any given vertex. For example for vertex 3
its adjacency list [0,7,6,1,2,5]
can be verified easily when displayed with GraphvizFiddle.py, as ordered counterclockwise traversal of the edges at vertex 3
:
I learned about and used CGAL library (Computational Geometry ALgorithms Library) recently.
I started with code from this gist and then made it write an .off output file, with z=0 for all points from the computed planar straight line drawing:
https://github.com/Hermann-SW/random_maximal_planar_embedding/tree/main/boost#random_maximal_planar_embedding
Then I used CGAL draw_polyhedron.cpp example to draw planar graph straight line drawing in window:
$ NOSTAT= randomgraph 10 -o 10.u
$ ./straight_line_drawing 10.u > 10.off 2>err
$ draw_polyhedron 10.off
Using OpenGL context 4.6 GL
$
Newest revision has template read_leda_graph() and does optional timing of the different BGL function calls.
Now the straight line drawing is done with graphviz nodes 0..num_vertices(G)-1 (index = leda index - 1).
Optional 2nd arg allows to select stuff depending on whether these characters are contained:
't' timing
'd' print GraphViz node labels
'c' write determined strainght line drawing coordinates into coords.txt
Timing for random maximal planar graph on 1million vertices:
https://github.com/Hermann-SW/randomgraph
hermann@7950x:~$
hermann@7950x:~$ ~/randomgraph/randomgraph 1000000 -t maximal_planar -o 1000000.u
-------------------------------------
malloc: 18 malloc-free: 0
hermann@7950x:~$ ./straight_line_graphviz 1000000.u t
read_leda_graph(g, argv[1]); 0.777592
make_connected(g); 0.164412
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 7.64732
make_biconnected_planar(g, &embedding2[0]); 0.29194
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.95229
make_maximal_planar(g, &embedding2[0]); 4.67061
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 6.96455
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding)); 7.13283
planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 0.29354
chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); 0.322715
assert(is_straight_line_drawing(g, straight_line_drawing)); 0.969046
hermann@7950x:~$
GraphViz drawing of K5 minus one edge with node labels:
hermann@7950x:~$ cat K5e.u
LEDA.GRAPH
int
int
5
0
0
0
0
0
9
1 2 0
1 3 0
1 4 0
1 5 0
2 3 0
2 4 0
2 5 0
3 4 0
3 5 0
hermann@7950x:~$ ./straight_line_graphviz K5e.u d
...
Latest revision added 'n' for disabling "is_straight_line_drawing()" when timing very large graph (10million vertices) because of new issue:
boostorg/graph#388
(and removed not needed vertex property)
Tested on 384GB RAM server with maximal planar randomgraph inputs from 10,000 up to 100 million vertices.
Maximal planar randomgraph created with:
https://github.com/Hermann-SW/randomgraph
~/randomgraph/randomgraph 100000000 -t maximal_planar -o 100000000.u
hermann@e5-2680:~$ wc 100000000.u
399999999 999999987 7233859598 100000000.u
hermann@e5-2680:~$
#vertices | 10,000 | 100,000 | 1,000,000 | 10,000,000 | 100,000,000 |
---|---|---|---|---|---|
function runtime [s] | |||||
read_leda_graph() | 0.020008 | 0.154834 | 1.47035 | 17.1115 | 196.042 |
make_connected() | 0.000971 | 0.013016 | 0.212996 | 2.78277 | 36.6699 |
boyer_myrvold_planarity_test() | 0.106312 | 1.21981 | 15.167 | 168.816 | 3434.22 |
make_biconnected_planar() | 0.003323 | 0.043937 | 0.651643 | 41.9703 | 741.72 |
boyer_myrvold_planarity_test() | 0.076281 | 1.13024 | 14.3753 | 193.546 | 4339.4 |
make_maximal_planar() | 0.026054 | 0.517922 | 7.06895 | 71.6249 | 1114.13 |
boyer_myrvold_planarity_test() | 0.054965 | 1.12413 | 14.4695 | 206.346 | 4567.78 |
boyer_myrvold_planarity_test() | 0.056981 | 1.15145 | 14.7344 | 163.61 | 3773.54 |
planar_canonical_ordering() | 0.00162 | 0.028491 | 0.397891 | 36.7577 | 713.713 |
chrobak_payne_straight_line_drawing() | 0.001588 | 0.027082 | 0.671891 | 11.0337 | 207.756 |
total runtime [h:mm:ss] | 0:01:08 | 0:15:21 | 5:20:48 | ||
maximal resident RAM usage [GB] | 2.8 | 28.1 | 281.4 |
Last row determined from output of:
top -b | grep straigh
Biggest graph execution:
hermann@e5-2680:~$ ./straight_line_graphviz 100000000.u tn
read_leda_graph(g, argv[1]); 196.042
make_connected(g); 36.6699
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 3434.22
make_biconnected_planar(g, &embedding2[0]); 741.72
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 4339.4
make_maximal_planar(g, &embedding2[0]); 1114.13
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = &embedding2[0])); 4567.78
assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, boyer_myrvold_params::embedding = embedding)); 3773.54
planar_canonical_ordering(g, embedding, std::back_inserter(ordering)); 713.713
chrobak_payne_straight_line_drawing( g, embedding, ordering.begin(), ordering.end(), straight_line_drawing); 207.756
hermann@e5-2680:~$
Option "t" does the timings, option "n" excludes "is_straight_line_drawing()" because of new issue:
boostorg/graph#388
Server used:
hermann@e5-2680:~$ grep E5 /proc/cpuinfo | head -1
model name : Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz
hermann@e5-2680:~$ nproc
48
hermann@e5-2680:~$ grep MemTotal /proc/meminfo
MemTotal: 395522736 kB
hermann@e5-2680:~$ grep PRETTY /etc/os-release
PRETTY_NAME="Ubuntu 20.04.6 LTS"
hermann@e5-2680:~$
Useful small makefile for this gist:
Makefile: