Author: admin

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 EmbedderMaxFace, EmbedderMaxFaceLayers, EmbedderMinDepth, EmbedderMinDepthMaxFace, EmbedderMinDepthMaxFaceLayers.
• 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).

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).
• SList, SListPure: 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
• ScalingLayout, PreprocessorLayout: 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_2, pi_4, and two_pi.

Bug Fixes

• Fixed a bug in GraphAttributes: writeGML 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).

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 Thread, CriticalSection, Mutex, Barrier.
• 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): EdgeCoverMerger, IndependentSetMerger, LocalBiconnectedMerger, MatchingMerger, RandomMerger, SolarMerger.
  • InitialPlacer module (placement): BarycenterPlacer, CirclePlacer, MedianPlacer, RandomPlacer, SolarPlacer, ZeroPlacer.
• 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 PlanarAugmentationFix, EmbedderMaxFace, EmbedderMaxFaceLayers, EmbedderMinDepth, EmbedderMinDepthMaxFace, EmbedderMinDepthMaxFace, EmbedderMinDepthPiTa, PlanarizationLayout.
• Fixed bug with copy constructor of graph arrays (NodeArray, EdgeArray 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++.

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 Array, ArrayBuffer, BoundedQueue, BoundedStack, MinHeap, 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.
  • PlanarStraightLayout, PlanarDrawLayout, 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 (ArrayBuffer, BinaryHeap, BoundedQueue, BoundedStack, MinHeap, Top10Heap).
  • 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 release, cleanrelease, etc. (instead of release_all, release_clean).
  Available make targets are now debug, saferelease (-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.

The first public version of OGDF is released.