INTERFACE GDHeurY;

(* Local vertical adjustment heuristics. *)

IMPORT Random;

IMPORT GDGraph AS Graph;
IMPORT GDLayeredDrawing AS LDwg;
FROM GDGeometry IMPORT LONG, NAT;

(*
  These heuristics try to improve the vertical placement of base nodes
  in a layered drawing "dr". Note that moving a base node "u", to a
  different layer usually requires changing the topology of the
  drawing "dr.D", and re-routing all polylines incident to "u".
  
  The "AdjustY*" heuristics below are all variants of the following
  procedure: (1) list the nodes of the base graph "G" in some
  order; (2) for each node, in that sequence, choose a new Y coordinate,
  preserving its current X coordinate; (3) move those nodes vertically,
  well out of the way of other nodes; (4) move each of those nodes
  to its computed position, in the same sequence, trying to preserve their
  abscissas.
  
  In step (2), the procedure takes care not to assign neighboring
  vertices to the same layer. In step (4), the procedure may shift
  vertices horzontally to make space.
  
  The various "AdjustY*" heuristics differ in the order in which the 
  vertices are processed, and on how the new Y coordinate is chosen. 
  In general each node gets initially assigned its current Y coordinate,
  which is then modified, taking into account the Y coordinates of
  its neighbors. *)

PROCEDURE AdjustYMedian( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices in random order. Chooses the new ordinate
    of each vertex as near as possible to the median of the layers of
    its neighbors, where a neighbor has double weight if the polyline
    is reversed. (If the vertex has no neighbors, the heuristic will
    place it in the median layer of all vertices). *)

PROCEDURE AdjustYMean( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices in random order. Chooses the new ordinate
    of each vertex as near as possible to the arithmetic mean of the
    layers of its neighbors, where a neighbor has double weight if the
    polyline is reversed. (If the vertex has no neighbors, the
    heuristic will place it in the median layer of all vertices). *)

PROCEDURE AdjustYFlip( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices in random order. Chooses the new ordinate
    of each vertex so as to minimize the number of reversed edges
    (in-neighbors below it, or out-neighbors above it). If there are
    many such layers, chooses one randomly. (If the vertex has no
    neighbors, the heuristic will place it in the median layer of all
    vertices). *)

PROCEDURE AdjustYPackUp( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices from the top down. Chooses the new 
    layer of each vertex so as to minimize the number of reversed edges
    (in-neighbors below it, or out-neighbors above it). If there are
    many such layers, chooses the highest of them. *)

PROCEDURE AdjustYPackDn( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices from the bottom up. Chooses the new 
    layer of each vertex so as to minimize the number of reversed edges
    (in-neighbors below it, or out-neighbors above it). If there are
    many such layers, chooses the lowest of them. *)
    
PROCEDURE AdjustYPackOt( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the vertices in order of increasing vertical distance
    from the median layer. Chooses the new layer of each vertex so as
    to minimize the number of reversed edges (in-neighbors below it,
    or out-neighbors above it). If there are many such layers, chooses
    the layer closest to the median of all vertices. *)
    
END GDHeurY.
(* Last edited on 2000-01-12 10:31:01 by stolfi *)