INTERFACE GDHeuristic;

(* Standardized heuristics (a.k.a. "agents") for layered-edge drawing of graphs *)

IMPORT Random;

FROM PSPlot IMPORT Color;

IMPORT GDGraph AS Graph;
IMPORT GDDrawing;
FROM GDGeometry IMPORT NAT, BOOL, LONG;

TYPE
  T = RECORD
      name: TEXT;      (* The heuristic's name, for history. *)
      exec: Proc;      (* The heuristic's algorithm. *)
      color: Color;    (* Color code, for trace plots. *)
      creator: BOOL;   (* TRUE if heuristic requires no input data. *)
    END;

  Proc = PROCEDURE(
      G: Graph.T;
      dr: GDDrawing.T; 
      rnd: Random.T;
      inertia: LONG;
      count: NAT;
      name: TEXT;
    ): GDDrawing.T;
    (*
      An heuristic procedure that tries to create or modify "dr", a (possibly
      incomplete) layered-edge drawing of a graph "G", hopefully
      for better.
      
      In addition to the layered-edge drawing invariants,
      these procedures assume and preserve two additional invariants:
      
        * There is at most one node assigned to a given 
          grid position;
        
        * All edges on a given polyline have the same vertical direction
          (all ascending, or all descending).

      An "HeuristicProc" may return "NIL" to indicate that it failed
      to improve the drawing.  In particular, it may return NIL if 
      the input is NIL.
      
      A `creator' heuristic will usually ignore the drawing "dr"
      (even if NIL) and produce an entirely new drawing for the same
      graph "G".
      
      If "inertia = 0" the procedure applies the heuristic completely.
      If "inertia = 1" the procedure does nothing.
      For values in between, the procedure does part of the job.
      
      In any case, the heuristic should repeat its action "count" times.
      
      The "name" parameter is meaningful only for some heuristics,
      eg. "ReadFile" below.
      
      *)

TYPE
  Menu = REF RECORD (* A linear list *)
      h: T; 
      next: Menu;         
    END;
    
PROCEDURE FindByName(name: TEXT; menu: Menu): T;
  (*
    Returns the heuristic with given name; bombs out 
    if not there. *)

PROCEDURE AddToMenu(READONLY h: T; menu: Menu): Menu;
  (*
    Appends "h" to the given "menu". *)

END GDHeuristic.
(* Last edited on 2000-01-12 10:36:01 by stolfi *)