Skip to content
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.
