Ric Holt, Department of Computer Science, University of
Waterloo
Apr 97, Updated May 2002, holt@uwaterloo.ca
This note explains how TA can be used to
be a graph drawing language. TA is intended to allow convenient recording of information
about certain kinds of graphs. The recorded information includes the nodes and
edges in the graph along with attributes that describe these nodes and edges.
TA is a notation for recording the
information in a graphical database, and is not uniquely designed as a drawing
language. However, we can use TA attributes with particular names, such as x
and y, so that a TA program encodes the information needed to draw the graph as
a diagram, perhaps on a computer screen.
We will use an example graph that
contains nodes P (a procedure), Q (a procedure) and V (a variable). There is
Call edge from P to Q and a Ref edge from Q to V. This information is recorded
in the "fact tuple" part of the graph's TA program as follows:
FACT TUPLE :
Call P Q // P Calls Q
Ref Q V // Q References V
To keep things simple, we shall assume that these are the only two edges in the graph. The attributes that are used to place nodes P, Q and V at particular (x, y) locations on the screen can be given as follows, as part of the "fact attribute" part of the graph's TA program:
FACT ATTRIBUTE :P { x = 50 y = 100 }
Q { x = 150 y = 100 }
V { x = 250 y = 100 }
The
convention is that the origin (x = 0, y = 0) is at the top left of the screen
(or window). Another convention is that x and y locate the top left corner of a
box the represents the node on the screen. In this example, the left sides of
the three boxes are, respectively, 50, 150 and 250 pixels from the left side of
the screen, and all three are 100 pixels from the top of the screen.
We will assume that procedures make up a
distinct class of entities called Proc, and variables make up a distinct class
of entities called Var. As a part of the "fact tuple" part of the
graph's TA program, we specify:
FACT TUPLE :$INSTANCE P Proc // P is an instance of a Proc
$INSTANCE Q Proc // Q is an instance of a Proc
$INSTANCE V Var // V is an instance of a Var
We
have now given the "fact" level information that describes the graph
itself and that also provides attributes for drawing the graph. We will now
give the "scheme" which will "declare" the entity classes
Proc and Var, allow connectivity of edges between nodes, and will provide
default attributes such as colors of edges and sizes of boxes.
In the scheme for this example, we allow
procedures to call procedures and procedures to reference variables, as
follows:
SCHEME TUPLE :Call Proc Proc // Procs call Procs
Ref Proc Var // Procs reference Vars
We
also specify that both Procs and Vars are considered to be Boxes, which in turn
have attributes needed for drawing them:
SCHEME TUPLE :$INHERIT Proc Box // A Proc is a Box
$INHERIT Var Box // A Var is a Box
We
specify that Boxes have drawing attributes, and by inheritance so do Procs and
Vars, as follows:
SCHEME ATTRIBUTE :Box { x y width = 70 height = 30 color }
This
specifies that any Box (and thus any Proc or Var) can have x, y, width, height
and color attributes and that the default width and height are respectively 70
and 30. We further give default colors for Proc and Var boxes:
SCHEME ATTRIBUTE :Proc { color = ( 1.0 0.0 0.0 ) } // color red (RGB encoding)
Var { color = ( 0.0 0.0 1.0 ) } // color blue
Our
scheme specifies default colors for Call and Ref edges:
SCHEME ATTRIBUTE :(Call) { color = ( 1.0 0.0 0.0 ) } // color red
(Ref) { color = ( 0.3 1.0 0.3 ) } // color bright red
Our
fact level attributes did not need to explicitly give color, width or height,
because defaults for these are provided in the scheme.
By means of an example, we have described
a basic set of drawing conventions, which we will now give explicitly. (Note
that other conventions may be created; ours is simply one possible convention,
for which a set of supporting tools has been created. The TA language proper is
"unaware" of these conventions.) These conventions use five attributes:
x, y, width, height and color.
The basic drawing conventions require
that each node have x and y attributes set to real (float) values. These are
interpreted as distances in pixels.
The drawing convention expects each node
to also have width and height real values (though defaults may be provided by a
drawing tool for these). It is expected, but not necessarily enforced, that
boxes should not overlap, i.e., the lines forming their edges should not touch
or cross each other.
A color attribute, given as an RGB
triple, is expected for both nodes and edges (though a drawing tool may provide
a default color, such as dark gray.)
These attributes can be provided at the fact level, for individual nodes
and edges, or as defaults in the scheme.
There is no constraint on how these are
specified. For example, it is not necessary to use an entity class called Box.
There is a convention that information
about the graph as a whole is encoded as attributes of a node named $ROOT. For
example, the following specifies that the frame size for drawing the diagram is
expected to be 600 pixels wide and 800 pixels high:
$ROOT { width = 600 height = 800 }
The $ROOT node is not considered to be an
actual node in the diagram. Conceptually, it contains all the nodes in the
graph. By assumption, there are no edges to or from the $ROOT node.
There is a distinguished relation, named
"contain", which gives the hierarchic structure of nodes in the
graph. The contain relation must be a forest. When the graph is drawn, a tuple
such as "contain A B" is represented by drawing box B nested inside
box A, instead of drawing an arrow from A to B.
The x and y values for a box B, contained
in box A, are interpreted as being relative to A, i.e., they are offsets from
the top left corner of A. Boxes can be nested inside boxes, recursively, at any
level, and the relative interpretation of x's and y's is done level by level.
(The default name for this relation is
"contain", but tools should support a mechanism for using alternate
spellings of this relation.)
The most important conventions for using
TA as a drawing language have already been described. We will now list two
other attributes that may be interpreted by software tools that draw diagrams:
Label attribute. By default, when a graph is drawn, the
name of each node is displayed in the node's box. If the label attribute is
given, its value is displayed instead.
Description attribute. If the description attribute is given,
the drawing tool may provide a mechanism for displaying its value.
Here are the collected parts of the TA program used in the extended example, illustrating how to use TA as a drawing language.SCHEME TUPLE : Call Proc Proc // Procs call Procs Ref Proc Var // Procs reference Vars $INHERIT Proc Box // A Proc is a Box $INHERIT Var Box // A Var is a Box SCHEME ATTRIBUTE : Box { x y width = 70 height = 30 color } Proc { color = ( 1.0 0.0 0.0 ) } // color red (RGB encoding) Var { color = ( 0.0 0.0 1.0 ) } // color blue (Call) { color = ( 1.0 0.0 0.0 ) } // color red (Ref) { color = ( 0.3 1.0 0.3 ) } // color bright red FACT TUPLE : $INSTANCE P Proc // P is an instance of a Proc $INSTANCE Q Proc // Q is an instance of a Proc $INSTANCE V Var // V is an instance of a Var Call P Q // P Calls Q Ref Q V // Q References V FACT ATTRIBUTE : P { x = 50 y = 100 } Q { x = 150 y = 100 } V { x = 250 y = 100 }