Graph Decomposition

Generate an acyclic random graph

This example shows how to generate a random plane triangulation, decompose it into its 4-connected components, and draw each of them from the outside in.

#include <ogdf/basic/graph_generators/randomized.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/decomposition/FourBlockTree.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/planarlayout/PlanarStraightLayout.h>
 
#include <string>
 
using namespace ogdf;
 
int main(void) {
    Graph g;
    constexpr int n = 16;
    randomPlanarConnectedGraph(g, n, 3 * n - 6);
    const adjEntry externalFace = g.firstNode()->firstAdj()->cyclicSucc();
 
    const auto fbt = FourBlockTree::construct(g, externalFace);
 
    PlanarStraightLayout layout;
    {
        GraphAttributes ga(g,
                ogdf::GraphAttributes::nodeLabel | ogdf::GraphAttributes::nodeGraphics
                        | ogdf::GraphAttributes::nodeStyle | ogdf::GraphAttributes::edgeGraphics
                        | ogdf::GraphAttributes::edgeStyle);
        ga.directed() = false;
        layout.callFixEmbed(ga, externalFace);
        for (const node v : g.nodes) {
            ga.label(v) = std::to_string(v->index());
            ga.fillColor(v) = Color::Name::White;
        }
        GraphIO::write(ga, "output-g.svg", GraphIO::drawSVG);
    }
    int i = 0;
    fbt->preorder([&](const FourBlockTree& treeNode) -> void {
        GraphAttributes ga(*treeNode.g,
                ogdf::GraphAttributes::nodeLabel | ogdf::GraphAttributes::nodeGraphics
                        | ogdf::GraphAttributes::nodeStyle | ogdf::GraphAttributes::edgeGraphics
                        | ogdf::GraphAttributes::edgeStyle);
        ga.directed() = false;
        layout.callFixEmbed(ga, treeNode.externalFace);
        for (const node v : treeNode.g->nodes) {
            ga.label(v) = std::to_string(treeNode.originalNodes[v]->index());
            ga.fillColor(v) = Color::Name::White;
        }
        GraphIO::write(ga, std::string("output-node-") + std::to_string(i++) + ".svg",
                GraphIO::drawSVG);
    });
    return 0;
}

Step-by-step explanation

1. The class FourBlockTree is declared in ogdf/decomposition/FourBlockTree.h
2. We create a random plane graph. Because of its high number of edges, it must be maximally planar, i.e., triangulated.
3. We use the function FourBlockTree::construct to build its 4-block tree. The 4-block tree is represented by its root, which has members
   • g, the 4-connected component
   • originalNodes, a map from nodes in g to the corresponding nodes in the original graph
   • externalFace, an adjEntry to the right of which the externalFace of the 4-connected component lies
   • parent, a raw pointer to its parent node (or nullptr, if this is the root)
   • parentFace, the adjEntry in parent corresponding to externalFace (or nullptr, if this is the root)
   • children, a vector of unique_ptrs to the child nodes
4. For our simple application of traversing the 4-block tree bottom-up, we can use the method preorder, which calls its argument on each node of the 4-block tree in preorder. A similar method named postorder exists as well. For each node of the 4-block tree, we draw it and save the drawing under a unique filename. To this end we use PlanarStraightLayout. We use originalNodes to assign multiple occurrences of the same node in the 4-block tree the same label.