Open Graph Drawing Framework
current version:
v.2015.05 (Baobab)


This page gives an overview about the various modules in OGDF used by layout algorithms. Modules not used with any layout algorithm are omitted here. For further information, click on the class name of the module base class or the class of a specific implementation.

This overview page is structured according to general modules, planarity-based layouts, multilevel layouts, planar layouts, and upward layouts.

General modules

These modules are used by various layout algorithms.

CCLayoutPackModule A CCLayoutPackModule arranges the layouts of the connected components of a graph, thereby obtaining a layout of the whole graph.
TileToRowsCCPacker The tile-to-rows algorithm packs the components into rows and respects a given aspect ratio.

Modules used with planarity-based layouts

These modules are used by planarity-based algorithms, in particular by algorithms applying the planarization approach.
See classes: PlanarizationLayout, PlanarizationGridLayout, and ClusterPlanarizationLayout

PlanarSubgraphModule A PlanarSubgraphModule computes a planar subgraph of an input graph G by determining which edges in G must be removed.
FastPlanarSubgraph The fast planar subgraph algorithm is based on PQ-trees. It is fast and usually achieves very good results, especially when using randomization option.
MaximalPlanarSubgraphSimple This algorithm computes a maximal planar subgraph by simply adding edges incrementally and testing planarity each time; if the graph becomes non-planar, the just inserted edge is removed.
This approach always computes a maximal planar subgraph, but is quite slow in practice and usually cannot achieve better results than FastPlanarSubgraph.
MaximumPlanarSubgraph The branch-and-cut-based exact algorithm computes a maximum planar subgraph, i.e., the largest possible planar subgraph.
Requires: COIN and ABACUS
EdgeInsertionModule An EdgeInsertionModule re-inserts edges previously removed to make a graph planar, resulting in a planarized representation of the original graph.
FixedEmbeddingInserter The fixed-embedding inserter is the standard approach for edge insertion. It simply fixes an embedding and inserts the edges by computing shortest paths in the dual graph. Each edge insertion requires linear runtime. The quality of the solutions can significantly be improved using postprocessing and random permutations.
VariableEmbeddingInserter The variable-embedding inserter applies the optimal one-edge insertion algorithm. It finds the best embedding for inserting an edge with the least crossings in linear runtime. It also supports postprocessing and random permutations to improve solution quality when inserting serveral edges.
EmbedderModule An EmbedderModule computes a planar embedding of a planar graph.
SimpleEmbedder The simple embedder simply encapsulates a standard planar embedding algorithm.
EmbedderMaxFace The max-face embedder computes a planar embedding with a largest possible external face in linear time.
EmbedderMinDepth The min-depth embedder computes a planar embedding with minimal block-nesting depth in linear time. The block-nesting depth is a measure for the nesting of biconnected components (blocks) in the planar embedding.
EmbedderMinDepthPiTa The min-depth-PiTA embedder computes a planar-embedding with minimal block-nesting depth for given embeddings of the biconnected components. The algorithm takes linear time.
EmbedderMinDepthMaxFace The min-depth max-face embedder combines the min-depth and max-face embedder. It computes a planar embedding with minimal block-nesting depth, which has the largest external face. The algorithm takes linear time.
EmbedderMaxFaceLayers The max-face-layers embedder is an improved version of the max-face embedder, which also tries to unfold inner parts.
EmbedderMinDepthMaxFaceLayers The min-depth max-face-layers embedder combines the min-depth and max-face-layers embedders, similar as the min-depth max-face embedder.
LayoutPlanRepModule A LayoutPlanRepModule is a planar layout algorithm which gets a PlanRepUML as input.
OrthoLayout The orthogonal layout algorithm is based on bend minimization using network flow algorithms; it also supports high-degree vertices of arbitrary size and applies sophisticated orthogonal compaction techniques.
GridLayoutPlanRepModule A GridLayoutPlanRepModule is a planar grid layout algorithm which gets a PlanRep as input.
MixedModelLayout The mixed-model layout is a linear-time algorithm that produces polyline drawings with few bends and good angular resolution.
Uses: EmbedderModule, AugmentationModule, ShellingOrderModule, MixedModelCrossingsBeautifierModule
LayoutClusterPlanRepModule A LayoutClusterPlanRepModule is a planar layout algorithm which gets a ClusterPlanRep as input.
ClusterOrthoLayout The cluster orthogonal layout algorithm is also based on bend minimization using network flow algorithms, supports high-degree vertices of arbitrary size, and applies sophisticated orthogonal compaction techniques.

Modules used with multilevel layouts

These modules are used within the modular multilevel-layout framework.
See class: ModularMultilevelMixer

MultilevelBuilder A MultilevelBuilder constructs a multilevel hierarchy, represented as a MultilevelGraph
RandomMerger The random merger simply selects vertices randomly and merges them with a random neighbor, until the size of the graph decreases by a predefined factor.
MatchingMerger The matching merger computes a matching by visiting the vertices in a random order, matching each unmatched vertex with a random unmatched neighbor if one exists.
EdgeCoverMerger The edge-cover merger is a variant of the matching merger intended to eliminate that for star-like structures a linear number of levels may be necessary. In addition to the matching, an edge cover is computed such that each contained edge is incident to at least one unmatched vertex. These cover edges are then used to merge their end points.
LocalBiconnectedMerger The local-biconnected merger is a variant of the edge cover merger that tries to avoid loss of biconnectivity in the local neighborhoods around the merging positions.
SolarMerger The solar merger corresponds to the method used in the FM³ algorithm, where the vertices are partitioned into solar systems, classifying each vertex as either sun, planet, or moon. The resulting solar systems are then collapsed to their sun vertex.
IndependentSetMerger The independent-set merger corresponds to the strategy within the GRIP approach, which is based on maximal independent set filtrations.
InitialPlacer An InitialPlacer computes an initial placement for vertices in a multilevel layout algorithm
ZeroPlacer The zero placer simply places a vertex at the same position as its representative in the previous level, with a small random offset to avoid zero distances between vertices.
RandomPlacer The random placer places vertices at random positions within the smallest circle containing all vertices around the barycenter of the current drawing.
This is usually a bad strategy, and other placers should be used instead!
BarycenterPlacer The barycenter placer places a vertex at the barycenter of its neighbor's positions.
MedianPlacer The median placer is an alternative to the barycenter places; it uses the median of the neighbor positions for each coordinate axis.
SolarPlacer The solar placer corresponds to the approach in the FM³ algorithm and uses information from the solar merger. A new vertex is placed on the direct line between two suns at the relative position with respect to its position on the intersystem path between these suns.
Please note: In combination with other mergers, the solar merger is equivalent to the zero placer.

Modules used with planar layouts

These modules are used with planar straight- and polyline algorithms. The crossings beautifier modules are only relevant when drawing planarized representations of a graph, where certain vertices represent edge crossings in the final drawing.
See classes: MixedModelLayout, PlanarDrawLayout, and PlanarStraightLayout

AugmentationModule An AugmentationModule adds edges to a graph to obtain a certain connectivity.
DfsMakeBiconnected This algorithm is based on depth-first search. If the input graph is planar, the augmented graph will also remain planar.
PlanarAugmentation The planar augmentation algorithm augments a planar graph to a planar biconnected graph. The implementation is based on the algorithm by Fialko and Mutzel. It gives much better solutions than the DFS-based algorithm, usually close to the optimum.
ShellingOrderModule A ShellingOrderModule computes a shelling order of a planar graph.
BiconnectedShellingOrder This algorithm computes a shelling order for a biconnected planar graph.
TriconnectedShellingOrder This algorithm computes a shelling order for a triconnected planar graph.
MixedModelCrossingsBeautifierModule A MixedModelCrossingsBeautifierModule is used within MixedModelLayout for improving the layout of vertices representing crossings in the final drawing.
MMDummyCrossingsBeautifier The dummy crossings beautifier does not do any beautification at all. It can be used to obtain the original mixed-model algorithm.
MMCBDoubleGrid The double-grid crossings beautifier simply doubles the grid.
MMCBLocalStretch The local-stretch crossings beautifier uses a local stretch strategy.

Modules used with upward layouts

These modules are used with layout algorithms for producing upward drawings of (acyclic) digraphs.
See classes: SugiyamaLayout and UpwardPlanarizationLayout, as well as DominanceLayout and VisibilityLayout

RankingModule A RankingModule computes a layering of a directed graph.
LongestPathRanking The longest-path ranking produces a layering whose height is the length of a longest path in the digraph. The implementation contains a special optimization for reducing the lengths of unnecessary long edges.
Uses: AcyclicSubgraphModule
OptimalRanking The optimal ranking algorithm computes a layering with minimal edge spans. It is based on an ILP-formulation and implemented using network flow.
Uses: AcyclicSubgraphModule
CoffmanGrahamRanking The Coffman-Graham ranking algorithm computes a layering with small height for a given maximal layer widths (number of nodes on a layer).
Uses: AcyclicSubgraphModule
AcyclicSubgraphModule An AcyclicSubgraphModule computes an acyclic subgraph of an input graph by determining a set of edges to be removed.
DfsAcyclicSubgraph The depht-first-search based algorithm simply removes the back edges in a DFS-tree. The linear-time algorithm is fast, but it might remove significantly more edges than necessary.
GreedyCycleRemoval The greedy-cycle-removal algorithm applies the greedy heuristic by Eades and Lin to compute a maximal acyclic subgraph. The quality of the solution is usually better than the one obtained by the simple DFS-based approach. The algorithm takes linear time as well.
TwoLayerCrossMin A TwoLayerCrossMin module minimizes the crossings between two layers in a layered graph, where one layer is fixed and the other layer shall be reordered.
BarycenterHeuristic The barycenter heuristic computes for each vertex the barycenter (average) of the positions of its neighbors on the fixed layer, and then sorts the vertices according to this value.
MedianHeuristic The median heuristic computes for each vertex the median of the positions of its neighbors on the fixed layer, and then sorts the vertices according to this value.
SplitHeuristic The split heuristic chooses a pivot vertex v, and places every other vertex to the left or right of v according to whether it would make fewer crossings. This step is applied recursively to order the left hand set and the right hand side of v.
SiftingHeuristic The sifting heuristic
GreedySwitchHeuristic The greedy-switch heuristic
GreedyInsertHeuristic The greedy-insert heuristic
HierarchyLayoutModule A HierarchyLayoutModule assigns coordinates to vertices and bend points in a Hierarchy.
FastHierarchyLayout The fast hierarchy layout module implements the coordinates assignment algorithm by Buchheim, Jünger, and Leipert. It guarantees that all edges will have at most two bends, and for each edge with exactly two bends that the segment between them is drawn vertically.
FastSimpleHierarchyLayout The fast-simple hierarchy layout module implements the coordinates assignment algorithm by Brandes and Köpf.
OptimalHierarchyLayout The optimal hierarch layout is based on an LP-formulation. It provides similar optimizations for long edges as the fast hierarchy layout module, in particular edges will have at most two bends.
Requires: COIN
UpwardPlanarizerModule An UpwardPlanarizerModule computes an upward planarized representation of an input graph.
SubgraphUpwardPlanarizer Uses: FUPSModule, UpwardEdgeInserterModule, AcyclicSubgraphModule
FUPSModule A FUPSModule computes a feasible upward planar subgraph.
FUPSSimple The FUPS-simple module computes a feasible upward planar subgraph using the algorithm by Chimani, Gutwenger, Mutzel, and Wong.
UpwardEdgeInserterModule An UpwardEdgeInserterModule re-inserts edges into an upward planarized representation.
FixedEmbeddingUpwardEdgeInserter The fixed-embedding upward edge inserter reinserts edges into a fixed upward planar embedding.
UPRLayoutModule An UPRLayoutModule computes a layout of an upward planarized representation.
LayerBasedUPRLayout The layer-based UPR layouter computes a layered hierarchy and applies a hierarchy layout module as within the Sugiyama algorithm.
Uses: RankingModule, HierarchyLayoutModule
tech/modules.txt · Last modified: 2014/12/16 12:20 (external edit)
This page is driven by DokuWiki