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
 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 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()
 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 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 nodeconnectivity now 
GraphCopy
copy assignment operator fixed for uninitialized GraphCopy
 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
 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 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 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 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 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()
 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 costtemplated 
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 NodeArray
s 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
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()
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 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)  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 nth 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 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 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, ravenworx on GitHub, Sebastian Semper, Stephan Beyer,
Tilo Wiedera, and Yosuke Onoue.