INTERFACE GDHeurX;

(* Horizontal position adjustment heuristics. *)

(*
  The heuristics in this section preserve the ordinates of all nodes
  (vertices and joints), adjusting only their abscissas.  Thus
  they don't create or destroy any nodes or links, and have no effect
  on the vertical direction of links. *)

IMPORT Random;

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

(* HORIZONTAL SQUASHING *)

PROCEDURE SquashX(
    G: Graph.T;
    dr: LDwg.T; 
    <*UNUSED*> rnd: Random.T;
    inertia: LONG;
    <*UNUSED*> count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    This heuristic simply squeezes all nodes in each layer
    to a consecutive range of abscissas, centered at 0, preserving their 
    relative order. *)

(* FANCY (AND EXPENSIVE) X ADJUSTMENTS *)

(*  
  The "AdjustX*" heuristics are variations of the following procedure:
  (1) enumerate the layers in some order; then, for each layer in
  turn, (2) sort the nodes in the layer, from left ot right, according
  to the average abscissa of those neighbors that lie on the
  previously processed layer; then (3) recompute the abscissas of
  those nodes so as preserve their order, while minimizing the sum of
  squared horizontal distances to those neighbors.
*)
 
PROCEDURE AdjustXDn(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from top to bottom. *)

PROCEDURE AdjustXUp(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from bottom to top. *)
    
PROCEDURE AdjustXOt(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from middle out. *)

(* SIMPLER MEAN-BASED ADJUSTMENTS *)

(*
  The "SmoothX*" heuristics are similar to the "AdjustX*" companions,
  except that step (2) is done by pushing all nodes horizontally by
  some large distance, then reinserting them one by one at the best
  position, possibly pushing aside the nodes previously placed on that
  step.
*)

PROCEDURE SmoothXDn(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from top to bottom. *)
  
PROCEDURE SmoothXUp(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from bottom to top. *)
  
PROCEDURE SmoothXOt(
    G: Graph.T;
    dr: LDwg.T; 
    rnd: Random.T;
    inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Processes the layers from the median layer outwards. *)
  
END GDHeurX.
(* Last edited on 2000-01-13 11:49:40 by stolfi *)