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 $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;
};

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

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: