INTERFACE GDHeuristicTools;

(* Tools for use in graph drawing heuristics. *)

IMPORT Random;

IMPORT GDGraph AS Graph;
IMPORT GDGeometry;
IMPORT GDDrawing AS Dwg;
FROM GDGraph IMPORT 
  Node, Nodes, Dir, Slot;
FROM GDGeometry IMPORT 
  Points, Weights, Interval, Axis, LONG, INT, NAT, NATS, BOOL;
FROM GDDrawing IMPORT 
  BaseNode;

(* RANDOM CHOICES *)

PROCEDURE RandomRound(x: LONG; rnd: Random.T): INT;
  (*
    If "x" is an exact integer, returns that integer.
    Otherwise chooses randomly between "FLOOR(x)" with probability "f"
    and "CEILING(x)" with probability "1-f", where 
    "f = x - FLOOR(x)". *)

PROCEDURE RandomPerm(n: NAT; rnd: Random.T): REF ARRAY OF NAT;
  (*
    A random permutation of "[0..n-1]". *)

PROCEDURE TopoSort(G: Graph.T; rnd: Random.T): REF ARRAY OF NAT;
  (*
    A topological sort of "[0..G.nV]". *)

PROCEDURE EnumNodesByLayer(
    G: Graph.T;
    READONLY pos: Points;
    cRef: LONG;
    axis: Axis;
  ): REF Nodes;
  (*
    Enumerates the nodes of "G" in order of distance 
    from "cRef" along the specified axis. *)
    
(* EVALUATING A LAYER *)

TYPE YChoice = { Mean, Median, Pack, Flip }; (* Criterion for "y" placement *)

PROCEDURE YCost(
    u: BaseNode; 
    yu: INT; 
    method: YChoice;
    yRef: LONG;
    G: Graph.T;
    READONLY pos: Points;
  ): LONG;
  (*
    Cost of placing the node "u" in layer "yu".
    For each out-neighbor "v" at ordinate "yv", the partial
    cost is infinite if "yu = yv", otherwise it is

      If "method = YChoice.Median":

        if "yu < (yv-1)" then "(yv-1)-yu" else "2*(yu-(yv-1))".

      If "method = YChoice.Mean": 

        Ditto, squared.

      If "method = YChoice.Pack":

        if "yu < (yv-1)" then 0 else "2*(yu-(yv-1))"
        plus a single term "ABS(yu - yRef)".

      If "method = YChoice.Flip":

        if "yu < (yv-1)" then 0 else "2*(yu-(yv-1))"
        plus a a single random term in [0_1].

    For each in-neighbor "v", the condition is reversed and "yv+1" is
    used instead of "yv-1".
  *)
  
PROCEDURE OcCost(oc, iOc, mOc: NAT): LONG;
(*
    Cost due to crowding of placing a base node "u" on a layer
    that already has "oc" base nodes, given that the ideal 
    number of base nodes per layer is "iOc", and the 
    maximum number is "mOc". *)

(* SELECTING A LAYER *)

PROCEDURE PossibleLayers(
    u: BaseNode;
    yRef: LONG;
    G: Graph.T;
    READONLY pos: Points;
  ): Interval;
  (* 
    Returns a range "[yMin..yMax]" of Y-coordinates for "u" that will
    not increase the number of ascending edges and may contain
    the layer of minimum "YCost".
  *)

PROCEDURE ChooseLayer(
    u: BaseNode; 
    method: YChoice;      (* Layer choice method. *)
    yRef: LONG;           (* Y coordinate for global bias. *)
    G: Graph.T;           (* Base graph *)
    READONLY pos: Points; (* Nominal position of all base nodes. *)
    yBase: INT;           (* Starting Y for "oc" indexing. *)
    READONLY oc: NATS;    (* "oc[y-yBase]" is the num of base nodes in layer "y". *)
    iOc: NAT;             (* Ideal occupancy per layer. *)
    mOc: NAT;             (* Maximum occupancy per layer. *)
    rnd: Random.T;        (* Coin. *)
    inertia: LONG;        (* Weight of current position *)
  ): INT;
  (*
    Computes the ``ideal'' Y-coordinate for a node "u" of the base
    graph "G", taking into account the current positions of its
    neighbors in "G". The result is guaranteed to be distinct from the
    Y-coordinates of those neighbors.
    
    The demerit of a Y coordinate "yu" is the sum of the "YCost" and
    "OcCost" terms, plus an `inertial' term equal to 
    "ABS(yCur - yu)" (or its square in the case of "YChoice.Mean"),
    plus a small random noise to break ties. *)

(* SPLITTING A LAYER *)

PROCEDURE SimpleSplitLayer(
    ySplit: NAT;      (* Layer to split. *)
    G: Graph.T;       (* Base graph. *)
    VAR pos: Points;  (* (I/O) positions of nodes of "G". *)
    iOc: NAT;         (* Ideal layer occupancy. *)
    mOc: NAT;         (* Maximum layer occupancy. *)
    rnd: Random.T;
  );
  (* 
    Given tentative positions "pos[u]" for the nodes of "G",
    modifies the, so as to split layer "ySplit" in two.
    
    More precisely, it increments by 1 the Y coordinate "y(u) =
    pos[u][1]" of some nodes "u" with "y(u) = ySplit", and of all
    nodes "u" with "y(u) > ySplit". The X coordinates are not changed.
    
    The decision whether to shift or keep each node "u" on layer
    "ySplit" is made taken into account the positions of "u"'s
    neighbors in "G" and the occupancy goals "iOc" and "mOc",
    plus a bit of randomness.
    
    Any node "u" with "pos[u][1] = NoY" is ignored when deciding
    the split, and its position will not be changed. 
    
    Note that this procedure should NOT be applied to the 
    field "dr.pos" of a drawing directly.  Clients should
    apply it to a private copy of "dr.pos", then use 
    "dr.moveNodes" to do the actual moving. *)

(* EVALUATING A POSITION IN A LAYER *)

PROCEDURE XCost(
    u: Node;               (* The node to be placed *)
    xu: INT;               (* The proposed abscissa *)
    dr: Dwg.T;             (* The drawing. *)
    wtR: REF Weights;      (* "wtR[v]" is the weight of node "v" as neighbor. *)
    inertia: LONG;         (* Rel. weight of current position. *)
  ): LONG;
  (* 
    Cost of placing node "u" at abscissa "xu" of its current layer.
    
    This procedure takes into account the current positions of "u"'s
    neighbors in adjacent layers (with weights "wtR"), and of "u"
    itself (with weight "inertia"), but ignores the existence of other
    nodes on that same layer. In particular, it does not care whether
    the abscissa "xu" is free or not). *)

PROCEDURE CrossingCount(
    dr: Dwg.T; 
    READONLY uu: Nodes;  (* Subset of nodes on some layer of "dr". *)
    ru: NAT;             (* An index into "uu". *)
    wtR: REF Weights;    (* "wtR[v]" is the weight of node "v" as neighbor. *)
  ): INT;
  (*
    Computes the weighted count of crossings between the "D"-edges
    incident to "uu[u]" and the "D"-edges incident to the other nodes
    of "uu", if these were laid out in the order given on their 
    present layer.  A crossing between an edge "(uu[i],v)" and
    "(uu[j],w)" will be counted with weight "wtR[v]*wtR[w]". *)
  
(* SELECTING A POSITION IN A LAYER *)

PROCEDURE FindBestRunBreak(
    dr: Dwg.T;
    xBar: INT;          (* Ideal abscissa for node. *)
    wt: LONG;           (* Weight of node. *)
    READONLY uu: Nodes; (* Maximal run of nodes w/ consex X spanning "xBar" *)
    rnd: Random.T;      (* Bag of coins. *)
    VAR xMin: INT;      (* (OUT) Best abscissa found *)
    VAR kMin: INT;      (* (OUT) "uu[kMin]" is currently occupying it (may not exist). *)
    VAR dMin: [-1..+1]; (* (OUT) direction in which "uu[kMin]" should be shifted. *)
  );
  (*
    Given the desired abscissa "xBar" for a new node, and a maximal
    list "uu[]" of consecutive nodes in some layer of "D", whose
    abscissas are increasing and bracket "xBar", this procedure
    decides where to place that new node. Variable "xMin" is set to
    the best abscissa. If "kMin" is in the range "[0..LAST(uu)]", then
    all nodes nodes "uu[kMin + i*dMin]" should be displaced in the
    direction "dMin". *)

(* OBTAINING A FREE POSITION IN SOME LAYER *)

PROCEDURE HardClearPosition(
    dr: Dwg.T;
    x: INT;    (* Desired abscissa. *)
    y: INT;    (* Layer. *)
    dir: Dir;  (* Node shifting direction. *)
    VAR changed: BOOL;
  );
  (*
    Frees position "(x,y)" in the drawing "(pos, D)", possibly
    by shifting other nodes horizontally in the direction "dir" if needed.
    Sets "changed" TRUE if any nodes were shifted, else leaves "changed" alone. *)

PROCEDURE FancyGetFreeX(
    dr: Dwg.T;         (* The drawing. *)
    xBar: LONG;        (* Desired abscissa. *)
    y: INT;            (* Node ordinate. *)
    wt: LONG;          (* "Mass" of node. *)
    VAR changed: BOOL;
    rnd: Random.T;
  ): INT;
  (*
    Tries to free position "(x,y)" in drawing "dr", or some other
    nearby position on the same layer, possibly by shifting other
    nodes horizontally if needed. Returns the "X" coordinate of the
    freed position. The mass "wt" is used to decide whether it is
    worth moving other Nodes instead of this one.
    
    Sets "changed" TRUE if any nodes were shifted, else 
    leaves "changed" alone. *)
  
(* REORDERING THE NODES OF A LAYER *)

PROCEDURE RearrangeNodesInLayer(
    dr: Dwg.T;        (* Drawing. *)
    VAR uu: Nodes;    (* Some nodes in a given layer. *)
    wtR: REF Weights; (* "wtR[v]" is the weight of "v" as neighbor (NIL=1). *)
    rnd: Random.T;    (* Coin. *)
    inertia: LONG;    (* Rel. weight of current order. *)
  ): BOOL;
  (*
    Tries to rearrange the nodes "uu[...]" (which should belong to the
    same layer of the drawing "dr") so as to decrease the weighted
    count of crossings among the links leading to adjacent layers.
    
    The crossing of an edge from "u" to "u1" and another edge from "v"
    to "v1", where "u" and "v" are in "uu", is counted as
    "wtR[u1]*wtR[v1]" crossings.
    
    If "inertia" is non-zero, gives some weight also to the current
    abscissas of the nodes. In particular, if "inertia = 1", preserved
    the current order.
    
    Returns TRUE iff the X-order changed. *)

PROCEDURE AdjustXInLayer(
    dr: Dwg.T;           (* Drawing to modify. *)
    READONLY uu: Nodes;  (* All the nodes in a given layer. *)
    wtR: REF Weights;    (* "wtR[v]" is the weight of "v" as neighbor (NIL=1). *)
    rnd: Random.T;       (* Coin. *)
    inertia: LONG;       (* Rel. weight of current position. *)
  ): BOOL;
  (*
    Recomputes the abscissas for the nodes "uu[...]", which must be
    all the nodes of "dr" on some layer "y", taking into account 
    the positions of their neighbors, but honoring the 
    order of the "uu[i]".

    Th contribution of neighbor "v" is weighted by "wtR[v]".

    The procedure returns TRUE if some node changed positions.
  *)

PROCEDURE SmoothXInLayer(
    dr: Dwg.T;        (* Drawing to modify. *)
    VAR uu: Nodes;    (* All the nodes in a given layer. *)
    wtR: REF Weights; (* "wtR[v]" is the weight of "v" as neighbor (NIL=1). *)
    rnd: Random.T;    (* Coin. *)
    inertia: LONG;    (* Rel. weight of current position. *)
  ): BOOL;
  (*
    Recomputes the abscissas for the nodes "uu[...]" (which must be
    all the nodes of "dr" on some layer "y") by placing each node
    approximately at the barycenter of its neighboring Nodes.
    Also sorts the array "w" by increasing "x".

    The contribution of neighbor "v" is weighted by "wtR[v]",
    or 1 if "wtR = NIL"

    The procedure returns TRUE if some node changed positions. *)

(* SELECTING LAYERS FOR ALL BASENODES *)

PROCEDURE ChooseYCoords(G: Graph.T; VAR pos: Points; rnd: Random.T);
  (*
    Sorts the nodes of "G" in topological order (to the extent possible),
    then assigns Y coordinates "pos[u][1]" for each node "u" in that order,
    taking into acount the positions of already placed neighbots
    Occasionally splits layers that become too crowded. *)
    
(* SELECTING ABSCISSAS FOR ALL BASENODES *)

PROCEDURE ChooseXCoords(G: Graph.T; VAR pos: Points; rnd: Random.T);
  (*
    Assumes the Y ordinates "pos[u][1]" are fixed for all nodes "u" of "G".
    Selects the abscissas "pos[u][0]" of each node "u" in turn,
    as close as possible to the mean of abscissas of previously placed nodes,
    but always outside the X range of abscissas of nodes placed 
    in the layer of "u". *)

(* ADDING POLYLINES *)

(*
  Each of these procedures adds a polyline to the drawing "dr",
  representing the edge "(u,v)" of "G". Nodes "u" and "v" must have
  different "y" coordinates. May create new joint nodes, in which case
  may expand the "rd" tables. (See "Dwg.AddPolyLine").
  It does nothing if the polyline is already there.

  The procedures differ in how they obtain the abscissas for the 
  joint nodes, if ANY. *)

PROCEDURE LazyAddPolyLine(
    dr: Dwg.T;
    dir: Dir;
    u: Node; ku: Slot; 
    v: Node; kv: Slot;
    rnd: Random.T;
  );
  (* 
    Each joint of the polyline will be placed, in the appropriate layer,
    just outside the range of abscissas of all nodes in that layer;
    either always on the left side, or always on the right side.
    Existing nodes are not moved. *)
  
PROCEDURE FancyAddPolyLine(
    dr: Dwg.T;
    dir: Dir;
    u: Node; ku: Slot; 
    v: Node; kv: Slot;
    rnd: Random.T;
  );
  (* 
    Each joint of the polyline will be placed, in the appropriate layer,
    approximately midway between the abscissas of the base nodes
    "u" and "v". Existing nodes may be moved horizontally to make space 
    for the polyline. The abscissa is obtained with "FancyGetFreeX". *)

PROCEDURE WiseAddPolyLine(
    dr: Dwg.T;
    dir: Dir;
    u: Node; ku: Slot; 
    v: Node; kv: Slot;
    rnd: Random.T;
  );
  (*
    Chooses an abscissa "x" approximately midway between the abscissas
    of the base nodes "u" and "v", then inserts all joint nodes at
    that abscissa, using "HardClearPosition" to make space for them. *)
    
(* VALIDATION *)

END GDHeuristicTools.
(* Last edited on 2000-01-13 10:37:45 by stolfi *)