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

Changelog v. 2012.05 (Madrona)

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).
tech/changes2012_05.txt · Last modified: 2014/12/16 12:20 (external edit)
This page is driven by DokuWiki