Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Last active October 6, 2024 11:19
Show Gist options
  • Save Hermann-SW/99d151a273d290ee0d843c79b2da26a8 to your computer and use it in GitHub Desktop.
Save Hermann-SW/99d151a273d290ee0d843c79b2da26a8 to your computer and use it in GitHub Desktop.
Boost make_"connected / biconnected_planar / maximal_planar"+straight_line_drawing demos made create graphviz graph with fixed coordinates
//=======================================================================
// 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;
}
@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 13, 2024

Useful small makefile for this gist:

pi@raspberrypi5:~ $ make clean
rm -f straight_line_graphviz
pi@raspberrypi5:~ $ make
g++ -Wall -pedantic -Wextra straight_line_graphviz.cpp -o straight_line_graphviz
pi@raspberrypi5:~ $ make cpplint
cpplint --filter=-legal/copyright,-build/namespaces straight_line_graphviz.cpp
Done processing straight_line_graphviz.cpp
pi@raspberrypi5:~ $ make cppcheck
cppcheck --enable=all --suppress=missingIncludeSystem straight_line_graphviz.cpp --check-config
Checking straight_line_graphviz.cpp ...
pi@raspberrypi5:~ $ 

Makefile:

straight_line_graphviz: straight_line_graphviz.cpp
	g++ -Wall -pedantic -Wextra $< -o $@

cpplint: straight_line_graphviz.cpp
	cpplint --filter=-legal/copyright,-build/namespaces $<

cppcheck: straight_line_graphviz.cpp
	cppcheck --enable=all --suppress=missingIncludeSystem $< --check-config

clean:
	rm -f straight_line_graphviz

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 15, 2024

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:
BGL straight_line_graphviz 2

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 15, 2024

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:
BGL straight_line_graphviz 2b

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:~ $ 

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 15, 2024

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)
BGL straight_line_graphviz 3

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 15, 2024

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)
BGL straight_line_graphviz 4

@Hermann-SW
Copy link
Author

Hermann-SW commented Mar 15, 2024

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)
x

@Hermann-SW
Copy link
Author

Hermann-SW commented Apr 28, 2024

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
BGL C60 planar_straight_line_drawing
It is also called "football fullerene", consists of 20 hexagons and 12 pentagons.

Here is C60 spherical embedding you most likely know:
Football_Pallo_valmiina-cropped

@Hermann-SW
Copy link
Author

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:
image

@Hermann-SW
Copy link
Author

Hermann-SW commented Jul 28, 2024

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
$ 

image

@Hermann-SW
Copy link
Author

Hermann-SW commented Oct 4, 2024

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
...

image

@Hermann-SW
Copy link
Author

Hermann-SW commented Oct 5, 2024

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)

@Hermann-SW
Copy link
Author

Hermann-SW commented Oct 6, 2024

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:~$ 

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment