************************************************************************** Changes.txt This file describes the changes in the latest versions of the AGD-Library. ************************************************************************** Version 1.2: -------------- -) #define __AGD__ 12 -) InteractiveSugiyama: modified version of Sugiyama algorithm that allows to add nodes and edges to a given Sugiyama layout -) New Algorithm NaiveMaximalPlanarSubgraph for computing maximal planar subgraph of given non-planar graph -) New, improved variants of ShortestPathInserter Version 1.1.2: -------------- -) #define __AGD__ 112 -) PlanarizationLayout, PlanarizationGridLayout: set the precondition "simple" only if required by the planar layout algorithm -) SPQRTree, PlanarSPQRTree: allow now also the special case that the graph contains only two nodes and at least 3 edges. -) PlaneGraphCopy constructor: parameter preserveMap TopologyModule::call: parameter preserve map -) PertinentGraph::skeleton_reference_edge() new -) PlanarSPQRTree::random_embed(): embeds skeleton graphs randomly. Version 1.1.1: -------------- -) #define __AGD__ 111 -) PlanarSPQRTree::number_of_embeddings() and PlanarSPQRTree::number_of_embeddings(node v): changed return type from int to integer (LEDA's data type for integers of arbitrary length), because even for relatively small graphs the number of embeddings can exceed the largest possible int value. -) CGraphWin: Load/Save cluster graphs uses now Windows Load/Save dialog boxes on Windows systems. -) return type of AGDModule::postcondition(int) changed to const KeySet &. The method will remain "non-const" until key word mutable is supported by all compilers for which AGD is compiled. -) (Grid)LayoutModule's declare now in their general postcondition (postcondition(0)), which call and call_grid interfaces they support in addition to call(const graph&, LayoutInterface &) and call_grid(const graph&, GridLayout&). Therefore, two new properties are used: key::planar_map_callable: call(const graph&, face, LayoutInterface &) and call_grid(const graph&, face, GridLayout&) are supported. key::PlaneGraphCopy_callable: call(PlaneGraphCopy&, face, LayoutInterface&) and call_grid(PlaneGraphCopy&, face, GridLayout&) are supported. The various concept classes (e.g., ConstLedaGraphConcept, PlaneGraphCopyGridConcept) of AGD declare these properties automatically in a static class function set_postcondition, which is called by the constructor of LayoutModuleImpl and GridLayoutModuleImpl, respectively. -) new standard graph properties for st-graphs (key::st_graph) and st-planar graphs (key::st_planar) with standard rules st-graph <-> acyclic & single source & single sink st_planar -> st_graph & planar new testing functions: bool AGD::is_st_graph (const graph& G, node& s, node& t) bool AGD::is_st_graph (const graph& G) bool AGD::is_st_planar (const graph& G, node &s, node &t) bool AGD::is_st_planar (const graph& G) bool AGD::has_single_source (const graph& G, node& s) bool AGD::has_single_sink (const graph& G, node& t) -) new layout algorithms for st-planar graphs: StPlanarGridLayout (can also compute a dominance drawing of a reduced st-planar graph) and StPlanarLayout -) new graph generator for st-planar graphs: st_planar_graph(...) Version 1.1: ------------ -) #define __AGD__ 110 -) Support for cluster graphs (classes Cluster and ClusterGraph) interface for cluster graph layout algorithms (contained in many classes like CGLayoutModule, CGGridLayoutModule, CGLayoutInterface, CGGridLayout, ... -) extension of LEDA's GraphWin for cluster graphs (class CGraphWin, CGraphWinInterface) -) layout algorithm for cluster graphs: ClusterOrthogonalLayout -) cluster-planarity testing and embedding algorithm (class CPlanarEmbed) -) linear-time implementation of SPQR-trees. Contained in classes SPQRTree, PlanarSPQRTree, Skeleton, and PertinentGraph. -) new compaction module: FlowCompaction, which is now default for PureOrthogonalLayout, OrthogonalLayout, and QuasiOrthogonalLayout. -) Include file version.h replaced by basic.h, which is always included by AGD -) new constructors: GraphCopy(const GraphCopy& GC, node_array &v_copy, edge_array &e_copy) PlaneGraphCopy(const PlaneCopy& PG, node_array &v_copy, edge_array &e_copy) -) new graph generator: planar_biconnected_graph() new graph generator: random_tree() name change: random_tric_graph -> planar_triconnected_graph Version 1.0.1: -------------- -) #define __AGD__ 101 -) GridCoordinateMapper: call() function now calls update() of the respective layout interface -) GraphCopyGLI: new constructors GraphCopyGLI(GridLayout &gl, GraphCopy &GC) GraphCopyGLI(GridLayout &gl, GraphCopy &GC, const IRect &bbox) -) GraphWinAnimInterface: An alternative to GraphWinInterface, that uses GraphWin's set_layout() function for redrawing the graph. -) GraphWinInterface has now an option flush for disabeling redrawing in update(). -) new two-layer crossing minimization heurisitc: SiftingHeuristic -) faster implementations of some other heuristics. Version 1.0: ------------ -) #define __AGD__ 100 -) GridLayout::init removed. Use, e.g., "gl = GridLayout(G)" instead. -) new RankAssignment module (1. phase of Sugiyama): OptNodeRanking -) new HierarchyLayoutModule (3. phase of Sugiyama): OptCompCoord -) Specifying the relation between properties with rules (e.g., biconnected -> connected) classes Rule, RuleAdmin, DefaultRuleAdmin -) class AGD contains DefaultRuleAdmin methods: get_rule_admin, closure, implies -) AgdKey::id() -> AgdKey::index() -) new grid coordinate mappers: MaxEachMapper and FixedGridMapper -) optional parameters of MaxAllMapper changed! -) constructor of IRect: parameters ymin and ymax changed! -) cordinate system for layouts is now defined such that positive y is up! -) name change: HierarchicalRanking -> LongestPathRanking -) new RankAssignment module: CoffmanGrahamRanking -) new subgraph modules: GreedyCycleRemoval, ReducedDigraph -) improved crossing minimization in SugiyamaLayout (new options: transpose and init_order) -) new 2-layer cross. min. heuristic: WeightedMedianHeuristic Version 0.9.1: -------------- -) compaction of orthogonal drawings: base class: CompactionModule algorithm: LongestPathCompaction -) checking of preconditions now implemented using checker-classes (GraphChecker, SubgraphChecker). They allow to add your own checking functions. all check functions of modules are now declared const. -) name changes: MaximumAcyclicSubgraph -> OptAcyclicSubgraph MaximumPlanarSubgraph -> OptPlanarSubgraph PlanAugOpt -> OptPlanAug Ortho -> PureOrthogonalLayout Quod -> QuasiOrthogonalLayout new variant of Quod: OrthogonalLayout -) Linear-time triconnectivity test. Module TriconnectivityTest and also called by AGD::is_triconnected. -) in GridLayoutModule: get_grid_area -> bounding_box -) new keys: maximal_planar, maximum_planar, maximal_acyclic, maximum_acyclic -) rename of integer constants for positions of parameters (AugmentationModule, SubgraphModule, PlanarizationModule, EdgeInsertionModule, TwoLayerCrossMin, RankAssignment, HierarchyLayoutModule) refinement of (abstract) parameter types of modules (e.g., graph -> subgraph) Version 0.9: -------------- -) new version of Mixed-Model. Implements the version presented at GraphDrawing '98. -) name change AGDModule::usable -> AGDModule::applicable -) Pre- and postcondition handling, keys, ... static initialization of AGD changed. Fixes a bug that can appear if modules are defined as global or static class variables. predefined keys are now defined as enumeration value of type key::Predefined (header AGD/key.h). Keys are represented by class AgdKey (instead of type agd_key). Values of type key::Predefined can be converted (implicitly) to AgdKey. pre- and postcondition are now represented by classes PreCond, PostCond, and PostCondRule. -) new subgraph module 'MaximumAcyclicSubgraph' in libAGDopt. Computes the optimal solution of the acyclic subgraph problem. -) new two-layer-cross-min module 'OptCrossMin' in libAGDopt. Computes the optimal solution of the two-layer crossing minimization problem (one layer fixed, one layer changeable). -) Sugiyama-Algorithm: new option 'fails' in SugiyamaLayout new module option 'subgraph' in HierarchicalRanking. Determines the algorithm used for computing a maximal acyclic subgraph. TopSortRanking removed. Use HierarchicalRanking instead. -) GridCoordinateMapper adapted in order to support "large nodes". Standard Interface changed! -) Animation support removed from layout algorithm classes. Will be replaced by a new module type later. -) Redesign of LayoutModule and GridLayoutModule classes. See the manual entries and the Chapter "Implementation of Layout Algorithms" in the documentation. -) GridLayout: support for large nodes: width and height attributes new functions for computing values of aesthetic criteria number_of_bends, total_manhattan_edge_length, total_edge_length, area former area renamed to bounding_box -) GridCoordinateMapper: input parameter gbbox removed, return type changed to void pure virtual method get_layout_size removed new function: grid_layout() -) name changes: _call -> do_call AugmentationModule, EdgeInsertionModule, SubgraphModule, PlanarizerModule AugmentModule -> AugmentationModule EdgeInsertModule -> EdgeInsertionModule Version 0.8.3: -------------- -) fixed a bug in PlaneGraphCopy (caused an error in PlanarizationLayout and PlanarizationGridLayout) -) SpringLayout: nodes don't come to close to each other now -) new class LeveledGraph (for future use) -) a few updates -) RankAssignment: added check-function Version 0.8.2: -------------- -) new module TopologyModule, which allows to retrieve the planar embedding of a graph out of a planar drawing -) header basic.h removed. version macro __AGD__ now defined in AGD.h -) headers allow to compile with LEDA_PREFIX -) fastHierarchyLayout -> FastHierarchyLayout -) LayoutInterface: init() and cleanup() method remove. Put initializing stuff in the constructor, and cleaning-up stuff in update() or the destructor. constructor gets the associated LEDA graph as parameter set_graph and get_graph for changeing the associated graph area() computes a tight bounding box GraphWinInterface::init(GW) new PSInterface::init(G,name) new -) LayoutModule: layout interface parameter for _call methods is now laways of type LayoutInterface overridable get_layout_size removed. -) GridLayoutModule computation of grid size: if desired, an algorithm can compute the grid bounding box and set it with set_grid_bbox(), otherwise the bounding box is computed automatically. unnecessary bend points are removed automatically -) new class GridLayout. Changed parameter types in GridLayoutModule. -) Redesign of classes GraphCopy and PlaneGraphCopy (former PlanarizedGraph): GraphCopy maintains now copy(v) and chain(e). GraphCopy::split(e) new -) layout modules supporting animation must now have a general postcondition "animation", e.g., call "add_post_rule (key::animation, 0);" in the constructor -) removed classes PlanarLayoutModule and PlanarGridLayoutModule Instead, we use a general postcondition key "planar layout" indicating a planar layout algorithm. For a module derived from PlanarLayoutModule, make the following changes: base class is now LayoutModule call "add_post_rule (key::planar_layout, 0);" in the constructor rename clone_pl to clone and change return type to AGDModule* For a module derived from PlanarGridLayoutModule, make the following changes: base class is now GridLayoutModule call the constructor of GridLayoutModule instead of LayoutModule in order to pass the parameter use_copy call "add_post_rule (key::planar_layout, 0);" in your constructor rename clone_plg to clone and change return type to AGDModule* -) new generic layout algorithm: PlanarizationGridLayout -) new ranking module: HierarchicalRanking Version 0.8.1: -------------- -) orthogonal layout algorithms: OrthoLayout (Tamassia's algorithm for four-graphs and Quod for general planar graphs) -) Sugiyama algorithm as generic layout algorithm. Several classes for different phases (RankingModule, TwoLayerCrossMin, HierarchyLayoutModule) and implementations (see manual) -) computing a maximum planar subgraph (MaximumPlanarSubgraph) -) implementation of KeySet changed from h_array to int_set (needs much less memory) -) PlanarSubgraph module runs with all kinds of graphs (directed, undirected, self loops, multi edges) Version 0.8: -------------- -) optimal branch and cut algorithm for planar biconnected augmentation (PlanAugOpt) -) module for computing a planar subgraph (PlanarSubgraph) -) new submodule classes for planar layout algorithms (PlanarLayoutModule and PlanarGridLayoutModule) -) LayoutBase is now a virtual base class of GridLayoutModule (and PlanarLayoutModule). That means, algorithms that derive from GridLayoutModule, PlanarLayoutModule or PlanarGridLayoutModule MUST call the constructor of LayoutModule (though it is not a direct base class) to set the parameter use_copy. -) Overridables for implementig algorithms are renamed to _call, _call_grid, ... (instead of call_layout, call_copy_layout, ...). -) New classes for implementing planarization (module classes, graph classes, layout interfaces) -) bug fix in GraphWinInterface (caused sometimes an error with SpringLayout). Version 0.7: -------------- -) Each AGDModule M must now have a method AGDModule *clone() const which returns a new allocated pointer to an instance with the same option settings as M -) class AGD split into AGD and AGDModule -) The class AGD allows to access the default keymapper, iteration over all defined keys is possible. -) new class KeySet -) class Keymapper: iteration over keys -) some renames: LayoutBase -> LayoutModule GridLayoutBase -> GridLayoutModule -) selection of using graph copies for layout and grid layout algorithms: use_copy is now a parameter of the constructor of LayoutModule and GridLayoutModule. -) precondition and postcondition handling: *) properties are now called postconditions. *) instead of "add_property(k)" use now "add_post_rule(k)" *) Postconditions can now depend on guaranteed preconditions, for example "add_post_rule(planar,in_graph,no_crossings)" would mean, that the layout contains no crossings if the input graph was planar. See the manual (class AGDModule) for more details. *) supports now more input and output parameters, what is necessary for modules *) the check method moved from AGD to LayoutModule *) new classes tr_literal and TaggedRule, which are used to represent postcondition rules (see manual class AGDModule) -) GraphWinInterface: support of source and target anchors implemented -) LayoutInterface: new method set_all_anchors(G,p) -) MaxAllMapper sets all edge anchors to (0,0) -) LayoutModule, GridLayoutModule: If implementation methods (e.g., call_copy_layout) are not overridden, a warning is displayed via LEDA error handler (can be turned off by defining LEDA_CHECKING_OFF). -) exception handling replaced by LEDA's error handler because of problems with compilers. You should not use the flag -fhandle_exceptions when compiling with g++ anymore. -) new module type: AugmentationModule -) new augmentation modules: PlanAug and LEDAMakeBiconnected