snap-2018-03-28

Changes since last snapshot

  • new isBipartite() graph algorithm
  • graph generator changes:
    • simpler re-implementation of planarCNBGraph()
    • new graph generators:
      • preferential attachment graphs
      • regular lattice graphs
      • Watts-Strogatz graphs
      • Chung-Lu graphs
      • Geographical Threshold graphs
      • Waxman graphs
      • generic randomEdgesGraph()
  • layout changes:
    • new NodeRespecterLayout
    • SchnyderLayout can now compute the 1989’s paper version by using SchnyderLayout::setCombinatorialObjects(SchnyderLayout::CombinatorialObjects::Faces)
    • fix for FMMMLayout’s setting of random seeds
    • LayoutStatistics changes:
      • new numberOfNodeOverlaps() method
      • new numberOfNodeCrossings() method
      • numberOfCrossings() can now return statistical measures on crossings
  • file format changes:
    • removal of OGML reader and writer
    • the Chaco file reader is now stricter
    • improvements in GraphAttributes support for DOT, DL, GEXF, TLP, GraphML, GDF, GML
  • miscellaneous new methods:
    • Graph::insert(otherGraph)
    • EdgeElement::isAdjacent(otherEdge)
    • GraphAttributes::nodeBoundingBoxes(boundingBoxes)
    • MaxFlowModule::isFeasibleInstance()
    • statistical methods in Math, e.g., standardDeviation()
  • general (sometimes internal) changes:
    • rbegin() and rend() now work with reverse iterators instead of forward iterators
    • rbegin() is renamed to backIterator() where a reverse iterator does not make sense
    • improvements for internal types (e.g., add swap(), key_type, value_type for ArrayBuffer)
    • slight refactoring of big algorithm classes (e.g. for minimum Steiner trees)
    • improvements in test coverage, tests, and documentation
    • ban of DisjointSets copies
    • MinSTCut-related fixes
    • compilation under MingW should now work again
    • further minor bug fixes (also regarding COIN and CPLEX)
  • build system changes (CMake):
    • new system-wide installation including CMake’s find_package() support
    • test resource files are now compiled into the tests for independent tests
    • removal of NDEBUG-requirement for release modes in one-configuration environments
    • new doc/examples/check-build-mode.cpp example to test build configuration
    • bug fixes (e.g., PROJECT_BINARY_DIR instead of CMAKE_BINARY_DIR is used)

snap-2017-07-23

Changes since last snapshot

  • Graph6 format (with explicit header!) is added to the generic reader
    • graph algorithms:
    • new isTwoEdgeConnected() to check a graph for 2-edge-connectivity
    • renamed and deprecated some forest functions with misleading names
    • algorithms in graphalg/ShortestPathAlgorithms.h are now templates
  • graph generators:
    • new randomSimpleConnectedGraph() generator
    • made randomTree() faster
  • geometry classes:
    • DPoint, IPoint are now template specializations of GenericPoint
    • DPolyline, IPolyline are now template specializations of new
      GenericPolyline
    • new GenericLine and new GenericSegment represent (infinite) lines and
      (finite) line segments, respectively, replacing DLine being a mix
      of both (for double only); breaking changes!
    • improved intersection methods of these classes
    • removed: DVector (simply use DPoint), DScaler, DRound
    • new DRect::intersection()
    • fixed bug and generalized DPolyline::normalize()
  • very basic types:
    • removed classes Stack, StackPure, BoundedStack in favor of ArrayBuffer
    • made Skiplist usable with range-based for-loops
    • new == and != operators for Array and ArrayBuffer
    • add Graph::allNodes() and Graph::allEdges() for arrays
    • Math:
      • Math is now a namespace instead of a static class
      • new radiansToDegrees() and degreesToRadians()
      • new updateMin() and updateMax()
      • new nextPower2()
  • further removed classes:
    • MixedForceLayout
    • HyperGraph (but Hypergraph still exists)
    • EList, EFreeList, EStack
  • build system (CMake) changes:
    • new option OGDF_WARNING_ERRORS to treat (some) warnings as errors
    • new option OGDF_DEBUG_MODE to enable even more costly debugging
    • NOMINMAX is defined for Windows
    • thread affinity is set under Linux for Fast Multipole Embedder
  • general (sometimes internal) changes:
    • new GenericComparer, replaces simple custom comparers by using lambdas
    • many std things imported into the ogdf namespace are now removed from it
      (e.g., swap, [io]stream, numeric_limits, cin, cout, endl, flush, ios)
    • new safeForEach() and safeTestForEach() as simple functions to iterate
      over containers destructively (i.e., the current member of an iteration
      may be destroyed)
    • SubsetEnumerator is now less dependent on a particular List type
    • further code deduplications and simplifications
    • silenced many classes
    • replaced some List usages by ArrayBuffer where sufficient
    • initialized former uninitialized member variables
    • fixed implicit fallthrough warnings
    • improved readability and consistency in code
    • improved const-correctness
    • improved documentation
    • new tests and looooooots of bug fixes

Note that the minimum supported version for GCC changed to 4.9.2.

snap-2017-02-16

Changes since last snapshot

  • new graph generator customGraph() for quick generation of
    specific custom graphs
  • the graph size is no longer bounded by the stack size for the
    following algorithms:
    • biconnectedComponents()
    • strongComponents()
    • isForest()
  • new simple graph algorithm nodeDistribution() and
    degreeDistribution() as a special case
  • file format changes:
    • an STP reader for Graph (without edge weights and terminals)
      is now available, and it is included in the generic reader
    • the DMF reader and writer uses Graph and EdgeArray instead
      of EdgeWeightedGraph now
    • the DOT reader is now implemented non-recursively
      (which allows reading of large files while having low stack size)
    • Graph6, GDF, and TLP readers now clear the graph before reading
  • new minimum s-t-cut functionality:
    • MinSTCut module
    • MinSTCutMaxflow (replaces old MinSTCut)
    • MinSTCutBFS
    • MinSTCutDijkstra
  • new class DIntersectableRect replaces IntersectionRectangle
  • new PlanarSubgraphTree class as Maximum Planar Subgraph heuristic
  • bugfixes, code cleanup, improvement of code quality, C++11ifications,
    e.g., in:
    • OGDF initialization
    • the POOL_TS memory manager
    • GraphAttributes
    • GraphCopySimple
    • List, ListPure, SLIst, SListPure
    • DisjointSets
    • EdgeRouter
    • FMMMLayout
    • LCA
    • (fast_multipole_embedder::)ArrayGraph
    • (fast_multipole_embedder::)WSPD
    • the spring embedder force models
  • general (sometimes internal) changes:
    • removal of the doDestruction() function template
    • removal of a lot of shadowing of variables
    • fixes of one-definition-rule violations that led
      to weird problems
    • enum classes (scoped enums) are now used throughout OGDF
      instead of unscoped enums
    • typedefs are replaced by using for improved readability
      and better flexibility
    • declaration of several constructors as explicit to
      avoid implicit conversion where it is wrong
    • some auxiliary classes are moved into sub-namespaces and
      their files are often moved into sub-directories
    • slightly improved consistency in documentation
    • slightly improved code style consistency

There are also CMake changes. The default target only compiles the OGDF (and its dependencies). There are new targets “tests” and “examples” doing the obvious, and a new target “build-all” that also compiles tests and examples. Separate test targets are renamed from foo_bar_test to test-foo-bar.

snap-2016-12-05

Changes since last snapshot

  • new graph generators:
    • emptyGraph() for an empty graph or n isolated nodes
    • randomGeometricCubeGraph() for random geometric graphs in a unit n-cube
    • randomRegularGraph() for random regular graphs
  • revised planar subgraph algorithms:
    • new MaximalPlanarSubgraphSimple adds new planarity-ensuring edges in a given planar subgraph greedily
    • MaximumPlanarSubgraph (ILP-based algorithm) now supports weighted edges
    • PlanarSubgraphBoyerMyrvold is a maximum planar subgraph heuristic based on the Boyer-Myrvold planarity test
    • new PlanarSubgraphCactus implements the 7/18-approximation algorithm by Călinescu et al.
    • new PlanarSubgraphEmpty is a dummy class
    • PlanarSubgraphFast computes a planar subgraph using PQ-trees
    • some of these classes are templates for different types of cost
  • miscellaneous new functionality:
    • AdjElement::isSource(), AdjElement::isBetween()
    • BoyerMyrvold::transform()
    • EdgeElement::getAdj()
    • methods like Graph::chooseNode() or CombinatorialEmbedding::chooseFace() can now adhere to constraints
    • GraphCopy::isReversedCopyEdge()
    • Math::harmonic(n) to compute the n-th harmonic number
    • NonPlanarCore can now process weighted graphs
    • NonPlanarCore::retransform()
    • isRegular() to check if a graph is regular
  • the graph size is no longer bounded by the stack size for the following algorithms:
    • isAcyclic()
    • isAcyclicUndirected()
    • isBiconnected()
    • makeBiconnected()
    • and all algorithms based on these functions
  • as usual: bugfixes, (a little) code cleanup and improvement of code quality, e.g., in
    • OGDF initialization
    • AStarSearch
    • CombinatorialEmbedding
    • DualGraph
    • Graph
    • GraphCopy
    • GraphIO::write{GML,OGML,LEDA,GEXF,GDF,TLP,DL,DOT,GraphML}
    • LCA
    • Math
    • MaxFlowSTPlanarItaiShiloach
    • MaximumCPlanarSubgraph
    • NonPlanarCore
    • SubgraphPlanarizer
    • VariableEmbeddingInserter
    • (internal) heap data structures
    • documentation
  • improved test coverage
  • and some further C++11ification.

Baobab

Today, we released the new version v2015.05 (Baobab) of OGDF! The release introduces various new algorithms and modules but also improves usability and elegance. To accomplish the latter, some changes had to be made that break compatibility to Sakura. Also, COIN-OR and ABACUS are now included in the OGDF package to make every feature work out-of-the-box.

In parallel to the release of Baobab, we uploaded a new snapshot of OGDF. It marks the start in using C++11 features and the CMake build system. Note that you will need much more recent compilers to compile the snapshot than you would need for the Baobab release or former releases.

Highlights

  • 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 (GridSiftingGlobalSifting; 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 (EdgeInsertionModuleFixedEmbeddingInserterVariableEmbeddingInserter*, 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)