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

Version History

v. 2015.05 (Baobab)

Release Date: 2015-05-30

Download: ogdf.v2015.05.zip [5.4 MB]

Significant Changes:

  • 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 (GridSifting, GlobalSifting; 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 (EdgeInsertionModule, FixedEmbeddingInserter, VariableEmbeddingInserter*, 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)

For a list of compatibility-breaking changes and how to deal with them, see the Porting Guide.

Picture: CC BY-SA 3.0 Martin Kraft via Wikimedia Commons

v. 2012.07 (Sakura)

Release Date: 2012-07-18

Download: ogdf.v2012.07.zip [2.06 MB]

Highlights:

  • Improved compiler support:
    • Support for the latest compiler versions added (gcc 4.7, Visual Studio 2012).
    • Support for new compilers / platforms: MinGW on Windows and LLVM/clang on Linux.
    • Adjusted generated project files for Visual Studio, so that source files can now be compiled in parallel.
    • Support for shared libraries (DLLs for Visual Studio 2008-2012, shared libraries for gcc, LLVM/clang).
  • Clean-up of classes for planarity testing and embedding:
    • PlanarModule has been renamed to BoothLueker.
    • Introduced a base class PlanarityModule for planarity testing and embedding and adjusted the interface of BoothLueker and BoyerMyrvold.
    • extended_graph_alg.h now contains simple functions for planarity testing and embedding.
  • Changed the interface of embedder modules from PlanRep to Graph. PlanarStraightLayout and PlanarDrawLayout now have a module option for the embedder.
  • Various important bugfixes:
    • Fixed crashes when compiling with gcc and -O2 or -O3. By default, OGDF release builds now use -O2.
    • Fixed crashes of some embedder modules when the input graph contained blocks just consisting of two parallel edges.
    • Fixed a bug in the special handling of isolated nodes when minimizing crossings with SugiyamaLayout. Previous code did not work as intended, the revised code can decrease the number of crossings in many cases.

For a complete list of changes, please refer to Sakura's change-log.

Picture: CC0 Hans Braxmeier

v. 2012.05 (Madrona)

Release Date: 10.05.2012

Download: ogdf.v2012.05.zip [2.07 MB]

Highlights:

  • First implementation of the approximation algorithm for multi-edge insertion (class MultiEdgeApproxInserter).
  • New planar straight-line layout methods: de Fraysseix, Pach, Pollack (class FPPLayout) and Schnyder (class SchnyderLayout).
  • Various new modules to be used with SugiyamaLayout:
    • New two-layer crossing minimization heuristics based on sifting (class SiftingHeuristic) and greedy approaches (classes GreedyInsertHeuristic and GreedySwitchHeuristic).
    • New ranking module based on the Coffman-Graham algorithm (class CoffmanGrahamRanking).
    • New module for coordinate assignment based on the algorithm by Brandes and Köpf (class FastSimpleHierarchyLayout).
  • New Union/Find data structure (class DisjointSets).
  • Support for some additional file formats (GD Challenge format, Chaco format).
  • Further graph generators ((toroidal) grid graphs, Petersen graphs, planar graphs).

For a complete list of changes, please refer to Madrona's change-log.

Picture: CC BY-SA 3.0 Walter Siegmund

v. 2010.10 (Sassafras)

Release Date: 21.10.2010

Download: ogdf.v2010.10.zip [2.10 MB]

Highlights:

  • Completely revised memory management; pool-memory allocator now supports thread-safe allocation.
  • Basic multithreading support for OGDF algorithms.
  • New class System provides methods for accessing system-dependent information and functionality (processor features, memory usage, file system).
  • New hierarchical graph layout method using upward planarization (class UpwardPlanarization); outperforms traditional Sugiyama-based methods with respect to crossings by far.
  • New multilevel layout algorithm (FastMultipoleMultilevelEmbedder), based on the multipole method, well-separated pair decomposition, and a new quadtree space partitioning (Martin Gronemann's Diploma thesis); makes use of SSE and multicore processors and is significantly faster than FMMMLayout.
  • New modular framework for multilevel graph layout (class ModularMultilevelMixer) with various options for coarsening, placement, and single-level layout.
  • New force-directed layout algorithms: Kamada-Kawai (class SpringEmbedderKK) and stress majorization (class StressMajorization).
  • New layout algorithms for directed graphs: DominanceLayout and VisibilityLayout.
  • Implementation of Prims' algorithm for minimum spanning tree computation.
  • Added support for OGML graph file format.
  • Exact algorithms for computing maximum planar and maximum c-planar subgraphs (classes MaximumPlanarSubgraph and MaximumCPlanarSubgraph).
  • OGDF can now be compiled as DLL under Windows.
  • Support for Visual Studio 2010 and latest g++ compilers.

For a complete list of changes, please refer to Sassafras' change-log.

v. 2007.11 (Bubinga)

Release Date: 23.11.2007

Download: ogdf.v2007.11.zip [1.61 MB]

Highlights:

  • New algorithm for planar augmentation with fixed embedding.
  • The planar drawing algorithms Planar-Straight, Planar-Draw, and Mixed-Model can now be called with a given planar embedding.
  • New class DualGraph representing the geometric dual graph of a combinatorial embedding.
  • Consistent interface for planarization layout that allows to call with GraphAttributes.
  • Sugiyama layout now produces drawings with given node ranks that are also respected across different connected components.
  • Hashing functions can now be passed as template parameters; the implementation of two-dimensional hash-arrays has been revised and allows now using different types for each index.
  • Optional template parameter for index type of array-based classes.
  • Unified naming conventions and interfaces.
  • Improved build system for Visual Studio, including support for compiling with Osi Coin and creating projects for Visual Studio 2003.
  • Significantly improved documentation.

For a complete list of changes, please refer to Bubinga's change-log.

v. 2007.09 (Jacaranda)

Release Date: 19.09.2007

Download: ogdf.v2007.09_a.zip [1.47 MB] (includes all hotfixes)

Hotfixes: hotfix-v2007.09_a.zip [7 KB] (released 08.10.2007)

Changes in Hotfix v2007.09_a:

  • Bug fix in LPSolver_coin.cpp: Wrong LP passed to Coin
  • Bug fix in coin.cpp: Pragma #warning not compatible with Visual C++

To install a hotfix unzip the hotfix in the root directory of the OGDF installation and recompile OGDF.

 
tech/versions.txt · Last modified: 2015/05/31 00:37 by stephan
This page is driven by DokuWiki