Sassafras

Today, we released the new version v2010.10 (Sassafras) of OGDF! This release brings various new algorithms and features.

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.

Detailed Changelog

New Features

  • Completely revised memory management, with a new thread-safe pool-memory allocator. OGDF provides now three allocators (which can be selected with compiler predefines):
    • thread-safe pool allocator (OGDF_MEMORY_POOL_TS; usually the deafult),
    • non-thread-safe pool allocator (OGDF_MEMORY_POOL_NTS), and
    • ordinary malloc/free (OGDF_MEMORY_MALLOC_TS).
  • Basic, platform-independent multithreading support for OGDF algorithms; new classes ThreadCriticalSectionMutexBarrier.
  • New class System provides methods for accessing system-dependent information and functionality (processor features, memory usage, file system).
  • New layout algorithms for directed (hierarchical) graphs:
    • DominanceLayout, based on dominance layout of st-digraphs.
    • VisibilityLayout, based on computation of a visibility representation.
  • New hierarchical graph layout method using upward planarization (class UpwardPlanarization); implements the algorithm by Chimani, Gutwenger, Mutzel and Wong. Outperforms traditional Sugiyama-based methods with respect to number of crossings by far. Uses module options for upward planarization and layout:
    • UpwardPlanarizerModule: its implementation SubgraphUpwardPlanarizer applies a 2-phase approach: first compute a feasible upward planar subgraph (FUPSModule with implementation FUPSSimple), then insert remaining edges (UpwardEdgeInserterModule with implementation FixedEmbeddingUpwardEdgeInserter).
    • UPRLayoutModule: implementation LayerBasedUPRLayout which makes use of hierarchy layout modules from the Sugiyama framework.
  • New force-directed layout algorithms:
    • Kamada-Kawai (class SpringEmbedderKK)
    • stress majorization (class StressMajorization).
  • 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.
    • MultilevelBuilder module (coarsening): EdgeCoverMergerIndependentSetMergerLocalBiconnectedMergerMatchingMergerRandomMergerSolarMerger.
    • InitialPlacer module (placement): BarycenterPlacerCirclePlacerMedianPlacerRandomPlacerSolarPlacerZeroPlacer.
  • Implementation of Prims’ algorithm for minimum spanning tree computation (function computeMinST in ogdf/basic/extended_graph_alg.h.
  • Added support for OGML graph file format:
    • class OgmlParser implements a parser for OGML-files;
    • methods writeOGML and readClusterGraphOGML in ClusterGraphAttributes provide reading and writing of OGML files.
  • Exact algorithm for computing a maximum planar subgraph (class MaximumPlanarSubgraph); requires COIN and ABACUS.
  • Exact algorithm for computing a maximum c-planar subgraph (class MaximumCPlanarSubgraph); requires COIN and ABACUS.

Minor Modifications

  • GraphAttributes provides now a flag indicating if the graph is directed or not (default is true): methods directed for getting / setting, support in reading and writing GML files (readGML and writeGML).
  • Hash values are now of type size_t for providing better compatibility with 64-bit systems.
  • Default parameters of GEMLayout revised.
  • ClusterPlanarizationLayout now allows to pass edge weights in its call, which are used for computing a c-planar subgraph (edges with low weight are preferred).
  • Clarified Comparer interfaces:
    • Class Comparer<E> renamed to VComparer<E> (since it relies on virtual functions).
    • Added the macros OGDF_AUGMENT_COMPARER and OGDF_AUGMENT_STATICCOMPARER to allow easy generation of comparers with full interfaces.
    • Added StdComparer (standard comparers) and TargetComparer (for comparing targets of pointers).
  • Array::grow() allows now to enlarge an array with empty index set.
  • PlanarizationLayout: changed default planar subgraph to FastPlanarSubgraph.
  • Changed return type of BCTree::findPathBCTree() to pointer (instead of reference) to reflect the fact that the returned object has been allocated with new.
  • isConnected()makeConnected(): improved performance by replacing recursive with iterative implementation.
  • New, more efficient implementation of list-based stacks.

Bug Fixes

  • Fixed bug in SugiyamaLayout: possibly incorrect setting of number of crossings if there are several connected components and arrangeCCs = true.
  • Fixed bug in BoyerMyrvold: incorrect embedding of self-loops.
  • Fixed memory leaks in PlanarAugmentationFixEmbedderMaxFaceEmbedderMaxFaceLayersEmbedderMinDepthEmbedderMinDepthMaxFaceEmbedderMinDepthMaxFaceEmbedderMinDepthPiTaPlanarizationLayout.
  • Fixed bug with copy constructor of graph arrays (NodeArrayEdgeArray etc.): crashed if copied array was not initialized for a graph.
  • Fixed bug with Hierarchy: memory leaks occurred when using initByNodes().
  • Revised compiler condition for systems providing only 15 random bits with rand() function; fixes a non-termination bug with FMMMLayout on Solaris/SPARC.
  • Fixed a bug in makeConnected().
  • Fixed a memory leak in LPSolver_coin.

Build System

  • Added support for Visual Studio 2010, which introduces an new project format (.vcxproj). For creating such a project, use makeVCXProj.py (instead of makeVCProj.py). At the moment, there is just one possible template file for VS 2010 (ogdf.vcxproj.vs2010.template; which is the default).
  • Added support for compiling OGDF as DLL under Windows (currently VS 2005 only); simply select project template ogdf.dll.vcproj.vs2005.template in makeVCProj.config.
  • Added support for latest g++ compilers (4.1.x – 4.4.x) on Linux and Mac OS X.
  • Windows only: OGDF now requires to also link against Psapi.lib.
  • g++ on Linux/Mac only: OGDF now requires to link against pthreads; add option -pthread when compiling and linking with g++.

Bubinga

The second public release of OGDF has been released today. This release focuses on improved usability, but also contains new functionality.

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.

Detailed Changelog

New Features

  • Additional (optional) template parameter for used size/index type in ArrayArrayBufferBoundedQueueBoundedStackMinHeap, and Top10Heap.
  • Specification of hash function as (optional) template parameter in Hashing and HashArray.
    • The default hash function is implemented by DefHashFunc<K> (instead of function hash()); this can be extended to further types by specializing DefHashFunc.
  • Revised implementation of HashArray2D.
    • Supports now different types for each index.
    • The hash-function can be passed as (optional) template parameter.
    • entry(const I&,const I&) → operator()(const I1&,const I2&)
    • Iterators: key(I&,I&) → key1() and key2()
  • The new class DualGraph represents the geometric dual graph of a combinatorial embedding.
  • New augmentation algorithm for planar biconnected augmentation with fixed embedding (class PlanarAugmentationFix).
  • Planar drawing algorithms now implement a call for drawing with a given planar embedding.
    • The base class PlanarGridLayoutModule defines this interface.
    • PlanarStraightLayoutPlanarDrawLayout, and MixedModelLayout implement this interface.
  • The planarization layout can now be called with GraphAttributes like other layout algorithms; setting/getting of options made consistent with ogdf naming style. The following changes were done:
    • UMLPlanarizationLayout → PlanarizationLayout
    • UMLLayoutModule inherits from LayoutModule
    • PlanarizationLayout has now a call(GraphAttributes&)
    • setCliqueSize(int) → minCliqueSize(int)
    • added int minCliqueSize()
    • preProcessCliques(bool) → preprocessCliques(bool)
    • added bool preprocessCliques()
  • SugiyamaLayout has a new option arrangeCCs (deciding whether components are laid out separately and arranged afterwards) and a new module option packer (for arranging connected components). Setting arrangeCCs to false and passing node ranks directly allows to get a layout which truly respects the layering across all connected components.
  • LongestPathRanking has a new option optimizeEdgeLength; setting this option to false gives a longest-path ranking as known from the literature; default is true which is same behavior as before (performs additional optimization for reducing edge lengths).

Minor Modifications

  • Unified interface for containers (ArrayBufferBinaryHeapBoundedQueueBoundedStackMinHeapTop10Heap).
    • size() returns the current number of elements in the container.
    • capacity() returns the maximal number of elements that can be stored in the container (if applicable).
    • empty() returns true if the container contains no elements.
    • full() returns true if the current number of elements has reached the capacity (if applicable).
    • clear() removes all elements from the container.
  • Unified naming conventions for array classes:
    • Array2 → Array2D
    • HashingArray → HashArray
    • TwoDHashArray → HashArray2D
    • TwoDHashIterator → HashConstIterator2D
  • Usage of size_t instead of int in:
    • BendString::BendString(char,size_t)
    • BendString::operator[](size_t)
    • BendString::size()
    • BendString::set(char,size_t)
    • BendString::init(char,size_t)
    • String::String(size_t,const char *)
    • String::length()
    • String::operator[](size_t)
  • Removed String::operator const char *(); use the new method String::cstr() instead.
  • Usage of const String& instead of const char* in:
    • CliqueFinder::writeGraph(Graph &, NodeArray<int> &, const String &)
    • GraphAttributes::readGML(Graph &, const String &)
    • GraphAttributes::writeGML(const String &)
    • GraphAttributes::readXML(Graph &G, const String &fileName)
    • GraphAttributes::writeXML(const String &, const char*, const char*)
    • GraphAttributes::readRudy(Graph &, const String &)
    • GraphAttributes::writeRudy(const String &)
    • String::compare(const String &,const String &)
  • GraphAttributes return now default values for type(node) and type(edge) even if the respective arrays are not initialized.
  • Renamed GraphStructure → GraphObserver.
  • The Methods assignNode()unassignNode(), and removeNodeAssignment() in ClusterGraph are now private (not meant for public use).
  • Added constructor PlanRepUML(const GraphAttributes&).
  • Changed default augmenter of PlanarStraightLayout and PlanarDrawLayout to PlanarAugmentation.
  • Removed OrthoFormerUML (obsolete); renamed OrthoFormerGENERIC → OrthoShaper.
  • Renamed UMLOrthoLayout → OrthoLayout and UMLPlanarLayoutModule → LayoutPlanRepModule.
  • Revised design of ClusterPlanarizationLayout:
    • ClusterPlanarizationLayout does not inherit from UMLLayoutModule anymore.
    • Removed unsupported call methods.
    • Removed (unused) module options subgraph and inserter.
    • Changed type of planarLayouter to new module type LayoutClusterPlanRepModule.
    • Changed base class of ClusterOrthoLayout to LayoutClusterPlanRepModule.
    • Renamed ClusterOrthoFormer to ClusterOrthoShaper
  • Renamed ClustererBase → ClustererModule and moved header ClustererModule.h to ogdf/module/.
  • Logging output of Coin Osi solver turned off by default (previous version produced some output in debug builds).

Bug Fixes

  • Fixed possible rounding error in LPSolver::checkFeasibility().
  • Fixed C++ template syntax for print() function of BoundedQueue.
  • Removed ”LPSolver::” in declaration of LPSolver::checkFeasibility() (did not compile with some g++ versions).

Build System

  • Visual Studio project file: Added configuration file makeVCProj.config for specifying project template and optional settings for LP-solver.
  • Support for Visual Studio 2003 (Visual C++ 7.1) by selecting ogdf.vcproj.vs2003.template as project template.
  • Linux/g++ makefile: Build targets renamed to releasecleanrelease, etc. (instead of release_allrelease_clean).
    Available make targets are now debugsaferelease (-O0), and release (-O1); default is release which yields a typical performance gain over the previous release (with -O0) by a factor of 2.5−12. We discourage using -O2 or -O3 with g++, since this is not stable.