Catalpa

Today, we released the new version v2020.02 (Catalpa) of OGDF.

This release has been in the making for a very long time. So-called “snapshots” have been introduced in the meantime to shorten the waiting time for the next release. Now, even after more than 3000 commits, our original ambitions of the “next release” are still not fully met, but it is about time for a new snapshot. We have however noticed that releasing snapshots has not proven to be useful; it just caused irritation and confusion among OGDF users. Hence, starting with this release, called Catalpa, we will not publish any further snapshots. Instead, we will try to publish ordinary releases more often, i.e., whenever there has been some noteworthy progress in OGDF.

Moreover, OGDF got a new website, a new logo, and the abbreviation now has a second meaning that reflects OGDF’s matter in a better way. OGDF now stands for both “Open Graph Drawing Framework” and “Open Graph algorithms and Data structures Framework”.

Noteworthy changes since last snapshot

If you used the snapshots, you might be interested in noteworthy changes since the last OGDF snapshot:

  • file formats:
    • DL:
      • improved (and fixed) logic when to use matrix and when to use adjacency list
    • DOT:
      • fixes regarding cluster graphs and parsing bugs
      • support for subgraphs, edge styles, edge types, custom node ids, node label positions, arrow directions
    • GEXF:
      • support for subgraphs, labels, bend points, edge styles, custom node ids, node label positions
      • compatibility fixes (e.g., regarding edge weights)
      • fix handling of directed vs. undirected graphs
    • GML:
      • compatibility changes regarding subgraphs
      • support for node types, node label positions, integral edge weights (including compatibility fix), and cluster graphs
    • Graph6 family:
      • new support for Sparse6 (s6) and Digraph6 (d6) file format
      • fixed support for the case of 63 nodes
    • GraphML:
      • compatibility changes regarding subgraphs
      • support for bend points, edge styles, custom node ids, node label positions
      • fix handling of directed vs. undirected graphs
    • STP:
      • support for coordinates, directed edges, node shapes for terminals
      • support for simplified format (from PACE 2018)
    • support for background pattern’s fill color of nodes in many file formats
    • fix self-loops in Chaco file format
    • the generic reader now supports more file formats and GraphAttributes
    • some readers (e.g., Rudy) are stricter now
    • readers with additional information (like edge weights or terminal nodes) are now available in Graph-only form
    • GraphAttributes can now be used for readers with edge weights
    • new generic writer (GraphIO::write()) based on file name extension
    • fix edge arrow issues in SVG printer
    • deprecated GraphIO functions based on filenames (instead of streams) are removed
  • graph generators:
    • faster randomSimpleGraph() and randomSimpleConnectedGraph()
    • new randomSimpleGraphByProbability() for fast random graph generation
  • new basic functions for convenience:
    • cast from AdjElement to corresponding node
    • EdgeElement::nodes() function for for (node v : anEdge->nodes()) { ... }
    • EdgeElement::isParallelUndirected()
    • EdgeElement::isParallelDirected()
    • EdgeElement::isInvertedDirected()
    • GraphAttributes::transferTo{Original,Copy}() to replace GraphCopyAttributes class (which is removed)
    • GraphAttributes::all flag
    • hasNonSelfLoopEdges() to check whether a graph has edges which are not self-loops
    • removeSelfLoops()
    • Graph::searchEdge() with and without edge direction
    • GraphAttributes::point(node) instead of querying single x- and y-coordinates
    • graphUnion() to form a (disjoint and non-disjoint) union of two graphs
    • graphProduct() to form the product of two graphs using a given function, and its common use-cases:
      • cartesianProduct()
      • tensorProduct()
      • lexicographicalProduct()
      • strongProduct()
      • coNormalProduct()
      • modularProduct()
      • rootedProduct()
  • algorithms:
    • new algorithms:
      • PlanarSubgraphTriangles for finding planar subgraphs
      • EdgeIndependentSpanningTrees for k edge-independent spanning trees
      • simple algorithms regarding matchings, e.g., Matching::findMaximalMatching()
    • algorithms for finding maximum planar subgraphs are now weight-templated
    • CliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQR
    • Steiner tree:
      • new SteinerTreeLowerBoundDualAscent algorithm that can be activated for preprocessing (SteinerTreePreprocessing::reduceFastAndDualAscent())
      • overhaul of constructing and managing full components (for approximation algorithms that use full components)
      • slight overhaul of SteinerTreePreprocessing (including some fixes), MinSteinerTreeGoemans139, MinSteinerTreeRZLoss
  • other noteworthy changes (besides typofixes, less compiler warnings, improved documentation, etc.):
    • many layouts/algorithms now run on corner cases like empty graphs or single nodes
    • overhaul of ClusterGraphAttributes, now similar to GraphAttributes
    • AdjacencyOracle can now trade memory usage versus speed by ignoring nodes of small degree
    • Layout::computeBoundingBox() can now handle negative coordinates
    • ConnectivityTester returns correct values also for node-connectivity now
    • GraphCopy copy assignment operator fixed for uninitialized GraphCopy
    • removed PreconditionViolatedException

Noteworthy changes since Baobab

Now let us talk about changes since our last non-snapshot release Baobab.

First of all, we are now using C++11 features, hence a C++11-capable compiler is necessary to use OGDF. Note that for this transition, macros like forall_nodes() have been removed in favor of range-based for-loops.

Check the porting guide for compatibility-breaking changes.

Our build system has been modernized to use CMake instead of self-written Python scripts. Our documentation (see the Build Guide) provides examples how to use it if you are not familiar with CMake.

Noteworthy changes since Baobab:

  • file formats:
    • there is now a generic reader (GraphIO::read()) recognizing many graph formats…
    • …and a generic writer (GraphIO::write()) based on file name extension
    • new support for file formats:
      • Graph6 (g6)
      • Sparse6 (s6)
      • Digraph6 (d6)
      • format of the DIMACS maximum flow challenge (DMF)
    • additional features and fixes in support for Chaco, DL, DOT, GDF, GEXF, GML, GraphML, STP, TLP
    • some readers (e.g., Rudy, GEXF, TLP) are stricter now (not accepting rubbish)
    • buggy XML parser is replaced by pugixml
    • dead OGML file format no longer supported
    • SVG printer is rewritten (bugfixes included)
    • readers with additional information (like edge weights or terminal nodes) are now available in Graph-only form
    • GraphAttributes can now be used for readers with edge weights
    • GraphIO functions based on filenames (instead of streams) are removed
  • layouts:
    • new LinearLayout, places nodes next to each other and draws edges as bows above the nodes
    • new NodeRespecterLayout, a force-directed layout respecting node shapes and sizes
    • SchnyderLayout can now compute the 1989’s paper version by using SchnyderLayout::setCombinatorialObjects(SchnyderLayout::CombinatorialObjects::Faces)
    • fixed setting of random seeds in FMMMLayout
    • LayoutStatistics changes:
      • new numberOfNodeOverlaps() method
      • new numberOfNodeCrossings() method
      • numberOfCrossings() can now return statistical measures on crossings
  • new graph generators:
    • customGraph() for quick generation of specific custom graphs
    • emptyGraph() for an empty graph or n isolated nodes
    • circulantGraph() for circulant graphs
    • completeKPartiteGraph() and completeBipartiteGraph()
    • randomSimpleConnectedGraph()
    • randomSimpleGraphByProbability()
    • randomGeometricCubeGraph() for random geometric graphs in a unit n-cube
    • randomRegularGraph() for random regular graphs
    • preferentialAttachmentGraph()
    • regularLatticeGraph()
    • randomWattsStrogatzGraph()
    • randomChungLuGraph()
    • randomGeographicalThresholdGraph()
    • randomWaxmanGraph()
    • generic randomEdgesGraph()
  • algorithms:
    • new algorithms:
      • s-t-planarity (planar and nodes s and t share a face):
        • isSTPlanar() to check if a graph is s-t-planar
        • planarSTEmbed() to embed a graph s-t-planarly
      • maximum flows in networks:
        • MaxFlowEdmondsKarp
        • MaxFlowGoldbergTarjan
        • MaxFlowSTPlanarDigraph
        • MaxFlowSTPlanarItaiShiloach
      • minimum s-t-cuts:
        • MinSTCutBFS
        • MinSTCutDijkstra
        • MinSTCutMaxflow (replaces old MinSTCut)
      • Steiner trees:
        • MinSteinerTreeDirectedCut
        • MinSteinerTreeDualAscent
        • MinSteinerTreeGoemans139
        • MinSteinerTreeKou
        • MinSteinerTreeMehlhorn
        • MinSteinerTreePrimalDual
        • MinSteinerTreeRZLoss
        • MinSteinerTreeShore
        • MinSteinerTreeTakahashi
        • MinSteinerTreeZelikovsky
        • SteinerTreePreprocessing
        • SteinerTreeLowerBoundDualAscent
      • planar subgraphs:
        • PlanarSubgraphTriangles
        • PlanarSubgraphTree
        • PlanarSubgraphCactus
        • PlanarSubgraphEmpty
        • MaximalPlanarSubgraphSimple
      • canonical orderings:
        • LeftistOrdering
        • BitonicOrdering
      • MaxAdjOrdering to compute one or all maximum adjacency orderings
      • AStarSearch for finding a shortest path between two given nodes
      • MaximalFUPS for the maximal feasible upward-planar subgraph based on a SAT formulation
      • EdgeIndependentSpanningTrees for k edge-independent spanning trees
      • simple algorithms regarding matchings, e.g., Matching::findMaximalMatching()
      • isTwoEdgeConnected() to check a graph for 2-edge-connectivity
      • isBipartite()
    • planar subgraph algorithms:
      • MaximumPlanarSubgraph now supports weighted edges
      • renamed BoyerMyrvoldSubgraph to PlanarSubgraphBoyerMyrvold
      • renamed FastPlanarSubgraph to PlanarSubgraphFast
    • NonPlanarCore:
      • can now process weighted graphs
      • new NonPlanarCore::retransform()
      • improved (returns simple graphs)
    • MinCostFlowReinelt is now cost-templated
    • CliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQR
    • renamed and deprecated some forest functions with misleading names
  • new basic functions (e.g., for convenience):
    • cast from AdjElement to corresponding node
    • AdjElement::isSource()
    • AdjElement::isBetween()
    • EdgeElement::nodes() function for for (node v : anEdge->nodes()) { ... }
    • EdgeElement::isAdjacent()
    • EdgeElement::getAdj()
    • EdgeElement::isParallelUndirected()
    • EdgeElement::isParallelDirected()
    • EdgeElement::isInvertedDirected()
    • operator() indexing (as synonym for operator[]) for NodeArrays and alike
    • operator== and operator!= for Array and ArrayBuffer
    • GraphCopy::isReversedCopyEdge()
    • Graph::searchEdge() with and without edge direction
    • GraphAttributes::nodeBoundingBoxes(boundingBoxes)
    • GraphAttributes::has() to check for attributes
    • GraphAttributes::transferTo{Original,Copy}() to replace GraphCopyAttributes class (which is removed)
    • GraphAttributes::all flag
    • GraphAttributes::point(node) instead of querying single x- and y-coordinates
    • hasNonSelfLoopEdges() to check whether a graph has edges which are not self-loops
    • removeSelfLoops()
    • Graph::insert()
    • graphUnion() to form a (disjoint and non-disjoint) union of two graphs
    • graphProduct() to form the product of two graphs using a given function, and its common use-cases:
      • cartesianProduct()
      • tensorProduct()
      • lexicographicalProduct()
      • strongProduct()
      • coNormalProduct()
      • modularProduct()
      • rootedProduct()
    • methods like Graph::chooseNode() or CombinatorialEmbedding::chooseFace() can now adhere to constraints
    • nodeDistribution() and degreeDistribution() as a special case
    • isRegular() to check if a graph is regular
    • GenericComparer replaces simple custom comparers by using lambdas
    • Graph::allNodes() and Graph::allEdges() for arrays
    • GraphAttributes::{x,y,z}Label() methods for the coordinates of a label relative to its node
    • Graph::HiddenEdgeSet replaces old and buggy (un)hiding mechanism for edges
    • new EpsilonTest class
  • geometry classes:
    • DPoint, IPoint are now template specializations of GenericPoint
    • DPolyline, IPolylineare now template specializations of newGenericPolyline`
    • new GenericLine and new GenericSegment represent (infinite) lines and (finite) line segments, respectively, replacing DLine being a mix of both (for double only)
    • improved intersection methods for these classes
    • removed: DVector (simply use DPoint), DScaler, DRound
    • new DRect::intersection()
    • fixed bug and generalized DPolyline::normalize()
    • new DIntersectableRect replaces IntersectionRectangle
  • Math utility changes:
    • Math is now a namespace instead of a static class
    • deprecate functions where one can use STL functions instead
    • template some functions such that they can be used, e.g., for ints and doubles
    • new harmonic(n) to compute the n-th harmonic number
    • new minValue(), maxValue(), sum(), mean(), standardDeviation()
    • new radiansToDegrees() and degreesToRadians()
    • new updateMin() and updateMax()
    • new nextPower2()
  • overhaul of ClusterGraphAttributes, now similar to GraphAttributes
  • removed classes Stack, StackPure, BoundedStack in favor of ArrayBuffer
  • removed OGDF file system functions (outside of scope of OGDF)
  • rather internal but noteworthy changes:
    • all include guards are replaced by #pragma once
    • all header files are now self-sufficient (i.e., have no other dependencies)
    • enum classes (scoped enums) are now used throughout OGDF instead of unscoped enums
    • cleanup of global namespace
    • some auxiliary classes are moved into sub-namespaces of ogdf
    • many std members imported into the ogdf namespace are now removed from it (e.g., swap, [io]stream, numeric_limits, cin, cout, endl, flush, ios)
    • rbegin() and rend() now work with reverse iterators instead of forward iterators
    • rbegin() is renamed to backIterator() where a reverse iterator does not make sense
    • removed ModuleOption (replaced by std::unique_ptr)
    • AdjacencyOracle can now trade memory usage versus speed by ignoring nodes of small degree
    • the graph size is no longer bounded by the stack size for the following algorithms:
      • biconnectedComponents()
      • isAcyclic()
      • isAcyclicUndirected()
      • isBiconnected()
      • isForest()
      • makeBiconnected()
      • strongComponents()
      • and all algorithms based on these functions
    • new safeForEach() and safeTestForEach() as simple functions to iterate over containers destructively (i.e., the current member of an iteration may be destroyed)
    • removed PreconditionViolatedException
  • many many bugfixes, code cleanup, improvements in code quality, documentation, and test coverage

This release contains (huge and small) contributions by Anuj Agarwal, Hendrick Brückler, Carsten Gutwenger, Daniel L. Lu, Denis Kurz, Ivo Hedtke, Jens Schmidt, Jöran Schierbaum, Karsten Klein, Kévin Szkudłapski, Łukasz Hanuszczak, Manuel Fiedler, Markus Chimani, Max Ilsen, Mirko Wagner, Mihai Popa, raven-worx on GitHub, Sebastian Semper, Stephan Beyer, Tilo Wiedera, and Yosuke Onoue.

snap-2018-03-28

Changes since last snapshot

  • new isBipartite() graph algorithm
  • graph generator changes:
    • simpler re-implementation of planarCNBGraph()
    • new graph generators:
      • preferential attachment graphs
      • regular lattice graphs
      • Watts-Strogatz graphs
      • Chung-Lu graphs
      • Geographical Threshold graphs
      • Waxman graphs
      • generic randomEdgesGraph()
  • layout changes:
    • new NodeRespecterLayout
    • SchnyderLayout can now compute the 1989’s paper version by using SchnyderLayout::setCombinatorialObjects(SchnyderLayout::CombinatorialObjects::Faces)
    • fix for FMMMLayout’s setting of random seeds
    • LayoutStatistics changes:
      • new numberOfNodeOverlaps() method
      • new numberOfNodeCrossings() method
      • numberOfCrossings() can now return statistical measures on crossings
  • file format changes:
    • removal of OGML reader and writer
    • the Chaco file reader is now stricter
    • improvements in GraphAttributes support for DOT, DL, GEXF, TLP, GraphML, GDF, GML
  • miscellaneous new methods:
    • Graph::insert(otherGraph)
    • EdgeElement::isAdjacent(otherEdge)
    • GraphAttributes::nodeBoundingBoxes(boundingBoxes)
    • MaxFlowModule::isFeasibleInstance()
    • statistical methods in Math, e.g., standardDeviation()
  • general (sometimes internal) changes:
    • rbegin() and rend() now work with reverse iterators instead of forward iterators
    • rbegin() is renamed to backIterator() where a reverse iterator does not make sense
    • improvements for internal types (e.g., add swap(), key_type, value_type for ArrayBuffer)
    • slight refactoring of big algorithm classes (e.g. for minimum Steiner trees)
    • improvements in test coverage, tests, and documentation
    • ban of DisjointSets copies
    • MinSTCut-related fixes
    • compilation under MingW should now work again
    • further minor bug fixes (also regarding COIN and CPLEX)
  • build system changes (CMake):
    • new system-wide installation including CMake’s find_package() support
    • test resource files are now compiled into the tests for independent tests
    • removal of NDEBUG-requirement for release modes in one-configuration environments
    • new doc/examples/check-build-mode.cpp example to test build configuration
    • bug fixes (e.g., PROJECT_BINARY_DIR instead of CMAKE_BINARY_DIR is used)

snap-2017-07-23

Changes since last snapshot

  • Graph6 format (with explicit header!) is added to the generic reader
    • graph algorithms:
    • new isTwoEdgeConnected() to check a graph for 2-edge-connectivity
    • renamed and deprecated some forest functions with misleading names
    • algorithms in graphalg/ShortestPathAlgorithms.h are now templates
  • graph generators:
    • new randomSimpleConnectedGraph() generator
    • made randomTree() faster
  • geometry classes:
    • DPoint, IPoint are now template specializations of GenericPoint
    • DPolyline, IPolyline are now template specializations of new
      GenericPolyline
    • new GenericLine and new GenericSegment represent (infinite) lines and
      (finite) line segments, respectively, replacing DLine being a mix
      of both (for double only); breaking changes!
    • improved intersection methods of these classes
    • removed: DVector (simply use DPoint), DScaler, DRound
    • new DRect::intersection()
    • fixed bug and generalized DPolyline::normalize()
  • very basic types:
    • removed classes Stack, StackPure, BoundedStack in favor of ArrayBuffer
    • made Skiplist usable with range-based for-loops
    • new == and != operators for Array and ArrayBuffer
    • add Graph::allNodes() and Graph::allEdges() for arrays
    • Math:
      • Math is now a namespace instead of a static class
      • new radiansToDegrees() and degreesToRadians()
      • new updateMin() and updateMax()
      • new nextPower2()
  • further removed classes:
    • MixedForceLayout
    • HyperGraph (but Hypergraph still exists)
    • EList, EFreeList, EStack
  • build system (CMake) changes:
    • new option OGDF_WARNING_ERRORS to treat (some) warnings as errors
    • new option OGDF_DEBUG_MODE to enable even more costly debugging
    • NOMINMAX is defined for Windows
    • thread affinity is set under Linux for Fast Multipole Embedder
  • general (sometimes internal) changes:
    • new GenericComparer, replaces simple custom comparers by using lambdas
    • many std things imported into the ogdf namespace are now removed from it
      (e.g., swap, [io]stream, numeric_limits, cin, cout, endl, flush, ios)
    • new safeForEach() and safeTestForEach() as simple functions to iterate
      over containers destructively (i.e., the current member of an iteration
      may be destroyed)
    • SubsetEnumerator is now less dependent on a particular List type
    • further code deduplications and simplifications
    • silenced many classes
    • replaced some List usages by ArrayBuffer where sufficient
    • initialized former uninitialized member variables
    • fixed implicit fallthrough warnings
    • improved readability and consistency in code
    • improved const-correctness
    • improved documentation
    • new tests and looooooots of bug fixes

Note that the minimum supported version for GCC changed to 4.9.2.

snap-2017-02-16

Changes since last snapshot

  • new graph generator customGraph() for quick generation of
    specific custom graphs
  • the graph size is no longer bounded by the stack size for the
    following algorithms:
    • biconnectedComponents()
    • strongComponents()
    • isForest()
  • new simple graph algorithm nodeDistribution() and
    degreeDistribution() as a special case
  • file format changes:
    • an STP reader for Graph (without edge weights and terminals)
      is now available, and it is included in the generic reader
    • the DMF reader and writer uses Graph and EdgeArray instead
      of EdgeWeightedGraph now
    • the DOT reader is now implemented non-recursively
      (which allows reading of large files while having low stack size)
    • Graph6, GDF, and TLP readers now clear the graph before reading
  • new minimum s-t-cut functionality:
    • MinSTCut module
    • MinSTCutMaxflow (replaces old MinSTCut)
    • MinSTCutBFS
    • MinSTCutDijkstra
  • new class DIntersectableRect replaces IntersectionRectangle
  • new PlanarSubgraphTree class as Maximum Planar Subgraph heuristic
  • bugfixes, code cleanup, improvement of code quality, C++11ifications,
    e.g., in:
    • OGDF initialization
    • the POOL_TS memory manager
    • GraphAttributes
    • GraphCopySimple
    • List, ListPure, SLIst, SListPure
    • DisjointSets
    • EdgeRouter
    • FMMMLayout
    • LCA
    • (fast_multipole_embedder::)ArrayGraph
    • (fast_multipole_embedder::)WSPD
    • the spring embedder force models
  • general (sometimes internal) changes:
    • removal of the doDestruction() function template
    • removal of a lot of shadowing of variables
    • fixes of one-definition-rule violations that led
      to weird problems
    • enum classes (scoped enums) are now used throughout OGDF
      instead of unscoped enums
    • typedefs are replaced by using for improved readability
      and better flexibility
    • declaration of several constructors as explicit to
      avoid implicit conversion where it is wrong
    • some auxiliary classes are moved into sub-namespaces and
      their files are often moved into sub-directories
    • slightly improved consistency in documentation
    • slightly improved code style consistency

There are also CMake changes. The default target only compiles the OGDF (and its dependencies). There are new targets “tests” and “examples” doing the obvious, and a new target “build-all” that also compiles tests and examples. Separate test targets are renamed from foo_bar_test to test-foo-bar.

snap-2016-12-05

Changes since last snapshot

  • new graph generators:
    • emptyGraph() for an empty graph or n isolated nodes
    • randomGeometricCubeGraph() for random geometric graphs in a unit n-cube
    • randomRegularGraph() for random regular graphs
  • revised planar subgraph algorithms:
    • new MaximalPlanarSubgraphSimple adds new planarity-ensuring edges in a given planar subgraph greedily
    • MaximumPlanarSubgraph (ILP-based algorithm) now supports weighted edges
    • PlanarSubgraphBoyerMyrvold is a maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test
    • new PlanarSubgraphCactus implements the 7/18-approximation algorithm by Călinescu et al.
    • new PlanarSubgraphEmpty is a dummy class
    • PlanarSubgraphFast computes a planar subgraph using PQ-trees
    • some of these classes are templates for different types of cost
  • miscellaneous new functionality:
    • AdjElement::isSource(), AdjElement::isBetween()
    • BoyerMyrvold::transform()
    • EdgeElement::getAdj()
    • methods like Graph::chooseNode() or CombinatorialEmbedding::chooseFace() can now adhere to constraints
    • GraphCopy::isReversedCopyEdge()
    • Math::harmonic(n) to compute the n-th harmonic number
    • NonPlanarCore can now process weighted graphs
    • NonPlanarCore::retransform()
    • isRegular() to check if a graph is regular
  • the graph size is no longer bounded by the stack size for the following algorithms:
    • isAcyclic()
    • isAcyclicUndirected()
    • isBiconnected()
    • makeBiconnected()
    • and all algorithms based on these functions
  • as usual: bugfixes, (a little) code cleanup and improvement of code quality, e.g., in
    • OGDF initialization
    • AStarSearch
    • CombinatorialEmbedding
    • DualGraph
    • Graph
    • GraphCopy
    • GraphIO::write{GML,OGML,LEDA,GEXF,GDF,TLP,DL,DOT,GraphML}
    • LCA
    • Math
    • MaxFlowSTPlanarItaiShiloach
    • MaximumCPlanarSubgraph
    • NonPlanarCore
    • SubgraphPlanarizer
    • VariableEmbeddingInserter
    • (internal) heap data structures
    • documentation
  • improved test coverage
  • and some further C++11ification.

Baobab

Today, we released the new version v2015.05 (Baobab) of OGDF! The release introduces various new algorithms and modules but also improves usability and elegance. To accomplish the latter, some changes had to be made that break compatibility to Sakura. Also, COIN-OR and ABACUS are now included in the OGDF package to make every feature work out-of-the-box.

In parallel to the release of Baobab, we uploaded a new snapshot of OGDF. It marks the start in using C++11 features and the CMake build system. Note that you will need much more recent compilers to compile the snapshot than you would need for the Baobab release or former releases.

Highlights

  • COIN-OR and ABACUS are integrated in the package for easier installation
  • improvements to GraphAttributes class
    • restructuring
    • more consistent naming scheme
    • improved color management (Color class instead of strings)
    • basic 3d support
  • new LayoutStandards: changeable default parameters (sizes, distances, colors) that allow more comparable drawings
  • basic support for hypergraphs (Hypergraph class)
  • reader and writer for fileformats
    • new support for DL, DOT, GDF, GEXF, GraphML, Tulip graph formats
    • new support for Bench and PLA hypergraph formats
    • improved GML and OGML parser
    • reading and writing files is now handled by GraphIO class
  • new layered crossing minimization for Sugiyama algorithm: grid sifting and global sifting heuristics (GridSiftingGlobalSifting; Bachmaier et al, 2011)
  • new EmbedderOptimalFlexDraw class for bend minimization in planar, orthogonal drawings (Bläsius et al, 2012)
  • new force-directed layout BertaultLayout that preserves edge-crossing properties (Bertault, 2000)
  • new parallelized version of FastPlanarSubgraph
  • new methods for some (restricted) upward planarity problems (UpwardPlanarity class)
  • new classes for stress majorization (StressMinimization), pivot multi-dimensional scaling (PivotMDS)
  • revised code for edge insertion into planar graphs (EdgeInsertionModuleFixedEmbeddingInserterVariableEmbeddingInserter*, SubgraphPlanarizer classes)
  • new Graph::CCsInfo class to store information about connected components
  • new LCA class to compute lowest common ancestors in arborescences with linear preprocessing time and constant query time (Bender and Farach-Colton, 2000)
  • new Voronoi class to compute Voronoi regions in graphs
  • new graph generators, e.g., randomSeriesParallelDAG()
  • new simple graph algorithms, e.g., makeBimodal() or makeMinimumSpanningTree()
  • and as usual: bugfixes, (a little) code cleanup, and improvement of code quality (like const-correctness)