|
|||
|
|
|
|||
|
|
OGDF » Release Notes » Sassafras
Released 2010-10-21.
This release brings various new algorithms and features.
Highlights:
UpwardPlanarization); outperforms traditional Sugiyama-based methods with respect to crossings by far.FastMultipoleMultilevelEmbedder), based on the multipole method, well-separated pair decomposition, and a new quadtree space partitioning (Martin Gronemann's Diploma thesis); makes use of SSE and multicore processors and is significantly faster than FMMMLayout.ModularMultilevelMixer) with various options for coarsening, placement, and single-level layout.SpringEmbedderKK) and stress majorization (class StressMajorization).DominanceLayout and VisibilityLayout.MaximumPlanarSubgraph and MaximumCPlanarSubgraph).OGDF_MEMORY_POOL_TS; usually the deafult),OGDF_MEMORY_POOL_NTS), andOGDF_MEMORY_MALLOC_TS).Thread, CriticalSection, Mutex, Barrier.System provides methods for accessing system-dependent information and functionality (processor features, memory usage, file system).DominanceLayout, based on dominance layout of st-digraphs.VisibilityLayout, based on computation of a visibility representation.UpwardPlanarization); implements the algorithm by Chimani, Gutwenger, Mutzel and Wong. Outperforms traditional Sugiyama-based methods with respect to number of crossings by far. Uses module options for upward planarization and layout:UpwardPlanarizerModule: its implementation SubgraphUpwardPlanarizer applies a 2-phase approach: first compute a feasible upward planar subgraph (FUPSModule with implementation FUPSSimple), then insert remaining edges (UpwardEdgeInserterModule with implementation FixedEmbeddingUpwardEdgeInserter).UPRLayoutModule: implementation LayerBasedUPRLayout which makes use of hierarchy layout modules from the Sugiyama framework.SpringEmbedderKK)StressMajorization).FastMultipoleMultilevelEmbedder), based on the multipole method, well-separated pair decomposition, and a new quadtree space partitioning (Martin Gronemann’s Diploma thesis); makes use of SSE and multicore processors and is significantly faster than FMMMLayout.ModularMultilevelMixer) with various options for coarsening, placement, and single-level layout.MultilevelBuilder module (coarsening): EdgeCoverMerger, IndependentSetMerger, LocalBiconnectedMerger, MatchingMerger, RandomMerger, SolarMerger.InitialPlacer module (placement): BarycenterPlacer, CirclePlacer, MedianPlacer, RandomPlacer, SolarPlacer, ZeroPlacer.computeMinST in ogdf/basic/extended_graph_alg.h.OgmlParser implements a parser for OGML files.writeOGML and readClusterGraphOGML in ClusterGraphAttributes provide reading and writing of OGML files.MaximumPlanarSubgraph); requires COIN and ABACUS.MaximumCPlanarSubgraph); requires COIN and ABACUS.GraphAttributes provides now a flag indicating if the graph is directed or not (default is true): methods directed for getting / setting, support in reading and writing GML files (readGML and writeGML).size_t for providing better compatibility with 64-bit systems.GEMLayout revised.ClusterPlanarizationLayout now allows to pass edge weights in its call, which are used for computing a c-planar subgraph (edges with low weight are preferred).Comparer interfaces:Comparer<E> renamed to VComparer<E> (since it relies on virtual functions).OGDF_AUGMENT_COMPARER and OGDF_AUGMENT_STATICCOMPARER to allow easy generation of comparers with full interfaces.StdComparer (standard comparers) and TargetComparer (for comparing targets of pointers).Array::grow() allows now to enlarge an array with empty index set.PlanarizationLayout: changed default planar subgraph to FastPlanarSubgraph.BCTree::findPathBCTree() to pointer (instead of reference) to reflect the fact that the returned object has been allocated with new.isConnected(), makeConnected(): improved performance by replacing recursive with iterative implementation.SugiyamaLayout: possibly incorrect setting of number of crossings if there are several connected components and arrangeCCs = true.BoyerMyrvold: incorrect embedding of self-loops.PlanarAugmentationFix, EmbedderMaxFace, EmbedderMaxFaceLayers, EmbedderMinDepth, EmbedderMinDepthMaxFace, EmbedderMinDepthMaxFace, EmbedderMinDepthPiTa, PlanarizationLayout.NodeArray, EdgeArray, etc.): crashed if copied array was not initialized for a graph.initByNodes().FMMMLayout on Solaris/SPARC.makeConnected().LPSolver_coin..vcxproj). For creating such a project, use makeVCXProj.py (instead of makeVCProj.py). At the moment, there is just one possible template file for VS 2010 (ogdf.vcxproj.vs2010.template; which is the default).ogdf.dll.vcproj.vs2005.template in makeVCProj.config.Psapi.lib.-pthread when compiling and linking with g++.