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

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