Elderberry

Today, we released the new version v2023.09 (Elderberry) of OGDF.

This release marks the beginning of public OGDF development on GitHub! Hooray!
Finally, bug fixes and new features will be directly available to the public.
While certain research branches will still have to be kept in a private repository until the corresponding scientific results have been published, the bulk of the development now happens on GitHub. Most importantly, this means that members of the GitHub community can participate in the development of the OGDF in a more direct manner.

We also want to highlight ogdf-python: These python bindings for the OGDF have proved to work quite well, also in conjunction with Jupyter Notebook. Try them out!
Further, we now have conan and vcpkg packages for the OGDF available.

Major Additions Regarding Public OGDF Development

The following new additions will facilitate OGDF development:

  • new dev-guide, inviting you to contribute!
  • code style via clang-format (see .clang-format in the root directory):
    • new script test_clang_format.sh for easy code style enforcement, using a public docker image when the correct version is not installed locally
    • accordingly reformatted code base
  • continuous integration (CI) using GitHub Actions:
    • publicly available docker images for the CI, and scripts to build these images
    • scripts for compiling and running OGDF
      • for Linux, Mac and Windows (the former two using ccache)
      • for different build types (Release, Debug)
      • for different compilers (gcc, clang)
      • with or without Gurobi as the ILP solver
    • scripts for style checks beyond clang-format

New Features and Bug Fixes

Concerning the main code base, this release includes many new features, bug fixes, tests and documentation improvements. Most noteworthy are:

  • compilation fixes, including:
    • C++20 compatibility
    • ARM64 Windows builds
    • cross-compilation for Windows on Linux
  • new geometric crossing minimization functionality:
    • CrossingMinimalPositionFast
    • GeometricEdgeInsertion, GeometricVertexInsertion, and VertexMovement
    • requires compilation with CGAL, for more info consult the corresponding README
  • new MaximumDensitySubgraph
  • new minimum cut algorithms:
    • MinimumCutModule
    • MinimumCutNagamochiIbaraki
    • MinimumCutStoerWagner, a rewritten MinCut with performance in mind
  • new planar separator algorithms:
    • PlanarSeparatorModule
    • SeparatorDual
    • SeparatorDualFC
    • SeparatorHarPeled
    • SeparatorLiptonTarjan
    • SeparatorLiptonTarjanFC
  • new spanner algorithms:
    • SpannerModule
    • SpannerBasicGreedy
    • SpannerBaswanaSen
    • SpannerBerman and SpannerBermanDisconnected
    • SpannerElkinNeiman
    • SpannerIteratedWrapper
    • SpannerKortsarzPeleg
  • new findMaximumCardinalityMatching()
  • new MaxAdjOrdering::calcForest() and MaxAdjOrdering::visualize()
  • new globeGraph() generator
  • GraphIO:
    • new drawTikz() allowing to write out graphs as LaTeX/TikZ
    • new GraphAttributes::isUniform() to test attribute uniformity
    • drawSVG() no longer dashes arrow heads of dashed arrows
    • drawSVG() now correctly uses its given settings
    • readDL() no longer fails when reading nodes with index n
    • readGML() no longer crashes on malformed index data
    • readGraphML() now accepts yFiles yEd files
  • layouts:
    • rewritten RadialTreeLayout now ensures planarity
    • new setForcing2DLayout() for PivotMDS and StressMinimization,
      ensuring a 2D-layout even when GraphAttributes::threeD is set

Contributors

This release contains (big and small) contributions by Dominik Potulski, Finn Stutzenstein, Hendrik Brückler, Ivo Hedtke, Jens Schmidt, Jöran Schierbaum, Kassian Köck, Marcel Radermacher, Mark Scheibner, Max Ilsen, Mirko H. Wagner, Sascha Alder, Simon Dominik “Niko” Fink, Stephan Beyer, Thomas Klein, and modmuss50 on GitHub.

Dogwood

Today, we released the new version v2022.02 (Dogwood) of OGDF.

As always, this release includes many new features, bug fixes and documentation improvements. The most important changes are listed below. Note that we are dropping the official support of some older compilers and are aiming to make use of C++17 features in the future. For more details, take a look at the porting guide.

Noteworthy changes

  • compilation:
    • fixes for compilation with gcc 11, clang 11, AppleClang 12, and ClangCL on MSVC
    • fixes for compilation on ARM architectures
    • installation of shared libraries now possible
    • new cmake option OGDF_FULL_DOC to include {test/,src/} doc in doxygen output
    • new cmake option OGDF_ENABLE_CLANG_TIDY to enable static analysis via clang-tidy
    • OGDF_ prepended to all commented out OGDF-macros (in case you enable them…)
  • basic graph functionality:
    • new GraphObjectContainer<E>::permute(), allows e.g. G.nodes.permute()
    • new GraphList::empty()
    • new optional parameter for contract() to keep self-loops
    • splitNode(a, a) is handled correctly
    • moveAdj() handles self-loops correctly
  • embeddings and dual graph:
    • new operator<<() for faces
    • CombinatorialEmbedding::splitFace() can create self-loops
    • CombinatorialEmbedding::joinFaces() accepts a bridge as an argument
    • EmbedderMaxFace now works correctly
    • new DynamicDualGraph allowing dynamic changes of a dual graph
  • GraphCopy:
    • GraphCopy::removeEdgePathEmbedded() now removes degree-1-nodes
    • new overloads of GraphCopy::{insert,remove}EdgePathEmbedded() can change a DynamicDualGraph
    • new GraphCopy methods to detect and remove non-simple crossings
    • GraphCopy[Simple]::init() now actually clears the graph first
    • empty GraphCopySimple can be constructed, similar to GraphCopy
    • GraphCopy of an empty Graph is now initialized correctly
  • GraphAttributes:
    • idNode() now returns v->index() if no user id is set
  • CoinManager:
    • updateLogging() replaces logging(), propagates log level to COIN
  • (graph) algorithms:
    • new findCutVertices() to extract the cut vertices of a graph
    • triangulate() now runs in linear time (previously: quadratic)
    • Dijkstra: new optional parameters for early termination
    • STNumbering no longer uses recursion, large instances do not cause a stack overflow
    • new BCTree::initNotConnected() for a given subset of graph nodes/components
    • new DisjointSets::init() allows reinitialization
    • new crossing minimization heuristics employing star insertion:
      • PlanarizerStarReinsertion
      • PlanarizerMixedInsertion
      • PlanarizerChordlessCycle
    • SubgraphPlanarizer removes non-simple crossings
  • GraphIO:
    • GraphIO::read() now determines format via file extension
      • GraphIO::read(G, "input.graphml", GraphIO::read) for old behavior
    • new GraphIO::readTsplibXml() for reading tsplib instances in XML format
    • drawSVG() now draws cluster labels
    • drawSVG() now draws arrows heads correctly
    • readDOT() now recognizes numeric literals correctly
    • readGML()/writeGML() now respects idNode() attribute
    • various fixes for ClusterGraph writing
  • layouts:
    • FFPLayout and ComponentSplitterLayout respect a given embedding if possible
    • FMMMLayout: high-level options no longer reset low-level options
      • new FMMMLayout::resetOptions() allows for manual option reset
    • HierarchyLayoutModule no longer resets node attributes
    • PivotMDS computes 3D coordinates when GraphAttributes::threeD is set
    • SugiyamaLayout no longer reverses bend points
    • SugiyamaLayout can handle ClusteredGraphAttributes

This release contains (big and small) contributions by Antoine Lambert, Finn Stutzenstein, Hendrik Brückler, Ivo Hedtke, Jöran Schierbaum, Mario Emmenlauer, Matthias Pfretzschner, Max Ilsen, Simon Dominik “Niko” Fink, Stephan Beyer, Thomas Klein, Thomas Roehr, Vadim Zabermakh, neotechllc and xuanjueheshang on GitHub. Thanks a lot to all contributors!

Catalpa

Today, we released the new version v2020.02 (Catalpa) of OGDF.

This release has been in the making for a very long time. So-called “snapshots” have been introduced in the meantime to shorten the waiting time for the next release. Now, even after more than 3000 commits, our original ambitions of the “next release” are still not fully met, but it is about time for a new snapshot. We have however noticed that releasing snapshots has not proven to be useful; it just caused irritation and confusion among OGDF users. Hence, starting with this release, called Catalpa, we will not publish any further snapshots. Instead, we will try to publish ordinary releases more often, i.e., whenever there has been some noteworthy progress in OGDF.

Moreover, OGDF got a new website, a new logo, and the abbreviation now has a second meaning that reflects OGDF’s matter in a better way. OGDF now stands for both “Open Graph Drawing Framework” and “Open Graph algorithms and Data structures Framework”.

Noteworthy changes since last snapshot

If you used the snapshots, you might be interested in noteworthy changes since the last OGDF snapshot:

  • file formats:
    • DL:
      • improved (and fixed) logic when to use matrix and when to use adjacency list
    • DOT:
      • fixes regarding cluster graphs and parsing bugs
      • support for subgraphs, edge styles, edge types, custom node ids, node label positions, arrow directions
    • GEXF:
      • support for subgraphs, labels, bend points, edge styles, custom node ids, node label positions
      • compatibility fixes (e.g., regarding edge weights)
      • fix handling of directed vs. undirected graphs
    • GML:
      • compatibility changes regarding subgraphs
      • support for node types, node label positions, integral edge weights (including compatibility fix), and cluster graphs
    • Graph6 family:
      • new support for Sparse6 (s6) and Digraph6 (d6) file format
      • fixed support for the case of 63 nodes
    • GraphML:
      • compatibility changes regarding subgraphs
      • support for bend points, edge styles, custom node ids, node label positions
      • fix handling of directed vs. undirected graphs
    • STP:
      • support for coordinates, directed edges, node shapes for terminals
      • support for simplified format (from PACE 2018)
    • support for background pattern’s fill color of nodes in many file formats
    • fix self-loops in Chaco file format
    • the generic reader now supports more file formats and GraphAttributes
    • some readers (e.g., Rudy) are stricter now
    • readers with additional information (like edge weights or terminal nodes) are now available in Graph-only form
    • GraphAttributes can now be used for readers with edge weights
    • new generic writer (GraphIO::write()) based on file name extension
    • fix edge arrow issues in SVG printer
    • deprecated GraphIO functions based on filenames (instead of streams) are removed
  • graph generators:
    • faster randomSimpleGraph() and randomSimpleConnectedGraph()
    • new randomSimpleGraphByProbability() for fast random graph generation
  • new basic functions for convenience:
    • cast from AdjElement to corresponding node
    • EdgeElement::nodes() function for for (node v : anEdge->nodes()) { ... }
    • EdgeElement::isParallelUndirected()
    • EdgeElement::isParallelDirected()
    • EdgeElement::isInvertedDirected()
    • GraphAttributes::transferTo{Original,Copy}() to replace GraphCopyAttributes class (which is removed)
    • GraphAttributes::all flag
    • hasNonSelfLoopEdges() to check whether a graph has edges which are not self-loops
    • removeSelfLoops()
    • Graph::searchEdge() with and without edge direction
    • GraphAttributes::point(node) instead of querying single x- and y-coordinates
    • graphUnion() to form a (disjoint and non-disjoint) union of two graphs
    • graphProduct() to form the product of two graphs using a given function, and its common use-cases:
      • cartesianProduct()
      • tensorProduct()
      • lexicographicalProduct()
      • strongProduct()
      • coNormalProduct()
      • modularProduct()
      • rootedProduct()
  • algorithms:
    • new algorithms:
      • PlanarSubgraphTriangles for finding planar subgraphs
      • EdgeIndependentSpanningTrees for k edge-independent spanning trees
      • simple algorithms regarding matchings, e.g., Matching::findMaximalMatching()
    • algorithms for finding maximum planar subgraphs are now weight-templated
    • CliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQR
    • Steiner tree:
      • new SteinerTreeLowerBoundDualAscent algorithm that can be activated for preprocessing (SteinerTreePreprocessing::reduceFastAndDualAscent())
      • overhaul of constructing and managing full components (for approximation algorithms that use full components)
      • slight overhaul of SteinerTreePreprocessing (including some fixes), MinSteinerTreeGoemans139, MinSteinerTreeRZLoss
  • other noteworthy changes (besides typofixes, less compiler warnings, improved documentation, etc.):
    • many layouts/algorithms now run on corner cases like empty graphs or single nodes
    • overhaul of ClusterGraphAttributes, now similar to GraphAttributes
    • AdjacencyOracle can now trade memory usage versus speed by ignoring nodes of small degree
    • Layout::computeBoundingBox() can now handle negative coordinates
    • ConnectivityTester returns correct values also for node-connectivity now
    • GraphCopy copy assignment operator fixed for uninitialized GraphCopy
    • removed PreconditionViolatedException

Noteworthy changes since Baobab

Now let us talk about changes since our last non-snapshot release Baobab.

First of all, we are now using C++11 features, hence a C++11-capable compiler is necessary to use OGDF. Note that for this transition, macros like forall_nodes() have been removed in favor of range-based for-loops.

Check the porting guide for compatibility-breaking changes.

Our build system has been modernized to use CMake instead of self-written Python scripts. Our documentation (see the Build Guide) provides examples how to use it if you are not familiar with CMake.

Noteworthy changes since Baobab:

  • file formats:
    • there is now a generic reader (GraphIO::read()) recognizing many graph formats…
    • …and a generic writer (GraphIO::write()) based on file name extension
    • new support for file formats:
      • Graph6 (g6)
      • Sparse6 (s6)
      • Digraph6 (d6)
      • format of the DIMACS maximum flow challenge (DMF)
    • additional features and fixes in support for Chaco, DL, DOT, GDF, GEXF, GML, GraphML, STP, TLP
    • some readers (e.g., Rudy, GEXF, TLP) are stricter now (not accepting rubbish)
    • buggy XML parser is replaced by pugixml
    • dead OGML file format no longer supported
    • SVG printer is rewritten (bugfixes included)
    • readers with additional information (like edge weights or terminal nodes) are now available in Graph-only form
    • GraphAttributes can now be used for readers with edge weights
    • GraphIO functions based on filenames (instead of streams) are removed
  • layouts:
    • new LinearLayout, places nodes next to each other and draws edges as bows above the nodes
    • new NodeRespecterLayout, a force-directed layout respecting node shapes and sizes
    • SchnyderLayout can now compute the 1989’s paper version by using SchnyderLayout::setCombinatorialObjects(SchnyderLayout::CombinatorialObjects::Faces)
    • fixed setting of random seeds in FMMMLayout
    • LayoutStatistics changes:
      • new numberOfNodeOverlaps() method
      • new numberOfNodeCrossings() method
      • numberOfCrossings() can now return statistical measures on crossings
  • new graph generators:
    • customGraph() for quick generation of specific custom graphs
    • emptyGraph() for an empty graph or n isolated nodes
    • circulantGraph() for circulant graphs
    • completeKPartiteGraph() and completeBipartiteGraph()
    • randomSimpleConnectedGraph()
    • randomSimpleGraphByProbability()
    • randomGeometricCubeGraph() for random geometric graphs in a unit n-cube
    • randomRegularGraph() for random regular graphs
    • preferentialAttachmentGraph()
    • regularLatticeGraph()
    • randomWattsStrogatzGraph()
    • randomChungLuGraph()
    • randomGeographicalThresholdGraph()
    • randomWaxmanGraph()
    • generic randomEdgesGraph()
  • algorithms:
    • new algorithms:
      • s-t-planarity (planar and nodes s and t share a face):
        • isSTPlanar() to check if a graph is s-t-planar
        • planarSTEmbed() to embed a graph s-t-planarly
      • maximum flows in networks:
        • MaxFlowEdmondsKarp
        • MaxFlowGoldbergTarjan
        • MaxFlowSTPlanarDigraph
        • MaxFlowSTPlanarItaiShiloach
      • minimum s-t-cuts:
        • MinSTCutBFS
        • MinSTCutDijkstra
        • MinSTCutMaxflow (replaces old MinSTCut)
      • Steiner trees:
        • MinSteinerTreeDirectedCut
        • MinSteinerTreeDualAscent
        • MinSteinerTreeGoemans139
        • MinSteinerTreeKou
        • MinSteinerTreeMehlhorn
        • MinSteinerTreePrimalDual
        • MinSteinerTreeRZLoss
        • MinSteinerTreeShore
        • MinSteinerTreeTakahashi
        • MinSteinerTreeZelikovsky
        • SteinerTreePreprocessing
        • SteinerTreeLowerBoundDualAscent
      • planar subgraphs:
        • PlanarSubgraphTriangles
        • PlanarSubgraphTree
        • PlanarSubgraphCactus
        • PlanarSubgraphEmpty
        • MaximalPlanarSubgraphSimple
      • canonical orderings:
        • LeftistOrdering
        • BitonicOrdering
      • MaxAdjOrdering to compute one or all maximum adjacency orderings
      • AStarSearch for finding a shortest path between two given nodes
      • MaximalFUPS for the maximal feasible upward-planar subgraph based on a SAT formulation
      • EdgeIndependentSpanningTrees for k edge-independent spanning trees
      • simple algorithms regarding matchings, e.g., Matching::findMaximalMatching()
      • isTwoEdgeConnected() to check a graph for 2-edge-connectivity
      • isBipartite()
    • planar subgraph algorithms:
      • MaximumPlanarSubgraph now supports weighted edges
      • renamed BoyerMyrvoldSubgraph to PlanarSubgraphBoyerMyrvold
      • renamed FastPlanarSubgraph to PlanarSubgraphFast
    • NonPlanarCore:
      • can now process weighted graphs
      • new NonPlanarCore::retransform()
      • improved (returns simple graphs)
    • MinCostFlowReinelt is now cost-templated
    • CliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQR
    • renamed and deprecated some forest functions with misleading names
  • new basic functions (e.g., for convenience):
    • cast from AdjElement to corresponding node
    • AdjElement::isSource()
    • AdjElement::isBetween()
    • EdgeElement::nodes() function for for (node v : anEdge->nodes()) { ... }
    • EdgeElement::isAdjacent()
    • EdgeElement::getAdj()
    • EdgeElement::isParallelUndirected()
    • EdgeElement::isParallelDirected()
    • EdgeElement::isInvertedDirected()
    • operator() indexing (as synonym for operator[]) for NodeArrays and alike
    • operator== and operator!= for Array and ArrayBuffer
    • GraphCopy::isReversedCopyEdge()
    • Graph::searchEdge() with and without edge direction
    • GraphAttributes::nodeBoundingBoxes(boundingBoxes)
    • GraphAttributes::has() to check for attributes
    • GraphAttributes::transferTo{Original,Copy}() to replace GraphCopyAttributes class (which is removed)
    • GraphAttributes::all flag
    • GraphAttributes::point(node) instead of querying single x- and y-coordinates
    • hasNonSelfLoopEdges() to check whether a graph has edges which are not self-loops
    • removeSelfLoops()
    • Graph::insert()
    • graphUnion() to form a (disjoint and non-disjoint) union of two graphs
    • graphProduct() to form the product of two graphs using a given function, and its common use-cases:
      • cartesianProduct()
      • tensorProduct()
      • lexicographicalProduct()
      • strongProduct()
      • coNormalProduct()
      • modularProduct()
      • rootedProduct()
    • methods like Graph::chooseNode() or CombinatorialEmbedding::chooseFace() can now adhere to constraints
    • nodeDistribution() and degreeDistribution() as a special case
    • isRegular() to check if a graph is regular
    • GenericComparer replaces simple custom comparers by using lambdas
    • Graph::allNodes() and Graph::allEdges() for arrays
    • GraphAttributes::{x,y,z}Label() methods for the coordinates of a label relative to its node
    • Graph::HiddenEdgeSet replaces old and buggy (un)hiding mechanism for edges
    • new EpsilonTest class
  • geometry classes:
    • DPoint, IPoint are now template specializations of GenericPoint
    • DPolyline, IPolylineare now template specializations of newGenericPolyline`
    • new GenericLine and new GenericSegment represent (infinite) lines and (finite) line segments, respectively, replacing DLine being a mix of both (for double only)
    • improved intersection methods for these classes
    • removed: DVector (simply use DPoint), DScaler, DRound
    • new DRect::intersection()
    • fixed bug and generalized DPolyline::normalize()
    • new DIntersectableRect replaces IntersectionRectangle
  • Math utility changes:
    • Math is now a namespace instead of a static class
    • deprecate functions where one can use STL functions instead
    • template some functions such that they can be used, e.g., for ints and doubles
    • new harmonic(n) to compute the n-th harmonic number
    • new minValue(), maxValue(), sum(), mean(), standardDeviation()
    • new radiansToDegrees() and degreesToRadians()
    • new updateMin() and updateMax()
    • new nextPower2()
  • overhaul of ClusterGraphAttributes, now similar to GraphAttributes
  • removed classes Stack, StackPure, BoundedStack in favor of ArrayBuffer
  • removed OGDF file system functions (outside of scope of OGDF)
  • rather internal but noteworthy changes:
    • all include guards are replaced by #pragma once
    • all header files are now self-sufficient (i.e., have no other dependencies)
    • enum classes (scoped enums) are now used throughout OGDF instead of unscoped enums
    • cleanup of global namespace
    • some auxiliary classes are moved into sub-namespaces of ogdf
    • many std members imported into the ogdf namespace are now removed from it (e.g., swap, [io]stream, numeric_limits, cin, cout, endl, flush, ios)
    • 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
    • removed ModuleOption (replaced by std::unique_ptr)
    • AdjacencyOracle can now trade memory usage versus speed by ignoring nodes of small degree
    • the graph size is no longer bounded by the stack size for the following algorithms:
      • biconnectedComponents()
      • isAcyclic()
      • isAcyclicUndirected()
      • isBiconnected()
      • isForest()
      • makeBiconnected()
      • strongComponents()
      • and all algorithms based on these functions
    • new safeForEach() and safeTestForEach() as simple functions to iterate over containers destructively (i.e., the current member of an iteration may be destroyed)
    • removed PreconditionViolatedException
  • many many bugfixes, code cleanup, improvements in code quality, documentation, and test coverage

This release contains (huge and small) contributions by Anuj Agarwal, Hendrick Brückler, Carsten Gutwenger, Daniel L. Lu, Denis Kurz, Ivo Hedtke, Jens Schmidt, Jöran Schierbaum, Karsten Klein, Kévin Szkudłapski, Łukasz Hanuszczak, Manuel Fiedler, Markus Chimani, Max Ilsen, Mirko Wagner, Mihai Popa, raven-worx on GitHub, Sebastian Semper, Stephan Beyer, Tilo Wiedera, and Yosuke Onoue.

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.