**************************************************************************

                                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<node> &v_copy,
	      edge_array<edge> &e_copy)
      PlaneGraphCopy(const PlaneCopy& PG, node_array<node> &v_copy,
	      edge_array<edge> &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

