Sakura

Today, we released the new version v.2012.07 (Sakura) of OGDF! This release is mainly a clean-up and bug-fix release, bringing support for new compilers and fixing some annoying bugs.

Highlights

  • Improved compiler support:
    • Support for the latest compiler versions (gcc 4.7, Visual Studio 2012) and new compilers (MinGW, LLVM/clang).
    • 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.
  • 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.

Detailed Changelog

New Features

  • Clean-up of classes for planarity testing and embedding:
    • PlanarModule has been renamed to BoothLueker; both have been adjusted to the new interface specified by PlanarityModule.
    • Introduced a base class PlanarityModule specifiying the interface for planarity testing and embedding.
    • Derived BoothLueker and BoyerMyvold from PlanarityModule and adjusted their interface.
    • Added new functions for planarity testing and embedding to extended_graph_alg.h, making it easier to call this functionality: isPlanar()planarEmbed()planarEmbedPlanarGraph()
    • Remark: If you used PlanarModule for planarity testing or embedding in your programs, you have to rewrite your code! The simplest way is to use the above functions from extended_graph_alg.h instead.
  • Changed the interface of embedder modules from PlanRep to Graph.
  • Added module option for the embedder to PlanarStraightLyout and PlanarDrawLayout.

Minor Modifications

  • renamed some graph load functions (for consistent naming):
    • loadRomeGraphStream → loadRomeGraph
    • loadChacoStream → loadChacoGraph
    • loadSimpleGraphStream → loadSimpleGraph
    • loadBenchHypergraphStream → loadBenchHypergraph
  • made Array2D::det() method const
  • moved definition of MemElem to MallocMemoryAllocator
  • replaced ogdf’s min/max by std::min/std::max
  • renamed eLabelTyp → eLabelType
  • made destructor of class Thread virtual

Bug Fixes

  • 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. Affected where EmbedderMaxFaceEmbedderMaxFaceLayersEmbedderMinDepthEmbedderMinDepthMaxFaceEmbedderMinDepthMaxFaceLayers.
  • 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.
  • Fixed a bug in makeConnected(): now also works for empty graphs (just returns)
  • Added missing header files for SteinLibParser.
  • Corrected various errors when compiling HyperGraph.h.

Build System

  • Added support for gcc 4.7.
  • Added support for Visual Studio 2012.
  • Added support for MinGW on Windows (just 32-bit MinGW version).
  • Added support for LLVM/clang on Linux.
  • Adjusted generated project files for Visual Studio, so that source files can now be compiled in parallel.
  • OGDF can now be built as DLL with Visual Studio 2008-2012
  • OGDF can now be built as a shared library on Linux with gcc and LLVM/clang
  • Clean-up of OGDF’s main directory:
    • moved project templates to the subdirectory config
    • moved OGDF’s doxygen configuration file ogdf-doxygen.cfg to the subdirectory doc
  • Documentation adjusted to latest doxygen version (1.8.1.1).

Madrona

Today, we released the new version v2012.05 (Madrona) of OGDF! This release brings various new algorithms and modules, as well as bug fixes and adaptions for current compilers.

Highlights

  • First implementation of the approximation algorithm for multi-edge insertion (class MultiEdgeApproxInserter).
  • New planar straight-line layout methods: de Faysseix, Pack, 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).

Detailed Changelog

New Features

  • New edge insertion module (MultiEdgeApproxInserter) implementing an approximation algorithm for multi-edge insertion.
  • New planar straight-line layout algorithms:
    • FPPLayout implements the algorithm by de Fraysseix, Pach, Pollack.
    • SchnyderLayout implements the algorithm by Schnyder.
  • New ranking module (CoffmanGrahamRanking) which allows to limit the number of nodes on a layer.
  • New two-layer crossing minimization heuristics:
    • GreedyInsertHeuristic
    • GreedySwitchHeuristic
    • SiftingHeuristic
  • New module for coordinate assignment (FastSimpleHierarchyLayout) in Sugiyama’s framework implementing the algorithm by Brandes and Köpf.
  • New Union/Find data structure (DisjointSets).
  • New force-directed layout algorithm (SpringEmbedderFRExact): Fruchterman/Reingold spring-embedder with exact force calculations; also features OpenMP and SSE3 parallelization.
  • New functions for parsing file formats:
    • loadChallengeGraph()saveChallengeGraph(): read and write graphs in GD Challenge file format.
    • loadChacoGraph: read graph in Chaco (graph partitioning software) file format.
    • loadEdgeListSubgraph()saveEdgeListSubgraph(): read and write graphs with specified subgraphs in a simple file format (used in experimental evaluation of edge insertion algorithms by Chimani and Gutwenger).
    • SteinLibParser: reads instances from SteinLib.
  • New graph generators:
    • planarConnectedGraph(): creates a connected (simple) planar (embedded) graph.
    • gridGraph(): creates a (toroidal) grid graph.
    • petersenGraph(): creates a generalized Petersen graph.

Minor Modifications

  • changeDir() now returns a boolean value (true = successful).
  • SListSListPure: added search() method.
  • Renamed ModularMultilevelMixerLayout.h to ModularMultilevelMixer.h (since it defines class ModularMultilevelMixer).
  • ClusterGraphAttributes: made method readClusterGraphGML() private, since it should not be called by a user.
  • CrossingsMatrix: changed return type of operator() from double to int
  • ScalingLayoutPreprocessorLayout: proper usage of module options.
  • Moved definitions of constants for pi and e to class Math and renamed euler to e; added definitions of constants pi_2pi_4, and two_pi.

Bug Fixes

  • Fixed a bug in GraphAttributeswriteGML now uses edge arrow attributes if specified.
  • Fixed bug in GmlParser: Access to uninitialized pointer in destructor if file could not be opened in constructor.
  • ModularMultilevelMixer: implemented correct usage of module options; fixes a potential memory leak.
  • Cluster-Sugiyama: fixed bug in ExtendedNestingGraph::tryEdge() (integer overflow); reimplemented computation of “levels” for fast acyclicity testing such that levels are < 2n.
  • DynamicPlanarSPQRTree.h: fixed include statement (missing subdirectory decomposition).
  • Fixed a 0-pointer exception in GraphListBase::swap() (wrong swap-function was called).

Build System

  • Documentation adjusted to latest doxygen version (1.8.0).