INTERFACE GDLayeredDrawing; (* Tools for manipulating layered-edge graph drawings. *) IMPORT GDGraph, GDGeometry, GDDrawing; FROM GDGraph IMPORT Node, Edge, Edges, Dir, Slot; FROM GDGeometry IMPORT Points, INT, NAT, BOOL, LONG; FROM GDDrawing IMPORT BaseNode, BaseNodes; TYPE T = GDDrawing.T; (* A `layered-edge drawing' is a drawing where every edge connects two vertices whose Y coordinates differ by +1 or -1; and, moreover, all the edges of a polyline have the same Y direction (all ascending, or all descending). This interface provides procedures that assume and preserve this property. *) (* UTILITIES *) PROCEDURE EdgeLayer(s: Edge; READONLY pos: Points): INT; (* The edge layer containing edge "e", i.e. the Y coordinate of the top (lowest Y) endpoint of the edge "e", irrespective of its direction. *) PROCEDURE SortEdgesByLayer(VAR s: Edges; READONLY pos: Points); (* Sorts the edges in "ee" by the Y coordinates of their top endpoints. The edges within the same layer in arbitrary order. *) (* CHECKING AND SELECTING LAYERS FOR BASE NODES *) PROCEDURE LayerIsSafe(u: Node; y: INT; G: GDGraph.T; READONLY pos: Points): BOOL; (* TRUE iff "y" is a layer where "u" be placed without violating the layered edge invariants; i.e. iff layer "y" contains no vertex that is a neighbor of "u" in "dr.G". *) PROCEDURE FindSafeLayer( dr: T; u: Node; y: INT; dir: [-1..+1]; ): INT; (* Returns the first ordinate in "y", "y+dir", "y+2*dir", ... where "u" can be legally placed, i.e. that does not contain any neighbors "u". *) (* ADDING AND DELETING POLYLINES *) TYPE GetJointXProc = PROCEDURE (dr: T; y: INT; VAR changed: BOOL): INT; (* A procedure that finds a free abscissa in layer "y" of "dr" for a joint node of a polyline, possibly by horizontally displacing other nodes on that layer. Should return the abscissa that was actually cleared. When this procedure is called, the joint node in question will not have been created yet. Must set the variable "changed" to TRUE if any node was displaced; otherwise leaves "changed" as it was. The procedure is NOT allowed to modify the nodes and edges of the drawing, to move nodes to different layers, or to change the abscissas of nodes in other layers. *) PROCEDURE AddPolyLine( dr: T; (* The drawing *) dir: Dir; (* Direction of edge. *) u: Node; ku: Slot; (* Base node of origin/dest, and slot. *) v: Node; kv: Slot; (* Base node of dest/origin, and slot. *) getJointX: GetJointXProc; (* X coordinate selector for joint nodes. *) ); (* Adds a polyline to the drawing "dr", representing an edge of the base graph "G" with direction "dir" between "u" and "v". The base nodes "u" and "v" must have different "y" coordinates. Does nothing if the polyline is already there. If "u" and "v" are not on adjacent layers, the procedure will create one new joint node for each intermediate layer. The "getFreeX" procedure is used to choose the abscissas of the new joint nodes. These are currently created in y-order, from the layer of "u" towards the layer of "v". *) PROCEDURE DeletePolyLine( dr: T; dir: Dir; u: Node; ku: Slot; v: Node; kv: Slot; ); (* Deletes a polyline of "D" from the drawing "dr", representing the base edge "(u,v)" of "G". The slots "ku" of "u" and "kv" of "v" will become vacant (" = NoNode") in "D". Also any joint nodes along that polyline will become unreachable, although they will still occupy their current positions. (Clients may want to do a "crunch" after calling this procedure.) Does nothing if the polyline has already been deleted. *) (* MOVING BASE NODES AND THEIR POLYLINES *) PROCEDURE DisconnectBaseNode(dr: T; u: BaseNode); (* Deletes from "dr.D" the polylines corresponding to the base edges of "dr.G" that are incident to base node "u". The corresponding slots "dr.D.nbor(u...)" of "D" are set to "NoNode". Does not delete the joint nodes. *) TYPE GetBaseNodeXProc = PROCEDURE (dr: T; u: Node; y: INT; VAR changed: BOOL): INT; (* A procedure that finds a free abscissa for the base node "u" in layer "y" of "dr", possibly by horizontally displacing other nodes on that layer.. When this procedure is called, some base nodes may have been displaced to layers with very large "y", but retaining their original abscissas. Also the graph "D" may be incomplete. The procedure may therefore use the positions of all "D" nodes currently on layer "y", and the abscissas of "u" and of its "G"-neighbors (but it should not look at its "D"-neighbors). The procedure must set the variable "changed" to TRUE if it displaces any node of "dr"; otherwise it should leave "changed" as it was on entry. The procedure is NOT allowed to modify the nodes and edges of the drawing, to move nodes to different layers, or to change the abscissas of nodes in other layers. *) AddPolyLineProc = PROCEDURE(dr: T; dir: Dir; u: BaseNode; ku: Slot; v: BaseNode; kv: Slot); (* Template for a procedure that adds to the drawing "dr" a polyline from output slot "ku" of base node "u" to input slot "kv" of base node "v". Those two slots must be currently vacant. The procedure is supposed to add to "dr" new nodes for use as joints of the polyline; and is allowed to displace any nodes (including base nodes) horizontally. *) PROCEDURE ConnectBaseNode( dr: T; u: BaseNode; addPolyLine: AddPolyLineProc; ); (* Adds to the drawing "dr" (with "addPolyLine") the new polylines that represent all base edges incident to "u". Polylines that are already there will not be affected. *) PROCEDURE MoveBaseNodes( dr: T; READONLY uu: BaseNodes; READONLY pp: Points; getBaseNodeX: GetBaseNodeXProc; addPolyLine: AddPolyLineProc; ); (* Tries to move base node "uu[i]" of the graph "G" from its current position to position "pp[i]", for all "i". Proceeds by (1) deleting all polylines incident to the base nodes that change layers, and (2) moving them to layers with very high "y"; then (3) moving all given nodes sequentially to the specified layers, at or near the specified abscissas (using "getBaseNodeX" to select the actual abscissas), and finally (4) reinserting (with "addPolyLine") the polylines that were deleted in step (1). When choosing the new node positions "pp[..]", the client must make sure that, after all nodes have been moved, there will be no two base nodes in the same layer that are neighbors in "G". *) PROCEDURE MoveTree( dr: T; u: BaseNode; yNew: INT; getBaseNodeX: GetBaseNodeXProc; addPolyLine: AddPolyLineProc; ); (* Moves base node "u" from its current layer "yOld" to layer "yNew". If "yNew > yOld", also identifies any out-neighbors of "u" that lie in layers "yOld+1 .. yuNew", and moves them to layer "yuNew+dir" (or beyond), and so on recursively. If "yNew < yOld", does the same to in-neighbors in layers "yOld-1 .. yNew". Proceeds by (1) computing the base nodes that have to be moved, and theur new layers; then (2) calling MoveBaseNodes to do the actual motion. The "getBaseNodeX" and "addPolyLine" procedures are passed on to "MoveBaseNodes". *) (* DRAWING SCORES *) PROCEDURE NumCrossings(dr: T): LONG; (* Number of crossings between the edges of "dr.D". *) PROCEDURE NumReverse(dr: T): LONG; (* Number of reversed polylines (not edges) in "dr.D" *) PROCEDURE NumBends(dr: T): LONG; (* Number of joint nodes of "D" whose incident edges are not collinear. *) PROCEDURE TotLength(dr: T): LONG; (* Total Euclidean lenth of the edges of "D". *) (* VALIDATION *) PROCEDURE VerifyLayerInvariants(D: GDGraph.T; READONLY pos: Points); (* Verifies whether all edges of "D" have endpoints on distinct but adjacent layers. Bombs out on failure. *) PROCEDURE VerifyPolylineMonotonicity(D: GDGraph.T; nBaseV: NAT; READONLY pos: Points); (* Verifies that all polylines of "D" (the maximal paths that begin and end in vertices "[0..nBaseV-1]" are monotonic in "y". Bombs out on failure. *) END GDLayeredDrawing. (* Last edited on 2000-01-12 13:22:39 by stolfi *)