INTERFACE GDHeurDir;

(* Edge direction heuristics. *)

IMPORT Random;

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

(* 
  Let "Y(u)" be the Y-coordinate of verted "u" in a given drawing
  "dr". Ideally every edge "(u,v)" should be descending, i.e. "Y(u) <
  Y(v)". (Recall that the Y axis points *down*.) The heuristics in
  this section try to fix edges that go in the wrong way.
  
  Unlike the "GDHeurY" methods, which adjust one vertex at
  a time and look only at the immediate neighbors of the vertex being
  processed, these heuristics will displace entire subsets of the
  nodes at one time. *)

PROCEDURE FixEDirs( 
    G: Graph.T;
    dr: LDwg.T;  
    rnd: Random.T;
    <*UNUSED*> inertia: LONG;
    count: NAT;
    <*UNUSED*> name: TEXT;
  ): LDwg.T;
  (*
    Let "H" be the subgraph of "dr.G" consisting of all
    descending edges.  (Note that "H" is necessarily acyclic.)
    
    This heuristic looks for an edge "(u,v)" of "dr.G" such that 
    "Y(u) > Y(v)" and "u" is not a descendant of "v" in "H".
    Then it fixes that edge by moving "v" down and/or "u" up,
    until "Y(u) < Y(v)".  Base nodes that are descendants
    of "v" or ascendants of "u" in "H" may have to be displaced
    as well, in order not to reverse any "H" edges. *)
    
END GDHeurDir.
(* Last edited on 2000-01-12 10:28:01 by stolfi *)