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

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: