Boost make_"connected / biconnected_planar / maximal_planar"+straight_line_drawing demos made create graphviz graph with fixed coordinates

straight_line_graphviz.cpp

//=======================================================================
// 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;
}

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)

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

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.

Here is C60 spherical embedding you most likely know:

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