Instantly share code, notes, and snippets.

# Hermann-SW/straight_line_graphviz.cpp

Last active July 21, 2024 22:16
Show Gist options
• 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 //======================================================================= // 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 \$f.cpp cppcheck --enable=all --suppress=missingIncludeSystem \$f.cpp --check-config */ //======================================================================= #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // 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; }; int main(int argc, char** argv) { typedef adjacency_list< vecS, vecS, undirectedS, property< vertex_index_t, int >, property< edge_index_t, int > > graph; int n, m, dbg; char line[200]; assert((argc >> 1) == 1); std::ifstream in(argv[1]); assert(in); dbg = (argc == 3); in >> line; in >> line; in >> line; in >> n; graph g(n+1); 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, t, g); } 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); // Verify that the drawing is actually a plane drawing assert(is_straight_line_drawing(g, straight_line_drawing)); std::cout << "graph {" << std::endl; std::cout << " layout=neato" << std::endl; std::cout << " node [shape=none]" << std::endl; // get the property map for vertex indices typedef property_map::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) { if (index[*vi] == 0) continue; coord_t coord(get(straight_line_drawing, *vi)); std::cout << " " << *vi << " [pos=\"" << coord.x << "," << coord.y << "!\""; if (dbg) std::cout << " label=\"" << *vi - 1 <<"\""; std::cout << "]" << std::endl; } for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { if (index[source(*ei, g)] == 0) continue; if (index[target(*ei, g)] == 0) continue; 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; }

Makes use of pos="x,y!" feature that neato layout engine provides, and dot layout engine does not.
So neato is not used as layout engine at all, but only to display the straight line drawing determined with this gist.

``````pi@raspberrypi5:~ \$ ./straight_line_graphviz | head -5
graph {
layout=neato
node [shape=none]
0 [pos="0,0!"]
1 [pos="16,0!"]
pi@raspberrypi5:~ \$ ./straight_line_graphviz | tail -3
8--5
9--6
}
pi@raspberrypi5:~ \$
``````

Best used with GraphvizFiddle.py in case no local dot/neato installation is present:

``````pi@raspberrypi5:~ \$ GraphvizFiddle.py firefox <(./straight_line_graphviz)
pi@raspberrypi5:~ \$
``````

GraphvizFiddle gets opened in firefox and displays the computed straight line drawing:
(GraphvizFiddle share link for opening in browser)

### Hermann-SW commented Mar 13, 2024

Revision 3 can handle disconnected graphs as well.

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

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

clean:
rm -f straight_line_graphviz
``````

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

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)

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.

Here is C60 spherical embedding you most likely know:

### Hermann-SW commented Jul 21, 2024

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