INTERFACE GDDrawing; (* Plane drawings of graphs. *) IMPORT Rd, Wr; IMPORT GDGraph AS Graph; IMPORT GDGeometry; FROM GDGraph IMPORT Node, Nodes, NodeDict, Dir; FROM GDGeometry IMPORT Point, Points, Interval, Weights, Axis, NAT, INT, LONG, BOOL; TYPE T <: PublicT; PublicT = OBJECT G: Graph.T; (* (CONSTANT) The base graph *) D: Graph.T; (* (READONLY) The representation graph. *) pos: REF Points; (* (READONLY) Node coordinates. *) (* A "Drawing.T" is a directed graph "D" whose nodes are assigned to points of the integer grid (see the method "pos" below). The graph "D" is meant to be a geometric representation of another graph "G", the `base graph'. The base graph must not have parallel or missing edges; meaning that, for each direction "dir", the nodes, "{ G.nbor(u,dir,k) : valid k }", must be all proper and distinct. Specifically, node "v" of drawing "D"represents node "v" of the base graph "G", for "v" in "[0..G.nV-1]". The nodes of "D" with numbers "G.nV" and higher are called `joints', and have indegree = outdegree = 1. Thus, each base edge "(u,v)" of the graph "G" is represented in the drawing "D" by a `polyline', a directed path from node "u" to node "v", whose internal nodes (if any) are all joints. The polyline must exit from node "u" and enter node "v" in "D" through the same slots that the base edge "(u,v)" uses in "G". That is, if "v = G.nbor(u,+1,ku)" and "u = G.nbor(v,-1,kv)", for some "ku" and "kv", then the first edge of the polyline that represents in "D" the base edge "(u,v)" will begin with the edge from "u" to node "D.nbor(u,+1,ku)", and end with the edge from "D.nbor(v,-1,kv)" to "v". Occasionally, a base edge "(u,v)" of "G" may not have a corresponding polyline in "D". In that case the corresponding slots of "u" and "v" in "D" will be empty ("NoNode"). If that happens to one or more base edges of "G", we say that that "D" is a `sub-drawing' or `incomplete drawing' of "G". Note that, in any case, the base nodes of "G" are always present in "D". At any instant, every node "u" of "D" has a definite position "pos[u]". Note that elements "pos[i]" with "i >= D.nV" are garbage and should be ignored. As far as this interface is concerned, there can be any number of nodes assigned to the same grid position. A grid position "(x,y)" is `free' if there is no node at that position. All nodes with the same "y" coordinate are called a `layer' of the graph. It follows that "D" cannot have self-loops. The fields "D", "G", and "pos" are exposed only for efficiency and succintness reasons. Clients should refrain from modifying them except through the methods of this interface. *) METHODS init(G: Graph.T; injective: BOOL; allocJoints: NAT := 20): T; (* Initializes the drawing for the base graph "G". The initial drawing graph "D" will have no joint nodes, and no edges; it will have only the base nodes, "[0..G,nV-1]", each placed on a distinct layer at abscissa 0. If "injective = TRUE", the node positions mut be distinct at all times. The "allocJoints" parameter is an efficiency hint of how many joint nodes will be created in "D" (in addition to the base nodes). *) copy(): T; (* Makes a full copy of the object, so that calling the methods of one will not affect the other. (Note that the base graph "G" is not copied since it is assumed to be constant). *) baseNode(u: Node; dir: Dir): BaseNode; (* Returns the first node of "G" that can be found from node "u" by following edges of "D", either forward ("dir = +1") or backwards ("dir = -1"). In particular, if "u" is already a node of "G", returns "u" itself. If a vacant slot is found before reaching a base node, returns "NoNode". *) layerNodes(y: INT): REF Nodes; (* Returns a list of all the nodes in layer "y", sorted by increasing abscissa, with ties broken by node number. *) layerXRange(y: INT): Interval; (* The range of abscissas spanned by the nodes on layer "y". *) nodeAt(p: Point): Node; (* Returns the node that is currently placed at position "p", or "NoNode" if the position is free. Bombs out if there is more than one node at that position. *) nodeRunAt(p: Point): REF Nodes; (* Returns the maximal list of consecutive nodes in layer "p[1]" that spans position "p". In particular, returns a zero-length list if that position is free. *) addJoint(p: Point): Node; (* Adds a new joint node to the drawing "D", at position "p". The node will be numbered one higher than all existing nodes, i.e. "D.nV". If the drawing was initialized as injective, the point "pt" must be distinct from the current postions of all nodes. *) crunch(): NodeDict; (* Deletes all joints of "D" that cannot be reached from the base base nodes, and renumbers the rest sequentially. *) moveNode(u: Node; p: Point); moveNodes(READONLY uu: Nodes; READONLY pp: Points); moveAllNodes(READONLY pp: Points); (* These methods allow clients to change the position "pos[u]" of node "u" in a safe way, updating internal structures. Method "moveNode" sets "pos[u] := p". Method "moveNodes" simultaneously performs "moveNode(uu[i],pp[i])" for all "i". Method "moveAllNodes" is equivalent to "moveNodes(uu,pp)" where "uu[i] = i" for "i = 0..LAST(pp)". For al three methods, if the drawing was initialized as injective, the positions of all nodes must remain distinct after the specified moves are performed. *) END; TYPE BaseNode = Graph.Node; BaseNodes = Graph.Nodes; BaseEdge = Graph.Edge; BaseEdges = Graph.Edges; CONST NoNode = Graph.NoNode; (* Null value for node number. *) CONST NoX = LAST(INT); (* Null value for X coordinate. May be handy. *) NoY = LAST(INT); (* Null value for Y coordinate. May be handy. *) (* UTILITY PROCEDURES *) PROCEDURE MinBaseY(dr: T): LONG; PROCEDURE MedBaseY(dr: T): LONG; PROCEDURE MaxBaseY(dr: T): LONG; (* The minimum, median, and maximum Y-coordinate of the base vertices of "dr". *) PROCEDURE GetNodesAtX(x: INT; READONLY uu: Nodes; READONLY pos: Points; VAR lo, hi: INT); (* Assumes the nodes in "uu" are sorted by increasing abscissa. Sets "lo" and "hi" to the interval containing all indices "k" such that "uu[k]" has abscissa "x". If there is no such node, returns "lo > hi". *) PROCEDURE GetNodeRunAtX(x: INT; READONLY uu: Nodes; READONLY pos: Points; VAR lo, hi: INT); (* Assumes the nodes in "uu" are sorted by increasing abscissa. Sets "lo" and "hi" to the maximal interval of indices "k" such that the nodes "uu[k]" have consecutuve abscissas spanning "x". If there is no node with abscissa "x", returns "lo > hi". *) PROCEDURE SortNodesByCoords(VAR uu: Nodes; READONLY pos: Points); (* Sorts "uu" lexicographically by increasing coordinate: first "y", then "x", then node number. *) PROCEDURE NeighborMean( u: Node; (* A node of "H". *) H: Graph.T; (* A graph. *) READONLY pos: Points; (* Coordinates for the nodes of H. *) default: LONG; (* Default coordinate. *) wt: REF Weights; (* Weights for the nodes of "H" (NIL means all "1"). *) axis: Axis; (* Coordinate to average. *) ): LONG; (* Computes the weighted average of coordinate "axis" of the neighbors of "u". If "u" has no neighbors, or the total weight of the neighbors is 0, returns the given "default". *) (* INPUT/OUTPUT *) PROCEDURE Read(rd: Rd.T; allocJoints: NAT := 0): T; (* Reads from "rd" a drawing for some graph. Allocates initially space for at least "allocJoints" joint nodes, in addition to the base vertices, even if the drawing actually has fewer than that. *) PROCEDURE Write(wr: Wr.T; dr: T; comment: TEXT := ""); (* Writes "dr" to "wr" in a format compatible with "Read". *) PROCEDURE PlotEPS( name: TEXT; (* File name minus extension (".eps" provided) *) dr: T; (* The drawing *) label: REF ARRAY OF TEXT; (* Base node labels, or NIL *) labelPad: NAT; (* Min width of label boxes (chars). *) fontSize: REAL; (* Nominal font interline height (points). *) scale: LONG := 1.0d0; (* Global scale factor. *) ); (* Writes to "eps" a Postscript representation of drawing "dr". The label of node "u" will be "label[u]" if "label" is not NIL, otherwise it will be "u"; in either case the node box will be dimensioned to contain "labelPad" digits. The "fontSize" is the font height in points. The "scale" factor will be applied to the whole plot, including the font and line widths. *) (* VALIDATION *) PROCEDURE VerifyDegreeInvariants(D: Graph.T; nBaseV: NAT); (* Verifies whether nodes of "D" with numbers above "nBaseV" and above have indegree = outdegree = 1. Bombs out on failure. *) PROCEDURE VerifySlotCorrespondence(G, D: Graph.T); (* Verifies whether the polylines of a drawing graph "D" are attached to the same slots as the edges of the base graph "G". Bombs out on failure. *) PROCEDURE VerifyDistinctPositions(READONLY pos: Points); (* Verifies that all positions in "pos" are distinct. *) END GDDrawing. (* Last edited on 2000-01-13 10:31:07 by stolfi *)