Key Features

The following is a short and incomplete list of the main algorithms and datastructures in OGDF. Many algorithms are encaspulated into Modules, such that other algorithms can easily switch between multiple different Algorithms for the same subproblem:

• Basic Data Structures
  • List, dynamic Array, Skiplist, MinHeap, Hashing, etc.
  • Graph and related data structures like ClusterGraph, GraphCopy, GraphAttributes, CombinatorialEmbedding etc.
  • various graph-loaders

• Basic Algorithms
  • 2-connectivity decomposition and BCTree, also DynamicBCTree
  • Min-Cost-Flow
  • Minimum Cut
  • Shortest Path
  • etc.

• Sophisticated Algorithms and Data Structures
  • linear-time implementation of 3-connectivity decomposition and SPQRTree, also DynamicSPQRTree
  • linear-time Planarity testing: the traditional Chiba, Nishizeki, Abe, Ozawa algorithm based on PQ-trees, and the fast BoyerMyrvold, including a linear algorithm to extract multiple Kuratowski-subdivisions at once.
  • linear-time Upward-Planarity testing of sT-graphs
  • Cluster-Planartiy testing of c-connected cluster graphs
  • EmbedderMinDepthMaxFace
  • linear-time NonPlanarCore Reduction
  • linear-time edge insertion over all embeddings (VariableEmbeddingInserter), and SubgraphPlanarizer, the currently best known crossing minimization heuristic. Also suitable for Simultaneous Crossing Minimization and Minor Monotone Crossing Minimization.
  • Planar 2-connected Augmentation

• Layouts
  • Orthogonal: UMLOrtholayout with modules for the steps of shape and compaction, ClusterOrthoLayout
  • Planar: MixedModelLayout, PlanarStraightLayout, PlanarDrawLayout.
  • Planarization: UMLPlanarizationLayout, PlanarizationGridLayout, ClusterPlanarizationLayout
  • Energy-based: FM³ Layout (FMMMLayout), Simulated-Annealing (DavidsonHarelLayout), Fruchterman-Reingold (SpringEmbedderFR), etc.
  • Layered: SugiyamaLayout with multiple pluggable modules for the individual steps (acyclic subgraph, ranking, 2-layer crossing minimization, coordinate assignment), also for cluster graphs
  • Tree-based: TreeLayout, RadialTreeLayout
  • Misc: CircularLayout, BallonLayout