Graph Drawing

 v. 2020.02 (Catalpa)

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.

using namespace ogdf;
int main()
if (!GraphIO::read(GA, G, "unix-history.gml", GraphIO::readGML)) {
std::cerr << "Could not load unix-history.gml" << std::endl;
return 1;
GraphIO::write(GA, "output-unix-history-hierarchical.gml", GraphIO::writeGML);
GraphIO::write(GA, "output-unix-history-hierarchical.svg", GraphIO::drawSVG);
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.

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()
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++];
SL.setLayout(ohl);, 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.

using namespace ogdf;
int main()
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;
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.

using namespace ogdf;
int main()
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;
auto* ps = new PlanarSubgraphFast<int>;
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.

using namespace ogdf;
int main()
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.
using namespace ogdf;
template<class T>
static MultilevelBuilder *getDoubleFactoredZeroAdjustedMerger()
T *merger = new T();
return merger;
static InitialPlacer *getBarycenterPlacer()
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.
// In this example it is used to scale with fixed factor 2 relative to the graph drawing.
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.
// No scaling is done. It is fixed to factor 1.
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.
// The ScalingLayout is used to scale with a factor between 5 and 10
// relative to the edge length.
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;
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.
// It will use 1000 iterations at each level.
// To minimize dispersion of the graph when more nodes are added, a
// ScalingLayout can be used to scale up the graph on each level.
// The FastMultipoleEmbedder is nested into this ScalingLayout.
// Set the merger and placer according to the wanted configuration.
InitialPlacer *placer;
switch (argv[1][0]) {
case 2:
configureFastLayout(sl, merger, placer);
case 1:
configureNiceLayout(sl, merger, placer);
configureNoTwistLayout(sl, merger, placer);
// Then the ModularMultilevelMixer is created.
// The single level layout, the placer and the merger are set.
// 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.
// The TileToRowsPacker merges these connected components after computation.
// At last the PreprocessorLayout removes double edges and loops.
// After the computation the MultilevelGraph is exported to the
// GraphAttributes and written to disk.
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;
double separation() const override
Returns the minimum distance between edges and vertices.
Definition: OrthoLayout.h:69
void setScalingType(ScalingType type)
Sets a ScalingType wich sets the relative scale for the Graph.
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
Declaration of class VariablEmbeddingInserter.
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
void setInitialPlacer(InitialPlacer *placement)
Sets the initial placer module to placement.
Definition: ModularMultilevelMixer.h:138
The barycenter placer for multilevel layout.
Definition: BarycenterPlacer.h:42
Declaration of class MedianHeuristic.
Postproceesing with all edges.
The median heuristic for 2-layer crossing minimization.
Definition: MedianHeuristic.h:42
static bool read(Graph &G, const string &filename, ReaderFunc reader=GraphIO::read)
Reads arbitrary format from a file specified by name.
Definition: GraphIO.h:166
FMMMOptions::QualityVsSpeed qualityVersusSpeed() const
Returns the current setting of option qualityVersusSpeed.
Definition: FMMMLayout.h:343
void setLayoutModule(LayoutModule *layout)
Definition: ComponentSplitterLayout.h:63
The planarization approach for drawing graphs.
Definition: PlanarizationLayout.h:48
static const long edgeStyle
Corresponds to edge attributes strokeColor(edge), strokeType(edge), and strokeWidth(edge).
Definition: GraphAttributes.h:146
static const long nodeStyle
Corresponds to node attributes strokeColor(node), strokeType(node), strokeWidth(node),...
Definition: GraphAttributes.h:150
The optimal ranking algorithm.
Definition: OptimalRanking.h:74
MMM is a Multilevel Graph drawing Algorithm that can use different modules.
Best quality.
void setRandomize(bool b)
if true, layout algorithm will randomize the layout in the beginning
Definition: FastMultipoleEmbedder.h:82
static bool writeGML(const Graph &G, std::ostream &os)
Writes graph G in GML format to output stream os.
static bool drawSVG(const GraphAttributes &A, std::ostream &os, const SVGSettings &settings)
Optimal edge insertion module.
Definition: VariableEmbeddingInserter.h:52
void call(Graph &G, MultilevelGraph &MLG)
Declaration of class OrthoLayout which represents an orthogonal planar drawing algorithm.
Scales by a factor relative to the desired Edgelength m_desEdgeLength.
The fast multipole multilevel layout algorithm.
Definition: FMMMLayout.h:232
void setProfile(Profile pProfile)
Sets the layout profile.
Definition: HypergraphLayout.h:132
Stores additional attributes of edge standard representation of a hypergraph.
Definition: HypergraphAttributes.h:182
The fast multipole embedder approach for force-directed layout.
Definition: FastMultipoleEmbedder.h:46
Declaration of the PlanarSubgraphFast.
The PreprocessorLayout removes multi-edges and self-loops.
Definition: PreprocessorLayout.h:50
virtual void call(HypergraphAttributes &HA) override
Computes a layout of hypergraph given by HA.
The solar merger for multilevel layout.
Definition: SolarMerger.h:43
Declaration of class SubgraphPlanarizer.
double layerDistance() const
Returns the minimal allowed y-distance between layers.
Definition: OptimalHierarchyLayout.h:110
static bool readGML(Graph &G, std::istream &is)
Reads graph G in GML format from input stream is.
void setInserter(EdgeInsertionModule *pInserter)
Sets the module option for the edge insertion module.
Definition: SubgraphPlanarizer.h:140
Computation of a planar subgraph using PQ-trees.
Definition: PlanarSubgraphFast.h:68
Definition: MultilevelGraph.h:65
virtual void call(GraphAttributes &GA) override
Calls the layout algorithm for graph GA.
ogdf::NodeArray< int >
void weightedPositionPriority(bool on)
void setRandomizePositions(bool on)
Defines whether the positions of the node are randomized before the secondary layout call.
Definition: PreprocessorLayout.h:99
Places nodes at the barycenter of his neighbors.
double cOverhang() const
Returns the option m_cOverhang, which specifies the minimal distance of incident edges to the corner ...
Definition: OrthoLayout.h:82
double unitEdgeLength() const
Returns the current setting of option unitEdgeLength.
Definition: FMMMLayout.h:326
Base class for placer modules.
Definition: InitialPlacer.h:43
void setCrossMin(LayeredCrossMinModule *pCrossMin)
Sets the module option for the two-layer crossing minimization.
Definition: SugiyamaLayout.h:388
Preprocessor Layout simplifies Graphs for use in other Algorithms.
Declaration of optimal ranking algorithm for Sugiyama algorithm.
bool useHighLevelOptions() const
Returns the current setting of option useHighLevelOptions.
Definition: FMMMLayout.h:311
void setScaling(double min, double max)
Sets the minimum and the maximum scaling factor.
void setExtraScalingSteps(unsigned int steps)
Sets how often the scaling should be repeated.
double nodeDistance() const
Returns the minimal allowed x-distance between nodes on a layer.
Definition: OptimalHierarchyLayout.h:99
void setPlanarLayouter(LayoutPlanRepModule *pPlanarLayouter)
Sets the module option for the planar layout algorithm.
Definition: PlanarizationLayout.h:138
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:565
Declares ogdf::EmbedderMinDepthMaxFaceLayers.
virtual void call(GraphAttributes &GA) override
Calls the algorithm for graph GA and returns the layout information in GA.
Scales by a factor relative to the drawing.
Merges nodes with neighbour to get a Multilevel Graph.
static const long edgeType
Corresponds to edge attribute type(edge).
Definition: GraphAttributes.h:134
void setLayout(HierarchyLayoutModule *pLayout)
Sets the module option for the computation of the final layout.
Definition: SugiyamaLayout.h:399
void setPacker(CCLayoutPackModule *packer)
Definition: ComponentSplitterLayout.h:67
Declaration of Fast Multipole Multilevel Method (FM^3).
static const long nodeTemplate
Corresponds to node attribute templateNode(node).
Definition: GraphAttributes.h:153
Declares class GraphIO which provides access to all graph read and write functionality.
double weightBalancing() const
Returns the weight for balancing successors below a node; 0.0 means no balancing.
Definition: OptimalHierarchyLayout.h:146
Places Nodes with solar system rules.
void setEmbedder(EmbedderModule *pEmbedder)
Sets the module option for the graph embedding algorithm.
Definition: PlanarizationLayout.h:125
void setLayoutRepeats(int times=1)
Determines how many times the one-level layout will be called.
Definition: ModularMultilevelMixer.h:143
Splits and packs the components of a Graph.
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:492
void setLayoutModule(LayoutModule *layout)
Sets the secondary layout.
Definition: PreprocessorLayout.h:94
The Orthogonal layout algorithm for planar graphs.
Definition: OrthoLayout.h:41
Merges nodes with neighbour to get a Multilevel Graph.
static const long nodeLabel
Corresponds to node attribute label(node).
Definition: GraphAttributes.h:131
Base class for merger modules.
Definition: MultilevelBuilder.h:43
bool arrangeCCs() const
Returns the current setting of option arrangeCCs.
Definition: SugiyamaLayout.h:293
for every hyperedge e a minimal subcubic tree connecting all hypernodes incident with e together is a...
static bool write(const Graph &G, const string &filename, WriterFunc writer)
Writes arbitrary format to a file specified by name.
Definition: GraphIO.h:178
Definition: HypergraphLayout.h:57
Sugiyama's layout algorithm.
Definition: SugiyamaLayout.h:159
Declaration of class TileToRowsCCPacker.
void setLayoutRepeats(unsigned int repeats)
Sets how often the LayoutModule should be applied.
bool newInitialPlacement() const
Returns the current setting of option newInitialPlacement.
Definition: FMMMLayout.h:337
static const long edgeGraphics
Corresponds to edge attribute bends(edge).
Definition: GraphAttributes.h:119
void setSecondaryLayout(LayoutModule *layout)
Sets a LayoutModule that should be applied after scaling.
Planar graph embedding that minimizes block-nesting depth and maximizes the external face and optimiz...
Definition: EmbedderMinDepthMaxFaceLayers.h:52
Declaration of Fast-Multipole-Embedder layout algorithm.
ScalingLayout scales and calls a secondary layout.
void setSubgraph(PlanarSubgraphModule< int > *pSubgraph)
Sets the module option for the computation of the planar subgraph.
Definition: SubgraphPlanarizer.h:135
void setRanking(RankingModule *pRanking)
Sets the module option for the node ranking (layer assignment).
Definition: SugiyamaLayout.h:378
Definition: ComponentSplitterLayout.h:44
void setNumIterations(uint32_t numIterations)
sets the maximum number of iterations
Definition: FastMultipoleEmbedder.h:76
Declaration of class PlanarizationLayout.
The planarization approach for crossing minimization.
Definition: SubgraphPlanarizer.h:106
Layout algorithms for hypergraph based on edge standard representations (clique / star / tree) - Hype...
void removeReinsert(RemoveReinsertType rrOption)
Sets the remove-reinsert postprocessing method.
Definition: VariableEmbeddingInserterBase.h:73
Declaration and implementation of the optimal third phase of the Sugiyama algorithm.
Scales a graph layout and calls a secondary layout algorithm.
Definition: ScalingLayout.h:46
Modular multilevel graph layout.
Definition: ModularMultilevelMixer.h:72
The solar placer for multilevel layout.
Definition: SolarPlacer.h:42
void call(GraphAttributes &ga) override
Calls planarization layout for GraphAttributes ga.
The tile-to-rows algorithm for packing drawings of connected components.
Definition: TileToRowsCCPacker.h:40
static const long nodeType
Corresponds to node attribute type(node).
Definition: GraphAttributes.h:137
Class for the representation of nodes.
Definition: Graph_d.h:169
Definition: Hypergraph.h:405
void setMultilevelBuilder(MultilevelBuilder *levelBuilder)
Sets the multilevel builder module to levelBuilder.
Definition: ModularMultilevelMixer.h:133
static const long nodeGraphics
Corresponds to node attributes x(node), y(node), width(node), height(node), and shape(node).
Definition: GraphAttributes.h:116
void runs(int nRuns)
Sets the number of randomized runs to nRuns.
Definition: PlanarSubgraphFast.h:176
Declaration of Sugiyama algorithm.
Merges nodes with solar system rules.
void setLevelLayoutModule(LayoutModule *levelLayout)
Sets the one-level layout module to levelLayout.
Definition: ModularMultilevelMixer.h:123
The LP-based hierarchy layout algorithm.
Definition: OptimalHierarchyLayout.h:76