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

straight_line_graphviz.cpp

#undef NDEBUG // turn on asserts
//=======================================================================
// 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 <boost/core/ignore_unused.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <fstream>
#include <iostream>

#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/chrobak_payne_drawing.hpp>
#include <boost/graph/is_straight_line_drawing.hpp>
#include <boost/graph/make_biconnected_planar.hpp>
#include <boost/graph/make_connected.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
// #include <boost/graph/planar_face_traversal.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.

struct coord_t { size_t x, y; };

#define TIMED(blk)                                                                                           \
    {                                                                                                        \
        if (output)                                                                                          \
            std::cerr << __LINE__ << ": " << #blk << " ";                                                    \
        clock_t start_ = clock();                                                                            \
        blk;                                                                                                 \
        if (output)                                                                                          \
            std::cerr << (clock() - start_) * 1.0 / CLOCKS_PER_SEC << std::endl;                             \
    }

#ifdef REDUNDANT
using VProp = boost::property<boost::vertex_index_t, int>;
#else
using VProp = boost::no_property;
#endif
using EProp   = boost::property<boost::edge_index_t, int>;
using Graph   = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VProp, EProp>;
using ED      = boost::graph_traits<Graph>::edge_descriptor;
using VD      = boost::graph_traits<Graph>::vertex_descriptor;
namespace BMP = boost::boyer_myrvold_params;

static void read_leda_graph(Graph& g, std::string const& gname) {
    std::ifstream in;
    in.exceptions(std::ios::failbit | std::ios::badbit); // rudimentary ERROR handling...
    in.open(gname);

    assert(in);

    std::string line;
    getline(in, line);
    int n;
    in >> line >> line >> n;

    g = Graph(n);

    for (int i = 1; i <= n; ++i)
        in >> line;

    int m;
    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) {
    assert((argc >> 1) == 1);
    bool const output = (argc == 3) && strchr(argv[2], 't');
    bool const dbg    = (argc == 3) && strchr(argv[2], 'd');
    bool const coords = (argc == 3) && strchr(argv[2], 'c');

    Graph g;
    TIMED(read_leda_graph(g, argv[1]);)

    long edge_count_input = num_edges(g);

    TIMED(make_connected(g);)

    auto vidx = get(boost::vertex_index, g);
    auto eidx = get(boost::edge_index, g);

    // Initialize the interior edge index
    auto reindex = [eidx, vidx, &g] {
        boost::ignore_unused(vidx);

        for (size_t i = 0; ED e : boost::make_iterator_range(edges(g)))
            eidx[e] = i++;
#ifdef REDUNDANT
        for (size_t i = 0; VD v : boost::make_iterator_range(vertices(g)))
            assert(vidx[v] == i++);
#endif
    };

    reindex();

    // Test for planarity; compute the planar embedding as a side-effect
    using Embedding = std::vector<std::vector<ED>>;
    {
        Embedding tmp_embedding(num_vertices(g));
        auto      tmp = tmp_embedding.data(); // make_iterator_property_map(tmp_embedding.begin(), vidx)
        TIMED(assert(boyer_myrvold_planarity_test(BMP::graph = g, BMP::embedding = tmp));)

        TIMED(make_biconnected_planar(g, tmp);)

        reindex(); // since we just added a few edges

        // Test for planarity again; compute the planar embedding as a side-effect
        TIMED(assert(boyer_myrvold_planarity_test(BMP::graph = g, BMP::embedding = tmp));)

        TIMED(make_maximal_planar(g, tmp);)

        reindex(); // since we just added a few edges

        // Test for planarity one final time; compute the planar embedding as a side-effect
        TIMED(assert(boyer_myrvold_planarity_test(BMP::graph = g, BMP::embedding = tmp));)
    }

    // Create the planar embedding
    Embedding embedding(num_vertices(g));
    auto      emb_map = make_safe_iterator_property_map( //
        embedding.begin(), embedding.size(), vidx);

    TIMED(assert(boyer_myrvold_planarity_test(BMP::graph = g, BMP::embedding = emb_map));)

    // Find a canonical ordering
    std::vector<VD> ordering;
    TIMED(planar_canonical_ordering(g, emb_map, back_inserter(ordering));)

    // Set up a property map to hold the mapping from vertices to coord_t's
    std::vector<coord_t> coordinate(num_vertices(g));
    auto drawing = boost::make_safe_iterator_property_map(coordinate.begin(), coordinate.size(), vidx);

    // Compute the straight line drawing
    TIMED(chrobak_payne_straight_line_drawing(g, emb_map, ordering.begin(), ordering.end(), drawing);)

    if (coords) {
        std::ofstream out("coords.txt");
        for (VD v : boost::make_iterator_range(vertices(g))) {
            auto const& [x, y] = drawing[v];
            out << v << " " << x << " " << y << std::endl;
        }
    }

    // Verify that the drawing is actually a plane drawing
    TIMED(assert(is_straight_line_drawing(g, 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;
        }

        for (VD v : boost::make_iterator_range(vertices(g))) {
            auto const& [x, y] = drawing[v];
            std::cout << "  " << vidx[v] << " [pos=\"" << x << "," << y << "!\"";
            if (dbg)
                std::cout << " label=\"" << vidx[v] << "\"";
            std::cout << "]\n";
        }

        for (ED e : boost::make_iterator_range(edges(g))) {
            std::cout << "  " << vidx[source(e, g)] << "--" << vidx[target(e, g)]
                      << "[style=" << (edge_count_input-- > 0 ? "bold" : "dotted") << "]" << "\n";
        }

        std::cout << "}" << std::endl;
    }
}