Calling Layout Algorithms

Hierarchical layout

This example shows how to read a graph from a file and use a layout algorithm to retrieve a hierarchical visualization of it.

#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/SugiyamaLayout.h>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
      GraphAttributes::nodeGraphics |
      GraphAttributes::edgeGraphics |
      GraphAttributes::nodeLabel |
      GraphAttributes::edgeStyle |
      GraphAttributes::nodeStyle |
      GraphAttributes::nodeTemplate);
    if (!GraphIO::read(GA, G, "unix-history.gml")) {
        std::cerr << "Could not load unix-history.gml" << std::endl;
        return 1;
    }
 
    SugiyamaLayout SL;
    SL.setRanking(new OptimalRanking);
    SL.setCrossMin(new MedianHeuristic);
 
    OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;
    ohl->layerDistance(30.0);
    ohl->nodeDistance(25.0);
    ohl->weightBalancing(0.8);
    SL.setLayout(ohl);
 
    SL.call(GA);
    GraphIO::write(GA, "output-unix-history-hierarchical.gml");
    GraphIO::write(GA, "output-unix-history-hierarchical.svg");
 
    return 0;
}

Step-by-step explanation

1. What we see here for the first time is how to read a graph from a file. To achieve this we first have to enable all the attributes we want to be filled in using the information from the specified file. When calling ogdf::GraphIO::read() (again specifying the correct reader function for .gml files) any attribute enabled in GA will be parsed from the file – if present.
2. We then set up the configuration for a hierarchical layout algorithm called ogdf::SugiyamaLayout. As can be seen the algorithm is highly modular. In this case we specify
   1. A ranking module that will determine the layering of the graph
   2. A module that handles the minimization of two-layer crossing
   3. The main module that computes the actual graph layout
3. Although this is done by passing dynamically allocated configuration objects we don't have to worry about cleaning them up, as the layout class takes care of that. Also there is default values for all modules so you need not explicitly set all of them.
4. Calling the layout algorithm on an ogdf::GraphAttribute object relies on node size information and will alter the xy-coordinates of the nodes but will leave the other attributes untouched, so the svg visualization that is output in the end will still use the information initially read from the .gml file.

Hierarchical layout with predefined layering

This example shows a slight modification of the previous one in that layering is not done by an optimization module but instead is specified in advance.

#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>
#include <ogdf/layered/SugiyamaLayout.h>
 
using namespace ogdf;
 
int r[] = {
    0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9, 10, 10, 11, 12, 12,
    13, 14, 14, 15, 16, 17, 18, 18, 19, 19, 20, 21, 22, 22,
    22, 23, 23, 23, 23, 24, 25, 26, 27, 27, 27, 28, 29, 29,
    29, 30, 30, 31, 31, 31, 32, 33, 33, 34, 34, 35, 35, 35,
    35, 0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18,
    19, 20, 21, 22, 23, 25, 27, 29, 30, 31, 32, 33, 34, 35, -1
};
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
      GraphAttributes::nodeGraphics |
      GraphAttributes::edgeGraphics |
      GraphAttributes::nodeLabel |
      GraphAttributes::edgeStyle |
      GraphAttributes::nodeStyle |
      GraphAttributes::nodeTemplate);
    if (!GraphIO::read(GA, G, "unix-history-time.gml", GraphIO::readGML)) {
        std::cerr << "Could not load unix-history-time.gml" << std::endl;
        return 1;
    }
 
    NodeArray<int> rank(G);
    int i = 0;
    for(node v : G.nodes)
        rank[v] = r[i++];
 
    SugiyamaLayout SL;
    SL.setCrossMin(new MedianHeuristic);
    SL.arrangeCCs(false);
 
    OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;
    ohl->layerDistance(30.0);
    ohl->nodeDistance(25.0);
    ohl->weightBalancing(0.7);
    SL.setLayout(ohl);
 
    SL.call(GA, rank);
    GraphIO::write(GA, "output-unix-history-hierarchical-ranking.gml", GraphIO::writeGML);
    GraphIO::write(GA, "output-unix-history-hierarchical-ranking.svg", GraphIO::drawSVG);
 
    return 0;
}

There is just one new concept we encounter here which is ogdf::NodeArray<T>, a templated class used for direct mapping from ogdf::node handles to any type T. In this case it holds a rank value for each node which is later passed together with GA to the layout algorithm. In this case the ranking optimization module has no effect. Note that we also disable the separate layout and arranging of connected components by the default packing module using ogdf::SugiyamaLayout::arrangeCCs().

Energy-based layout

This example shows yet another layout algorithm, ogdf::FMMMLayout (fast multipole multilevel layout), suited for very large graphs and based on potential-field and force computations.

#include <ogdf/energybased/FMMMLayout.h>
#include <ogdf/fileformats/GraphIO.h>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G);
    if (!GraphIO::read(G, "sierpinski_04.gml")) {
        std::cerr << "Could not load sierpinski_04.gml" << std::endl;
        return 1;
    }
 
    for (node v : G.nodes)
        GA.width(v) = GA.height(v) = 5.0;
 
    FMMMLayout fmmm;
 
    fmmm.useHighLevelOptions(true);
    fmmm.unitEdgeLength(15.0);
    fmmm.newInitialPlacement(true);
    fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
 
    fmmm.call(GA);
    GraphIO::write(GA, "output-energybased-sierpinski-layout.gml", GraphIO::writeGML);
    GraphIO::write(GA, "output-energybased-sierpinski-layout.svg", GraphIO::drawSVG);
 
    return 0;
}

Step-by-step explanation

1. An important thing to note here is that after loading the graph from a file we can access node width and height without explicitly enabling ogdf::GraphAttributes::nodeGraphics in GA. This is because ogdf::GraphAttributes::nodeGraphics and ogdf::GraphAttributes::edgeGraphics are enabled by default.
2. ogdf::FMMMLayout can be configured in two ways: using high-level options (recommended) or low-level options (requires good knowledge of the algorithm). For this example we will use the few high-level options ogdf::FMMMLayout provides and thus set the respective flag to true before actually setting anything.
3. We then set the unit edge length (a scaling factor if you will), enable initial replacing of nodes and choose one of the available options from ogdf::FMMMOptions::QualityVsSpeed to tune tradeoffs between speed and aesthetic of the resulting graph. The only remaining high-level option is ogdf::FMMMOptions::PageFormatType which defaults to a Square if not explicitly set. These high-level options will then be used to derive the low-level settings accordingly.
4. After calling the algorithm on our read graph instance the same instance augmented by the node positions in the resulting graph layout is written back out to a .gml and a .svg file.

Orthogonal layout

This example shows how to layout a graph so that all edges propagate only parallel to the x- or y-axis meaning any edge bends have an angle of 90°. This is called an orthogonal drawing.

#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/orthogonal/OrthoLayout.h>
#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>
#include <ogdf/planarity/PlanarSubgraphFast.h>
#include <ogdf/planarity/PlanarizationLayout.h>
#include <ogdf/planarity/SubgraphPlanarizer.h>
#include <ogdf/planarity/VariableEmbeddingInserter.h>
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
      GraphAttributes::nodeGraphics | GraphAttributes::nodeType |
      GraphAttributes::edgeGraphics | GraphAttributes::edgeType);
 
    if (!GraphIO::read(GA, G, "ERDiagram.gml", GraphIO::readGML)) {
        std::cerr << "Could not read ERDiagram.gml" << std::endl;
        return 1;
    }
 
    for (node v : G.nodes)
    {
        GA.width(v) /= 2;
        GA.height(v) /= 2;
    }
 
    PlanarizationLayout pl;
 
    SubgraphPlanarizer *crossMin = new SubgraphPlanarizer;
    PlanarSubgraphFast<int> *ps = new PlanarSubgraphFast<int>;
    ps->runs(100);
    VariableEmbeddingInserter *ves = new VariableEmbeddingInserter;
    ves->removeReinsert(RemoveReinsertType::All);
 
    crossMin->setSubgraph(ps);
    crossMin->setInserter(ves);
    pl.setCrossMin(crossMin);
 
    EmbedderMinDepthMaxFaceLayers *emb = new EmbedderMinDepthMaxFaceLayers;
    pl.setEmbedder(emb);
 
    OrthoLayout *ol = new OrthoLayout;
    ol->separation(20.0);
    ol->cOverhang(0.4);
    pl.setPlanarLayouter(ol);
 
    pl.call(GA);
 
    GraphIO::write(GA, "output-ERDiagram.gml", GraphIO::writeGML);
    GraphIO::write(GA, "output-ERDiagram.svg", GraphIO::drawSVG);
 
    return 0;
}

Step-by-step explanation

1. Here, we use ogdf::PlanarizationLayout as our base layout algorithm, again configuring it to our needs by passing dynamically allocated module instances.
2. The first module we specify is the ogdf::CrossingMinimizationModule for which we choose ogdf::SubgraphPlanarizer. It works in two core phases, the former will compute a planar subgraph while the latter then reinserts the remaining edges while trying to minimize the resulting crossings. We alter its default configuration by setting the number of randomized reruns for planar subgraph computation and making it consider all edges in the postprocessing step during edge reinsertion.
3. The next submodule we configure is ogdf::EmbedderModule for which we use a default instance of ogdf::EmbedderMinDepthMaxFaceLayers.
4. The final module supplied to pl is ogdf::LayoutPlanRepModule. We use ogdf::OrthoLayout to achieve the main feature we wanted to achieve from the beginning and configure the minimum allowed distance between edges and vertices (and their corners).
5. As always, after calling the composed algorithm on the graph instance the result is once again written to out to .gml and .svg files.

Hypergraph layout

This example shows the interface for IO and layout of hypergraphs. There are only few algorithms for hypergraphs in the OGDF.

#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/hypergraph/HypergraphLayout.h>
 
using namespace ogdf;
 
int main()
{
    Hypergraph H;
 
    H.readBenchHypergraph("c17.bench");
 
    HypergraphAttributesES HA(H, EdgeStandardType::tree);
    HypergraphLayoutES hlES;
 
    hlES.setProfile(HypergraphLayoutES::Profile::Normal);
    hlES.call(HA);
 
    GraphIO::write(HA.repGA(), "output-c17.gml", GraphIO::writeGML);
    GraphIO::write(HA.repGA(), "output-c17.svg", GraphIO::drawSVG);
 
    return 0;
}

Step-by-step explanation

1. While ogdf::Hypergraph is the direct analogon to ogdf::Graph, ogdf::HypergraphAttributesES is the analogon of ogdf::GraphAttributes for edge-standard representation.
2. The input file is read via a dedicated hypergraph reader function ogdf::Hypergraph::readBenchHypergraph.
3. The hypergraph attributes get initialized and the option ogdf::EdgeStandardType that governs the internal representation of hyperedges is set to a tree representation. Note that only ogdf::EdgeStandardType::star and ogdf::EdgeStandardType::tree will insert dummy nodes which might be useful (as in this example) to generate a representation of the hypergraph using the standard ogdf::Graph and ogdf::GraphAttributes interfaces.
4. The base layout algorithm ogdf::HypergraphLayoutES that is then used has basically the same interface for modular configuring as the standard graph layout algorithms but on top of that it also has an option to choose between the general profiles ogdf::HypergraphLayoutES::Profile::Normal and ogdf::HypergraphLayoutES::Profile::ElectricCircuit.
5. After calling the layout algorithm on our hypergraph instance we can access the ogdf::GraphAttributes component of hlES as the internal representation works on a wrapped instance of ogdf::GraphAttributes with some dummy nodes added anyways. This is especially useful for using the standard ogdf::GraphIO interface to output a reduced representation of the resulting hypergraph layout.

Multilevel layout mixer

This example shows the use of the modular multilevel mixer class that can be used to build energybased multilevel layouts. Since it is modular one can easily assemble different layouts by using different coarsening techniques (merger), placer and single level layouts. As this example is quite exhaustive explanation is provided in place as inline comments.

// Introduction for Multilevelmixer:
//
// Multilevel layout computation is an iterative process that can
// be roughly divided in three phases: coarsening, placement, and
// single level layout. Starting with the smallest graph, the final
// layout for the input graph is obtained by successively computing
// layouts for the graph sequence computed by the coarsening phase.
// At each level, the additional vertices need to be placed into the
// layout of the preceding level, optionally after a scaling to provide
// the necessary space.
// It helps to overcome some problems of single level energybased graph
// layouts (such as finding a local optimal solution) and it speeds up
// the computation.
//
// The Modular Multilevel Mixer is an abstract class that can be used
// to build energybased multilevel layouts. Since it is modular you can
// easily assemble different layouts by using different coarsening
// techniques (merger), placer and single level layouts.
 
#include <ogdf/basic/PreprocessorLayout.h>
#include <ogdf/energybased/FastMultipoleEmbedder.h>
#include <ogdf/energybased/multilevel_mixer/BarycenterPlacer.h>
#include <ogdf/energybased/multilevel_mixer/EdgeCoverMerger.h>
#include <ogdf/energybased/multilevel_mixer/LocalBiconnectedMerger.h>
#include <ogdf/energybased/multilevel_mixer/ModularMultilevelMixer.h>
#include <ogdf/energybased/multilevel_mixer/ScalingLayout.h>
#include <ogdf/energybased/multilevel_mixer/SolarMerger.h>
#include <ogdf/energybased/multilevel_mixer/SolarPlacer.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/packing/ComponentSplitterLayout.h>
#include <ogdf/packing/TileToRowsCCPacker.h>
 
using namespace ogdf;
 
template<class T>
static MultilevelBuilder *getDoubleFactoredZeroAdjustedMerger()
{
    T *merger = new T();
    merger->setFactor(2.0);
    merger->setEdgeLengthAdjustment(0);
    return merger;
}
 
static InitialPlacer *getBarycenterPlacer()
{
    BarycenterPlacer *placer = new BarycenterPlacer();
    placer->weightedPositionPriority(true);
    return placer;
}
 
static void configureFastLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
{
    // The SolarMerger is used for the coarsening phase.
    merger = new SolarMerger(false, false);
    // The SolarPlacer is used for the placement.
    placer = new SolarPlacer();
 
    // Postprocessing is applied at each level after the single level layout.
    // It is turned off in this example.
    sl->setExtraScalingSteps(0);
    // In this example it is used to scale with fixed factor 2 relative to the graph drawing.
    sl->setScalingType(ScalingLayout::ScalingType::RelativeToDrawing);
    sl->setScaling(2.0, 2.0);
}
 
static void configureNiceLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
{
    // The EdgeCoverMerger is used for the coarsening phase.
    merger = getDoubleFactoredZeroAdjustedMerger<EdgeCoverMerger>();
    // The BarycenterPlacer is used for the placement.
    placer = getBarycenterPlacer();
 
    // Postprocessing is applied at each level after the single level layout.
    // In this example a FastMultipoleEmbedder with zero iterations is used for postprocessing.
    sl->setExtraScalingSteps(0);
    // No scaling is done. It is fixed to factor 1.
    sl->setScalingType(ScalingLayout::ScalingType::RelativeToDrawing);
    sl->setScaling(1.0, 1.0);
}
 
static void configureNoTwistLayout(ScalingLayout *sl, MultilevelBuilder *&merger, InitialPlacer *&placer)
{
    // The LocalBiconnectedMerger is used for the coarsening phase.
    // It tries to keep biconnectivity to avoid twisted graph layouts.
    merger = getDoubleFactoredZeroAdjustedMerger<LocalBiconnectedMerger>();
    // The BarycenterPlacer is used for the placement.
    placer = getBarycenterPlacer();
 
    // Postprocessing is applied at each level after the single level layout.
    // It is turned off in this example.
    sl->setExtraScalingSteps(1);
    // The ScalingLayout is used to scale with a factor between 5 and 10
    // relative to the edge length.
    sl->setScalingType(ScalingLayout::ScalingType::RelativeToDesiredLength);
    sl->setScaling(5.0, 10.0);
}
 
int main(int argc, const char *argv[])
{
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " (0|1|2)" << std::endl;
        return 255;
    }
 
    // We first declare a Graph G with GraphAttributes GA and load it from
    // the GML file sierpinski_04.gml.
    Graph g;
    GraphAttributes ga(g);
    if (!GraphIO::read(ga, g, "uk_Pack_Bary_EC_FRENC.gml", GraphIO::readGML)) {
        std::cerr << "Could not load Graph" << std::endl;
        return 1;
    }
 
    // We assign a width and height of 10.0 to each node.
    for (node v : g.nodes) {
        ga.width(v) = ga.height(v) = 10.0;
    }
 
    // Then we create a MultilevelGraph from the GraphAttributes.
    MultilevelGraph mlg(ga);
 
    // The FastMultipoleEmbedder is used for the single level layout.
    FastMultipoleEmbedder *fme = new FastMultipoleEmbedder();
    // It will use 1000 iterations at each level.
    fme->setNumIterations(1000);
    fme->setRandomize(false);
 
    // To minimize dispersion of the graph when more nodes are added, a
    // ScalingLayout can be used to scale up the graph on each level.
    ScalingLayout *sl = new ScalingLayout();
    sl->setLayoutRepeats(1);
    // The FastMultipoleEmbedder is nested into this ScalingLayout.
    sl->setSecondaryLayout(fme);
 
    // Set the merger and placer according to the wanted configuration.
    MultilevelBuilder *merger;
    InitialPlacer *placer;
    switch (argv[1][0]) {
    case 2:
        configureFastLayout(sl, merger, placer);
        break;
    case 1:
        configureNiceLayout(sl, merger, placer);
        break;
    default:
        configureNoTwistLayout(sl, merger, placer);
        break;
    }
 
    // Then the ModularMultilevelMixer is created.
    ModularMultilevelMixer *mmm = new ModularMultilevelMixer;
    mmm->setLayoutRepeats(1);
    // The single level layout, the placer and the merger are set.
    mmm->setLevelLayoutModule(sl);
    mmm->setInitialPlacer(placer);
    mmm->setMultilevelBuilder(merger);
 
    // Since energybased algorithms are not doing well for disconnected
    // graphs, the ComponentSplitterLayout is used to split the graph and
    // computation is done separately for each connected component.
    ComponentSplitterLayout *csl = new ComponentSplitterLayout;
    // The TileToRowsPacker merges these connected components after computation.
    TileToRowsCCPacker *ttrccp = new TileToRowsCCPacker;
    csl->setPacker(ttrccp);
    csl->setLayoutModule(mmm);
 
    // At last the PreprocessorLayout removes double edges and loops.
    PreprocessorLayout ppl;
    ppl.setLayoutModule(csl);
    ppl.setRandomizePositions(true);
 
    ppl.call(mlg);
 
    // After the computation the MultilevelGraph is exported to the
    // GraphAttributes and written to disk.
    mlg.exportAttributes(ga);
    GraphIO::write(ga, "output-multilevelmixer-" + std::string(argv[1]) + ".gml", GraphIO::writeGML);
    GraphIO::write(ga, "output-multilevelmixer-" + std::string(argv[1]) + ".svg", GraphIO::drawSVG);
 
    return 0;
}