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.