Grapher documentation

Richard R. Burton, Kurt VanLehn, R. Kaplan
Last revised: February 15, 1985
Copyright (c) 1982, 1983, 1985 Xerox Corporation

The GRAPHER library package contains a collection of functions and an interface for laying out, displaying, and editting graphs (i.e., networks of nodes and links).  Graphs have node labels but not link labels.  Links are drawn by default as straight lines without arrowheads, but the user can control the appearance of individual links.  Node labels can be a single line of text, a bitmap of arbitrary size, or an imageobject.  There are facilities for having actions triggered by selection of nodes in graphs, and image objects containing graphs can be constructed, so that graphs can be included in documents and other image structures. 

A typical way to use the grapher package is to implement a function that creates a partially specified graph that represents some user data (or control) structure.  For instance, the browser lispusers package uses graphs to represent function calling structures (from Masterscope).  Such a partially specified graph need only have the graph labels and the links specified.  It is given to LAYOUTGRAPH, along with some formatting information.  LAYOUTGRAPH assigns a position to each of the nodes.  There are formats for laying out trees, lattices and cyclic graphs.  LAYOUTGRAPH returns a GRAPH record, which is usually given to the function SHOWGRAPH.  SHOWGRAPH displays a graph in a window.  Displayed graphs are often used as menus: selecting a node with the left or middle button can cause user-provided functions to be called on that node.  Displayed graphs can be edited using the right button.  Nodes can be added, deleted, moved, enlarged or shrunk.  Links can be added or deleted.

This document first describes the data structures, the GRAPH and GRAPHNODE records, then the layout functions, the display functions, and the editing functions.

The Graph

A graph is represented by a GRAPH record, which has the following fields: GRAPHNODES, DIRECTEDFLG, SIDESFLG, GRAPH.MOVENODEFN, GRAPH.ADDNODEFN, GRAPH.DELETENODEFN, GRAPH.ADDLINKFN, GRAPH.DELETELINKFN and GRAPH.FONTCHANGEFN.

GRAPHNODES is a list of graph nodes, which are described below.

DIRECTEDFLG and SIDESFLG are flags which control how links are drawn between the nodes.  If DIRECTEDFLG is NIL, the Grapher will draw each link in such a way that it does not cross the node labels of the nodes it runs between.  Often, this leaves some ambiguity, which is settled by SIDESFLG:  If SIDESFLG is NIL, the Grapher prefers to draw links that go between the top and bottom edges of nodes.  If SIDESFLG is non-NIL, it prefers to draw links between the sides of the nodes.

If DIRECTEDFLG is non-NIL, the edges are fixed (e.g., always to the left edge of the to node).  This can cause links to cross the labels of the nodes they run between.  In this case, if SIDESFLG is NIL, the "from" end of the link is attached to the bottom edge of the "from" node; the "to" end of the link is attached to the top edge of the "to" node.  If DIRECTEDFLG is non-NIL and SIDESFLG is non-NIL, the "from" end of the link is attached to the right edge of the "from" node; the "to" end of the link is attached to the left edge of the "to" node.

The remaining fields give the user hooks into the graph editor, which is described below.


The Graph nodes


The GRAPHNODE record has the following fields of interest to the user:

NODELABEL  -  the thing that gets displayed as the node. If this is a bitmap, bitblt is used, if an image object, its imageboxfn and displayfn are used.  Anything else is printed with PRIN3. .

NODEID - a unique identifier.  NODEID's are used in the link fields instead of using pointers to the nodes themselves so that circular Lisp structures can be avoided.  NODEID's are often used as pointers to the structure represented by the graph.

TONODES  -  a list of NODEIDs: a link runs from this node to each node in TONODES.  Entries in this field may be used to specify properties of the lines drawn between nodes, as described below.

FROMNODES  -  a list of NODEIDs: a link runs to this node from each node in FROMNODES.

NODEPOSITION - the location of the center of the node (a POSITION).

NODEFONT -  Specifies the font in which this node's label will be displayed.  It can be any font specification acceptable to FONTCREATE, including a FONTDESCRIPTOR.  NODEFONT is changed by graph edit operations LARGER and SMALLER.  When this happens, the font family may be changed as well as the size.  Default is the value of DEFAULT.GRAPH.NODEFONT (initially NIL).

NODEBORDER - specifies the shade and width of the border around a node via the following values:
	     NIL,0	no border (= border of width 0)
	     T	black border, 1 pixel wide, as before
	     1,2,3...	black border of the given width
	     -1,-2...	white border of the given width
	     (W S)	where W is a fixp and S is a texture or a shade; yields a border W wide filled with
			the given shade S.
Default is the value of DEFAULT.GRAPH.NODEBORDER (initially NIL).

NODELABELSHADE  - contains the background shade of the node.  If this field is non-NIL, then when a node is displayed, the label area for the node is first painted as specified by this field, then the label is printed in INVERT mode.  This does not apply to labels that are bitmaps or image objects.  The legal values for the field are: NIL (same as WHITESHADE), T (same as BLACKSHADE), a texture, or a bitmap.  Default is the value of DEFAULT.GRAPH.NODELABELSHADE (initially NIL).

NODEWIDTH and NODEHEIGHT - Normally, these are set by grapher to be the width and height of the node's NODELABEL.  However, if the user provides integers for these fields, their values will be 	used instead.  This feature can be used to give a node a larger- than-normal "margin" around its label.

Entries in the TONODES field may be used to specify the appearance of the lines drawn between nodes.  If an item in the TONODES of a node N1 is not a NODEID but rather a list of the form:

	(Link% Parameters tonodeid . paramlist) 

then paramlist is interpreted as a property list specifying properties of the link drawn from N1 to tonodeid. 
Properties of paramlist currently noticed are  LINEWIDTH, DASHING, COLOR, and DRAWLINKFN.  The first three are passed directly to DRAWLINE.  For example, if the TONODES for A is:

	((Link% Parameters B LINEWIDTH 4 DASHING (3 3))
	 (Link% Parameters C DASHING (5 1) COLOR 12))

then two dashed lines would emanate from A, with the one to B having width 4 and dashing (3 3), and the one to C having the default width 1, dashing (5 1), and color (if implemented) 12.

If the property DRAWLINKFN is on the list, then its value must be a function to be called instead of DRAWLINE.  It will be passed all the arguments of DRAWLINE plus the paramList as a last argument. 

For convenience, the variable LINKPARAMS is set to the (constant) value Link% Parameters.  When DISPLAYGRAPH scales the graph to the units of a particular output stream, the properties whose names are found on the SPECVAR ScalableLinkParameters will also be scaled.

Graphnodes can be created by the create operator from the record package or with the following function:

   (NODECREATE ID LABEL POSITION TONODEIDS FROMNODEIDS FONT BORDER LABELSHADE)

This function returns a GRAPHNODE with NODEID=ID, NODELABEL=LABEL,  NODEPOSITION=POSITION, NODEFONT=FONT, NODEBORDER=BORDER. and NODELABELSHADE=LABELSHADE.



Laying out a Graph


(LAYOUTGRAPH NODELST ROOTIDS FORMAT FONT MOTHERD PERSONALD FAMILYD)

LAYOUTGRAPH "lays out" a partially specified graph by assigning positions to its graphnodes. It returns a GRAPH record suitable for displaying with SHOWGRAPH.  The input NODELST is a list of GRAPHNODES that partially specifies a graph: only their NODEID, NODELABEL, and TONODES fields need to be filled in.  Optional fields are: NODEFONT,  NODEWIDTH and NODEHEIGHT.  These optional fields will be filled in appropriately if they are NIL.  All other fields will be ignored and/or overwritten.  ROOTIDS is a list of the node identifiers of the nodes that will become the roots.  The other arguments are optional and control the format of the layout.  

FORMAT controls the geometry of the layout.  It is an unordered list of atoms.  There are three basic formats:

COMPACT  [the default] - The graph is layed out as a forest (a set of trees) in such a way that the minimal amount of screen space is used.

FAST - The graph is layed out as a forest, sacrificing screen space for speed.

LATTICE - The graph is layed out as an acyclic directed graph (a lattice).

REVERSE/DAUGHTERS -  The graph is layed out with the to-nodes in reverse order.

These basic formats come in the obvious two flavors:

	HORIZONTAL [the default] - roots at left, links run left-to-right.
	VERTICAL -  roots at the top, links run top-to-bottom. 

The directions can be reversed by including the atom REVERSE in FORMAT.  Thus, for example,  FORMAT=(LATTICE HORIZONTAL REVERSE) lays out horizontal lattices that have the roots on the right, with the links running right-to-left.  FORMAT=(VERTICAL REVERSE) lays out vertical trees that have the roots at the bottom, with links running bottom-to-top.  FORMAT=NIL lays out horizontal trees that have the roots on the left.     

LAYOUTGRAPH creates "virtual" graph nodes to avoid drawing a tangle of messy lines in cases where the graph is not a forest or a lattice to begin with.  It modifies the nodes of NODELST, which  may involve changing some of the TONODES fields to point to new nodes.  The modified NODELST is set into the GRAPHNODES field of a newly created GRAPH record, which is returned as the value of LAYOUTGRAPH.  The creation of virtual nodes depends on whether or not LATTICE is a member of FORMAT.  The forest (i.e., non-LATTICE) case will be described first:
   
Nodes are layed out by traversing the forest top-down, depth-first.  Whenever an already layed out node is found, instead of drawing a link to it that might cut across arbitrary parts of the graph, LAYOUTGRAPH creates a copy of the node (same NODELABEL, different NODEID, no TONODES), lays it down and "marks" both it and the original node (by setting their NODEBORDER fields and NODELABELSHADE fields).  Hence, a marked node means that it occurs at least twice in the forest.  The default is to leave the shade alone and set the border to 1, but the appearance of marked nodes can be controlled by adding (MARK ....) to the FORMAT argument.  The tail of (MARK ....) is a property list.  If it is NIL, marking is suppressed altogether.  If it contains BORDER or LABELSHADE properties. those values will be used in the corresonding fields of marked nodes.  FORMAT adds a few twists to this basic marking strategy.  It can include one or both of these atoms:

COPIES/ONLY - only the new "virtual" nodes are marked.  The original is left unmarked.

NOT/LEAVES - Marking is suppressed when the node has no daughters.

For examples, FORMAT = (COPIES/ONLY NOT/LEAVES) will markbox nodes that are copies of nodes that have daughters (i.e., if you see a mark, the nodes has daughters that aren't drawn).  FORMAT = (NOT/LEAVES) will mark both copies and originals, but only when they have no daughters.  FORMAT = NIL marks originals and copies regardless of progeny.

If FORMAT includes LATTICE, then a node that is the daughter of more than one node is not marked.  Instead, links from all its parents are drawn to it.  No attempt is made to avoid drawing lines through nodes or to minimize line crossings.  However, in HORIZONTAL format, nodes are positioned so that "from" is always left of "to."  Similar conventions hold for the other formats.  In VERTICAL format, for instance, the TONODES of a node are positioned beneath it, and the FROMNODES are positioned above it.  Cyclic graphs can not be drawn using this convention, of course (how can a node be left of itself?).  When LAYOUTGRAPH detects a node that points to itself, directly or indirectly, it creates a "virtual" node as described above, and marks both the original and the copy.  If FORMAT includes COPIES/ONLY, then only the newly created node is marked.


This ends the discussion of the FORMAT argument to LAYOUTGRAPH.  The other arguments are not so complicated.

FONT is a font specification for use as the default NODEFONT.

The remaining three arguments control the distances between nodes.  NILs cause "pretty" defaults based on the size of FONT.  PERSONALD controls the minimum distance between any two nodes.  MOTHERD is the minimum distance between a mother and her daughters.  FAMILYD controls the minimum distance between nodes from different nuclear families. The closest two sister nodes can be is PERSONALD.  The closest that two nodes that are not sisters can be is PERSONALD+FAMILYD.

LAYOUTGRAPH reads but does not change the fields NODEBORDER and NODELABELSHADE of the nodes given it (except for the marked nodes, of course).  Thus, if one is planning on installing black borders around the nodes after the nodes have been layed out (e.g. by RESET/NODE/BORDER described below), it is a good idea to give LAYOUTGRAPH nodes that have white borders.  This will cause the nodes to be layed out far enough apart that when you blacken the borders later, the labels of adjacent nodes will not be overwritten.



Displaying and Editing a Graph

(SHOWGRAPH GRAPH W LEFTBUTTONFN MIDDLEBUTTONFN TOPJUSTIFYFLG ALLOWEDITFLG COPYBUTTONEVENTFN)

SHOWGRAPH displays the nodes in the GRAPH. If W is a window, the graph will be displayed in it.  If the graph is larger than the window, the window is made a scrolling window.  If W is NIL, the graph will be displayed in a window large enough to hold it .  If W is a string, the graph will be displayed in a window large enough to hold it and the window will use the string for the window title.  SHOWGRAPH caches some information in the graphnode fields in order to make scrolling faster.  The graph is stored on the GRAPH property of the window.  SHOWGRAPH returns the window.

If either LEFTBUTTONFN or MIDDLEBUTTONFN are non-NIL, the window is given a BUTTONEVENTFN that, in effect, turns the graph into a menu.  Whenever the left or middle button is depressed and the cursor is over a node, that node will be displayed inverted, indicating that it is selected.  Letting up on the button will call either the LEFTBUTTONFN or MIDDLEBUTTONFN with two arguments: the selected GRAPHNODE (this will be NIL if the cursor was not over a node when the button was released) and the window (from the window, the functions can access the graph via WINDOWPROP).

The graph's initial position is determined by TOPJUSTIFYFLG.  If T, the graph's top edge is positioned at the top edge of the window; if NIL, the graph's bottom edge is positioned at the bottom edge of the window.

If ALLOWEDITFLG is non-NIL, the right button can be used to edit the graph.  (The normal window commands are available by right buttoning in the border or title regions.)  Right buttoning while the control shift is down allows positioning of nodes by tracking the cursor.  Right buttoning with the control shift up brings up a menu of edit operations.   The edit operations allow moving, adding, and deleting of nodes and links.  Adding a node prompts for a NODELABEL, creates a new node with that label, adds it to the graph and allows the user to position it.  Deleting a node removes it (using DREMOVE) from GRAPH after deleting all of the links to and from it.  When the STOP menu command is selected, the graph window is closed.

COPYBUTTONEVENTFN is a function to be run when the user copy-selects from the grapher window.  If this is not specified, the default will simply COPYINSERT a GRAPHER image object. 

Certain fields of the GRAPH record are functions that get called by the graph editor whenever an action is performed on an element in the displayed graph.  They allow the graph to serve as an simple edit interface to the structure being graphed.  Below are the fields of GRAPH and the arguments that the corresponding function will be called.  In all cases GRAPH is the graph being displayed and WINDOW is the window in which it is displayed.
 
	GRAPH.MOVENODEFN(NODE NEWPOS GRAPH WINDOW) called 
	after the user has stopped moving a node interactively
	(i.e. is not called as the node is being moved.)
 
	GRAPH.ADDNODEFN(GRAPH WINDOW) called when the user 
	selects "Add a node" and should return a node or NIL 
	if no new node is to be added.  Node moving operation 
	will be called on the new node after it is create to 
	determine its position.

	GRAPH.DELETENODEFN(NODE GRAPH WINDOW) called when a 
	node is deleted.  Before this function is called, all 
	of the links to or from the node are deleted.

	GRAPH.ADDLINKFN(FROM TO GRAPH WINDOW) called when 
	a link is added. 

	GRAPH.DELETELINKFN(FROM TO GRAPH WINDOW) called when 
	a link is deleted which can be either directly or from 
	deleting a node.

	GRAPH.FONTCHANGEFN(HOW NODE GRAPH WINDOW) called when 
	the user asked for the label on a node to be made larger 
	or smaller.  HOW is one of LARGER or SMALLER.

Efficiency note:   The node labels are reprinted whenever the graph is redisplayed.  If this makes scrolling of a large graph unacceptably slow, some speed-up may be achieved by instructing the Grapher to cache bitmaps of the labels with the nodes so they can be rapidly BITBLTed to the screen (set the variable CACHE/NODE/LABEL/BITMAPS/FLG to T).  The possible gain in time, however, may be offset by the increased storage required for the cache bitmaps.


(DISPLAYGRAPH GRAPH STREAM CLIP/REG TRANS)

Put the specified graph on STREAM (which can be any image stream) with coordinates translated to TRANS.  Some streams might also implement CLIP/REG as a clipping region.  This is primarily to improve efficiency for the display.

(HARDCOPYGRAPH GRAPH/WINDOW FILE IMAGETYPE TRANS)

Produces a file containing an image of GRAPH  (e.g., like SHOWGRAPH, only for files).  If GRAPH/WINDOW is a window, HARDCOPYGRAPH will operate on its GRAPH window property.  The FILE and IMAGETYPE argument are given to OPENIMAGESTREAM to obtain a stream that the graph will be displayed on.  TRANS is a position in screen points (i.e., it will be scaled by to the image stream's DSPSCALE) of the lower left corner of the graph from the lower left corner of the piece of paper. 

Grapher image objects

A graph data structure can be encapsulated in a Grapher image object, so that it can be inserted in Tedit documents or other image structures.  Grapher image objects are constructed by the following function:

(GRAPHEROBJ GRAPH HALIGN VALIGN)

returns a GRAPHER-type image object that will display GRAPH.  HALIGN and VALIGN specify how the graph is to be aligned with respect to the reference point in its host (Tedit file, image object window, etc.).  They can be numbers between 0 and 1, specifying as a proportion of the width/height of the graph the point in the graph that will overlay the reference point (0 means that the graph will sit completely above/to the left of the reference point, 1 means it will sit completely below/to the right).  They can also be pairs of the form (nodespec pos), where nodespec specifies a node that the graph is to be aligned by, and pos specifies where in the node the alignment point is. The nodespec can either be a node id or one of the atoms *TOP*, *BOTTOM*, *LEFT*, *RIGHT*, indicating the topmost, bottommost, etc. node of the graph.  The pos can be a number specifying proportional distances from the lower-left corner of the node, or the atom BASELINE, indicating the character baseline (for VALIGN, or simply 0 for HALIGN).   For example, to align a linguistic tree so that the baseline of the root node is at the reference point, VALIGN would be (*TOP* BASELINE).  The BUTTONEVENTINFN of the image object pops up a single item menu which if selected causes the graph editor to be run.


Miscellaneous functions

(GRAPHREGION GRAPH)

Returns the smallest region containing all of the nodes in GRAPH.

(FLIPNODE NODE DS)

Inverts a region in the stream DS that is 1 pixel bigger all around than NODE's region.  This makes it possible to see black borders after the node has been flipped.

(RESET/NODE/BORDER NODE BORDER STREAM GRAPH)
(RESET/NODE/LABELSHADE NODE SHADE STREAM)

These functions reset the appropriate fields in the node.  If STREAM is a display stream or a window, the old node will be erased and the new node will be displayed.  Changing the border may change the size of the node, in which case the lines to and from the node will be redrawn.  The entire graph must be available to RESET/NODE/BORDER for this purpose, either supplied as the GRAPH argument or obtained from the GRAPH property of STREAM, if it is a window.  Both functions take the atom INVERT as a special value for BORDER and SHADE.  They read the node's current border or shade, calculate what would be needed to invert it, and do so.

(LAYOUTSEXPR SEXPR FORMAT FONT MOTHERD PERSONALD FAMILYD)

Just like LAYOUTGRAPH except it gets its graph as a s-expression rather than a list of GRAPHNODEs.  A formal recursive definition of its first argument is: If the s-expr is an atom, its NODELABEL will be itself and it will have no TONODEs; else it is a list and its car will be taken as its NODELABEL and its cdr, which must be a list of s-exprs, will be taken as its TONODES.  Note that circular s-expressions are allowed.  For example, the following displays a parse tree for the sentence "The program displays a tree."

   [SHOWGRAPH (LAYOUTSEXPR '(S (NP (DET the)(NOUN program))
                               (VP (VERB displays)
                                   (NP (DET a)(NOUN tree))))
 
                          '(VERTICAL) NIL '(HELVETICA 12] 

(DUMPGRAPH GRAPH STREAM)

Graphs cannot be saved on files simply by ordinary print functions such as PRIN2.  This is because the grapher functions use FASSOC (i.e., EQ not EQUAL) to fetch a graphnode given its id, so reading it back in will give the right result only if the id's are atomic.  HPRINT resolves this problem, but it tends to dump too much information:  it will dump a complete description of the nodefont for example, including the character bitmaps.   The function DUMPGRAPH prints the GRAPH out on STREAM in a special, relatively compact encoding that can be interpreted by the function READGRAPH.  DUMPGRAPH and READGRAPH are used in the implementation of GRAPHER image objects.

(READGRAPH STREAM)

Reads information from STREAM starting at the current file pointer, and returns a graph structure equivalent to the one that was given to DUMPGRAPH.   





$<


TIMESROMAN
	HELVETICA
GACHA
	HELVETICA
+ 1
�

…+p0		
H
¡
	

)


6
D­[;
¡›—
Z




	:

	¯

ƒI

.q

	.	

-

u
%c


]



-




*
*

*
%


Ïn




4

	
O	º
b
 
*
^		
*

1/
)








K*
	

 j

i
O
	
	












D
_%	

.	4	
E9–
i

…

K

D

?
5


9
0
]
g
_
A
§*-
+; Æ"	L
ç4b_

L


9
ˆM3

ã
z½�
.

 
/
0
D/	7>u	=
&
µ-»



]
	
…
H
ˆ	p	

	
ô"	‰

.

GJ

°	‚;7
€

ôQ")
*	82
287

%8/

%

(9

);

#
o

+
@%Q
1

'	
	:R[

Ñ
 


%
Î:9-Cg)
n
e




;


(X

,
)

>ý*
3i
:

B	Z	$5	D“
<3=


;

}tµ	S	
S

m	




X¬z¹