Today, we released the new version v2020.02 (Catalpa) of OGDF.
This release has been in the making for a very long time. Socalled “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 selfloops 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
 DL:
 graph generators:
 faster
randomSimpleGraph()
andrandomSimpleConnectedGraph()
 new
randomSimpleGraphByProbability()
for fast random graph generation
 faster
 new basic functions for convenience:
 cast from
AdjElement
to correspondingnode

EdgeElement::nodes()
function forfor (node v : anEdge>nodes()) { ... }
EdgeElement::isParallelUndirected()
EdgeElement::isParallelDirected()
EdgeElement::isInvertedDirected()

GraphAttributes::transferTo{Original,Copy}()
to replaceGraphCopyAttributes
class (which is removed) 
GraphAttributes::all
flag 
hasNonSelfLoopEdges()
to check whether a graph has edges which are not selfloops removeSelfLoops()

Graph::searchEdge()
with and without edge direction 
GraphAttributes::point(node)
instead of querying single x and ycoordinates 
graphUnion()
to form a (disjoint and nondisjoint) union of two graphs 
graphProduct()
to form the product of two graphs using a given function, and its common usecases:cartesianProduct()
tensorProduct()
lexicographicalProduct()
strongProduct()
coNormalProduct()
modularProduct()
rootedProduct()
 cast from
 algorithms:
 new algorithms:

PlanarSubgraphTriangles
for finding planar subgraphs 
EdgeIndependentSpanningTrees
for k edgeindependent spanning trees  simple algorithms regarding matchings, e.g., Matching::findMaximalMatching()

 algorithms for finding maximum planar subgraphs are now weighttemplated

CliqueFinder
is split intoCliqueFinderHeuristic
andCliqueFinderSPQR
 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
 new
 new algorithms:
 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 toGraphAttributes

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 nodeconnectivity now 
GraphCopy
copy assignment operator fixed for uninitializedGraphCopy
 removed
PreconditionViolatedException
Noteworthy changes since Baobab
Now let us talk about changes since our last nonsnapshot release Baobab.
First of all, we are now using C++11 features, hence a C++11capable compiler
is necessary to use OGDF. Note that for this transition, macros like
forall_nodes()
have been removed in favor of rangebased forloops.
Check the porting guide for compatibilitybreaking changes.
Our build system has been modernized to use CMake instead of selfwritten 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
 there is now a generic reader (
 layouts:
 new
LinearLayout
, places nodes next to each other and draws edges as bows above the nodes  new
NodeRespecterLayout
, a forcedirected layout respecting node shapes and sizes 
SchnyderLayout
can now compute the 1989’s paper version by usingSchnyderLayout::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
 new
 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()
andcompleteBipartiteGraph()
randomSimpleConnectedGraph()
randomSimpleGraphByProbability()

randomGeometricCubeGraph()
for random geometric graphs in a unit ncube 
randomRegularGraph()
for random regular graphs preferentialAttachmentGraph()
regularLatticeGraph()
randomWattsStrogatzGraph()
randomChungLuGraph()
randomGeographicalThresholdGraph()
randomWaxmanGraph()
 generic
randomEdgesGraph()

 algorithms:
 new algorithms:
 stplanarity (planar and nodes s and t share a face):

isSTPlanar()
to check if a graph is stplanar 
planarSTEmbed()
to embed a graph stplanarly

 maximum flows in networks:
MaxFlowEdmondsKarp
MaxFlowGoldbergTarjan
MaxFlowSTPlanarDigraph
MaxFlowSTPlanarItaiShiloach
 minimum stcuts:
MinSTCutBFS
MinSTCutDijkstra

MinSTCutMaxflow
(replaces oldMinSTCut
)
 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 upwardplanar subgraph based on a SAT formulation 
EdgeIndependentSpanningTrees
for k edgeindependent spanning trees  simple algorithms regarding matchings, e.g.,
Matching::findMaximalMatching()

isTwoEdgeConnected()
to check a graph for 2edgeconnectivity isBipartite()
 stplanarity (planar and nodes s and t share a face):
 planar subgraph algorithms:

MaximumPlanarSubgraph
now supports weighted edges  renamed
BoyerMyrvoldSubgraph
toPlanarSubgraphBoyerMyrvold
 renamed
FastPlanarSubgraph
toPlanarSubgraphFast


NonPlanarCore
: can now process weighted graphs
 new
NonPlanarCore::retransform()
 improved (returns simple graphs)

MinCostFlowReinelt
is now costtemplated 
CliqueFinder
is split intoCliqueFinderHeuristic
andCliqueFinderSPQR
 renamed and deprecated some forest functions with misleading names
 new algorithms:
 new basic functions (e.g., for convenience):
 cast from
AdjElement
to corresponding node AdjElement::isSource()
AdjElement::isBetween()

EdgeElement::nodes()
function forfor (node v : anEdge>nodes()) { ... }
EdgeElement::isAdjacent()
EdgeElement::getAdj()
EdgeElement::isParallelUndirected()
EdgeElement::isParallelDirected()
EdgeElement::isInvertedDirected()

operator()
indexing (as synonym foroperator[]
) forNodeArray
s and alike 
operator==
andoperator!=
forArray
andArrayBuffer
GraphCopy::isReversedCopyEdge()

Graph::searchEdge()
with and without edge direction GraphAttributes::nodeBoundingBoxes(boundingBoxes)

GraphAttributes::has()
to check for attributes 
GraphAttributes::transferTo{Original,Copy}()
to replaceGraphCopyAttributes
class (which is removed) 
GraphAttributes::all
flag 
GraphAttributes::point(node)
instead of querying single x and ycoordinates 
hasNonSelfLoopEdges()
to check whether a graph has edges which are not selfloops removeSelfLoops()
Graph::insert()

graphUnion()
to form a (disjoint and nondisjoint) union of two graphs 
graphProduct()
to form the product of two graphs using a given function, and its common usecases:cartesianProduct()
tensorProduct()
lexicographicalProduct()
strongProduct()
coNormalProduct()
modularProduct()
rootedProduct()
 methods like
Graph::chooseNode()
orCombinatorialEmbedding::chooseFace()
can now adhere to constraints 
nodeDistribution()
anddegreeDistribution()
as a special case 
isRegular()
to check if a graph is regular 
GenericComparer
replaces simple custom comparers by using lambdas 
Graph::allNodes()
andGraph::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
 cast from
 geometry classes:

DPoint
,IPoint
are now template specializations ofGenericPoint

DPolyline,
IPolylineare now template specializations of new
GenericPolyline`  new
GenericLine
and newGenericSegment
represent (infinite) lines and (finite) line segments, respectively, replacingDLine
being a mix of both (for double only)  improved intersection methods for these classes
 removed:
DVector
(simply useDPoint
),DScaler
,DRound
 new
DRect::intersection()
 fixed bug and generalized
DPolyline::normalize()
 new
DIntersectableRect
replacesIntersectionRectangle


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 nth harmonic number  new
minValue()
,maxValue()
,sum()
,mean()
,standardDeviation()
 new
radiansToDegrees()
anddegreesToRadians()
 new
updateMin()
andupdateMax()
 new
nextPower2()

 overhaul of
ClusterGraphAttributes
, now similar toGraphAttributes
 removed classes
Stack
,StackPure
,BoundedStack
in favor ofArrayBuffer
 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 selfsufficient (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 subnamespaces of
ogdf
 many
std
members imported into theogdf
namespace are now removed from it (e.g.,swap
,[io]stream
,numeric_limits
,cin
,cout
,endl
,flush
,ios
) 
rbegin()
andrend()
now work with reverse iterators instead of forward iterators 
rbegin()
is renamed tobackIterator()
where a reverse iterator does not make sense  removed
ModuleOption
(replaced bystd::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()
andsafeTestForEach()
as simple functions to iterate over containers destructively (i.e., the current member of an iteration may be destroyed)  removed
PreconditionViolatedException
 all include guards are replaced by
 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, ravenworx on GitHub, Sebastian Semper, Stephan Beyer, Tilo Wiedera, and Yosuke Onoue.