|
|||
|
|
|
|||
|
|
OGDF » Release Notes » Catalpa
Released 2020-02-09.
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".
If you used the snapshots, you might be interested in noteworthy changes since the last OGDF snapshot:
Graph-only formGraphAttributes can now be used for readers with edge weightsGraphIO::write()) based on file name extensionGraphIO functions based on filenames (instead of streams) are removedrandomSimpleGraph() and randomSimpleConnectedGraph()randomSimpleGraphByProbability() for fast random graph generationAdjElement to corresponding nodeEdgeElement::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 flaghasNonSelfLoopEdges() to check whether a graph has edges which are not self-loopsremoveSelfLoops()Graph::searchEdge() with and without edge directionGraphAttributes::point(node) instead of querying single x- and y-coordinatesgraphUnion() to form a (disjoint and non-disjoint) union of two graphsgraphProduct() to form the product of two graphs using a given function, and its common use-cases:cartesianProduct()tensorProduct()lexicographicalProduct()strongProduct()coNormalProduct()modularProduct()rootedProduct()PlanarSubgraphTriangles for finding planar subgraphsEdgeIndependentSpanningTrees for k edge-independent spanning treesCliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQRSteinerTreeLowerBoundDualAscent algorithm that can be activated for preprocessing (SteinerTreePreprocessing::reduceFastAndDualAscent())SteinerTreePreprocessing (including some fixes), MinSteinerTreeGoemans139, MinSteinerTreeRZLossClusterGraphAttributes, now similar to GraphAttributesAdjacencyOracle can now trade memory usage versus speed by ignoring nodes of small degreeLayout::computeBoundingBox() can now handle negative coordinatesConnectivityTester returns correct values also for node-connectivity nowGraphCopy copy assignment operator fixed for uninitialized GraphCopyPreconditionViolatedExceptionNow 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:
GraphIO::read()) recognizing many graph formats...GraphIO::write()) based on file name extensionGraph-only formGraphAttributes can now be used for readers with edge weightsGraphIO functions based on filenames (instead of streams) are removedLinearLayout, places nodes next to each other and draws edges as bows above the nodesNodeRespecterLayout, a force-directed layout respecting node shapes and sizesSchnyderLayout can now compute the 1989's paper version by using SchnyderLayout::setCombinatorialObjects(SchnyderLayout::CombinatorialObjects::Faces)FMMMLayoutLayoutStatistics changes:numberOfNodeOverlaps() methodnumberOfNodeCrossings() methodnumberOfCrossings() can now return statistical measures on crossingscustomGraph() for quick generation of specific custom graphsemptyGraph() for an empty graph or n isolated nodescirculantGraph() for circulant graphscompleteKPartiteGraph() and completeBipartiteGraph()randomSimpleConnectedGraph()randomSimpleGraphByProbability()randomGeometricCubeGraph() for random geometric graphs in a unit n-cuberandomRegularGraph() for random regular graphspreferentialAttachmentGraph()regularLatticeGraph()randomWattsStrogatzGraph()randomChungLuGraph()randomGeographicalThresholdGraph()randomWaxmanGraph()randomEdgesGraph()isSTPlanar() to check if a graph is s-t-planarplanarSTEmbed() to embed a graph s-t-planarlyMaxFlowEdmondsKarpMaxFlowGoldbergTarjanMaxFlowSTPlanarDigraphMaxFlowSTPlanarItaiShiloachMinSTCutBFSMinSTCutDijkstraMinSTCutMaxflow (replaces old MinSTCut)MinSteinerTreeDirectedCutMinSteinerTreeDualAscentMinSteinerTreeGoemans139MinSteinerTreeKouMinSteinerTreeMehlhornMinSteinerTreePrimalDualMinSteinerTreeRZLossMinSteinerTreeShoreMinSteinerTreeTakahashiMinSteinerTreeZelikovskySteinerTreePreprocessingSteinerTreeLowerBoundDualAscentPlanarSubgraphTrianglesPlanarSubgraphTreePlanarSubgraphCactusPlanarSubgraphEmptyMaximalPlanarSubgraphSimpleLeftistOrderingBitonicOrderingMaxAdjOrdering to compute one or all maximum adjacency orderingsAStarSearch for finding a shortest path between two given nodesMaximalFUPS for the maximal feasible upward-planar subgraph based on a SAT formulationEdgeIndependentSpanningTrees for k edge-independent spanning treesMatching::findMaximalMatching()isTwoEdgeConnected() to check a graph for 2-edge-connectivityisBipartite()MaximumPlanarSubgraph now supports weighted edgesBoyerMyrvoldSubgraph to PlanarSubgraphBoyerMyrvoldFastPlanarSubgraph to PlanarSubgraphFastNonPlanarCore:NonPlanarCore::retransform()MinCostFlowReinelt is now cost-templatedCliqueFinder is split into CliqueFinderHeuristic and CliqueFinderSPQRAdjElement to corresponding nodeAdjElement::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 alikeoperator== and operator!= for Array and ArrayBufferGraphCopy::isReversedCopyEdge()Graph::searchEdge() with and without edge directionGraphAttributes::nodeBoundingBoxes(boundingBoxes)GraphAttributes::has() to check for attributesGraphAttributes::transferTo{Original,Copy}() to replace GraphCopyAttributes class (which is removed)GraphAttributes::all flagGraphAttributes::point(node) instead of querying single x- and y-coordinateshasNonSelfLoopEdges() to check whether a graph has edges which are not self-loopsremoveSelfLoops()Graph::insert()graphUnion() to form a (disjoint and non-disjoint) union of two graphsgraphProduct() to form the product of two graphs using a given function, and its common use-cases:cartesianProduct()tensorProduct()lexicographicalProduct()strongProduct()coNormalProduct()modularProduct()rootedProduct()Graph::chooseNode() or CombinatorialEmbedding::chooseFace() can now adhere to constraintsnodeDistribution() and degreeDistribution() as a special caseisRegular() to check if a graph is regularGenericComparer replaces simple custom comparers by using lambdasGraph::allNodes() and Graph::allEdges() for arraysGraphAttributes::{x,y,z}Label() methods for the coordinates of a label relative to its nodeGraph::HiddenEdgeSet replaces old and buggy (un)hiding mechanism for edgesEpsilonTest classDPoint, IPoint are now template specializations of GenericPointDPolyline,IPolylineare now template specializations of new GenericPolylinenewGenericLineand newGenericSegmentrepresent (infinite) lines and (finite) line segments, respectively, replacingDLinebeing a mix of both (for double only)improved intersection methods for these classesremoved:DVector(simply useDPoint),DScaler,DRoundnewDRect::intersection()fixed bug and generalizedDPolyline::normalize()newDIntersectableRectreplacesIntersectionRectangle *Mathutility changes: *Mathis now a namespace instead of a static classdeprecate functions where one can use STL functions insteadtemplate some functions such that they can be used, e.g., for ints and doublesnewharmonic(n)to compute the n-th harmonic numbernewminValue(),maxValue(),sum(),mean(),standardDeviation()newradiansToDegrees()anddegreesToRadians()newupdateMin()andupdateMax()newnextPower2()overhaul ofClusterGraphAttributes, now similar toGraphAttributesremoved classesStack,StackPure,BoundedStackin favor ofArrayBufferremoved OGDF file system functions (outside of scope of OGDF)rather internal but noteworthy changes:
- all include guards are replaced bypragma 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 enumscleanup of global namespacesome auxiliary classes are moved into sub-namespaces ofogdfmanystdmembers imported into theogdfnamespace 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 senseremovedModuleOption(replaced bystd::unique_ptr) *AdjacencyOraclecan now trade memory usage versus speed by ignoring nodes of small degreethe 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
newsafeForEach()andsafeTestForEach()as simple functions to iterate over containers destructively (i.e., the current member of an iteration may be destroyed)removedPreconditionViolatedException`
many many bugfixes, code cleanup, improvements in code quality, documentation, and test coverageThis 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.