Orthogonal layout

Back to List of Examples

Load a graph from a GML file, apply customized Orthogonal Layout, and write the graph with layout information back to a file.

Requires: ogdf v.2007.11

#include <ogdf/planarity/PlanarizationLayout.h>
#include <ogdf/planarity/VariableEmbeddingInserter.h>
#include <ogdf/planarity/FastPlanarSubgraph.h>
#include <ogdf/orthogonal/OrthoLayout.h>
#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>
 
 
using namespace ogdf;
 
int main()
{
    Graph G;
    GraphAttributes GA(G,
	GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics |
	GraphAttributes::nodeLabel | GraphAttributes::nodeColor | 
	GraphAttributes::edgeColor | GraphAttributes::edgeStyle | 
	GraphAttributes::nodeStyle | GraphAttributes::nodeTemplate);
    GA.readGML(G, "er-diagram.gml");
 
    PlanarizationLayout pl;
 
    FastPlanarSubgraph *ps = new FastPlanarSubgraph;
    ps->runs(100);
    VariableEmbeddingInserter *ves = new VariableEmbeddingInserter;
    ves->removeReinsert(EdgeInsertionModule::rrAll);
    pl.setSubgraph(ps);
    pl.setInserter(ves);
 
    EmbedderMinDepthMaxFaceLayers *emb = new EmbedderMinDepthMaxFaceLayers;
    pl.setEmbedder(emb);
 
    OrthoLayout *ol = new OrthoLayout;
    ol->separation(20.0);
    ol->cOverhang(0.4);
    ol->setOptions(2+4);
    pl.setPlanarLayouter(ol);
 
    pl.call(GA);
 
    GA.writeGML("er-diagram-layout.gml");
 
    return 0;
}

Example graph: er-diagram.gml

In this example, we want to produce an orthogonal layout of an ER-diagram. We will use the class PlanarizationLayout which implements the planarization approach for drawing graphs. This approach divides the layout process into two steps: The crossing minimization step seeks for a planarized representation of the graph with as few crossings as possible (a planarized representation is a planar graph, where a dummy vertex is “put” on each edge crossing) and the planar layout step applies a planar drawing algorithm (usually an orthogonal layout algorithm) to the planarized representation. The final layout is then simply obtained by replacing the dummy vertices again with edge crossings.

In our example, we proceed as follows. First, we declare a Graph G with GraphAttributes GA storing all the layout information we need (these include in our case also colors and line styles, since these shall be preserved in the output GML file). Then, we declare an instance pl of PlanarizationLayout and set various module options:

• The crossing minimization step consists of computing a planar subgraph and reinserting the remaining edges. We use FastPlanarSubgraph for computing the planar subgraph and set its number of randomized runs to 100, and we use VariableEmbeddingInserter with very high postprocessing (EdgeInsertionModule::rrAll) as edge inserter, giving us a high-quality crossing minimization heuristic.
• The computed (planar) orthogonal layout is influenced by the choice of the planar embedding and planar layout algorithm. We use an algorithm that minimizes the block nesting depth and tries to have large faces at the outside of the drawing (EmbedderMinDepthMaxFaceLayers), since such embeddings are well-suited for clear planar layouts. Our planar layout algorithm is OGDF’s standard orthogonal layout, but we need to set it as module option, since we want to adjust the spacing parameters. The separation specifies the minimum distance between vertices and edges, the cOverhang specifies how close edges can attach at vertex corners (in this case 40% of the node size, but the algorithm can also reduce this if required), and the additional options which are set to 2+4 turn on the scaling and progressive options of OrthoLayout.

Finally, we call the planarization layout algorithm in the usual way by passing the graph attributes object, which will then be assigned the produced layout. This layout is saved in the file er-diagram-layout.gml.

Graph layout:
er-diagram-layout.gml

Drawing: