MAKEGRAPH documentation

D. Austin Henderson, Jr.
Last revised: March 17, 1983

<LISPUSERS>MAKEGRAPH (and .DCOM) is a package which sits on top of Grapher and helps one create graphs depicting a data structure by walking through it. The central idea is that each point in the walk (and node in the graph) is characterized by a datum/state pair and motion is defined by a graph specification in the form of state transition function. This function is specified by a collection of state specifications, each of which indicates how to display (label and font) the datum when one is in that state and how to find the datum/state pairs which are the sons of that node. Also the state specification may specify additional roots for the walk. The generation of a branch of the graph ceases when either there are no sons of a node, or an already encountered node is revisited (identical datum and identical state). The package contains a function for creating such graphs and an example of its use: a function which graphs the graph specifications themselves. Comments are welcomed.

The main functions:

MAKE.GRAPH (WINDOW TITLE GRAPH.SPECIFICATION ROOTS CONTEXT LEFTBUTTONFN MIDDLEBUTTONFN TOPJUSTIFYFLG DEPTH)

Creates a MAKEGRAPH window. If WINDOW is NIL, then a new one will be created and the user will be prompted to position it. Otherwise, the graph will be shown in WINDOW. The window will be titled with TITLE, will call LEFTBUTTONFN and MIDDLEBUTTONFN on nodes selected (or NIL if selection is made where no node is positioned), and will be justified as indicated by TOPJUSTIFYFLG (a la Grapher). The button functions are defaulted to MAKE.GRAPH.LEFTBUTTONFN (which scrolls the window so that the selected node is in the middle of the window, or if the left shift key is depressed, prints out information about it) and MAKE.GRAPH.MIDDLEBUTTONFN (which provides a menu of two choices: INSPECT - inspects the datum of the node selected, or if the left shift key is depressed, inspects the node itself; and SUB.GRAPH - which opens another MAKEGRAPH window with the same parameters as this one, but with graph starting at the selected node). The arguments to MAKE.GRAPH are added as properties to the window under their argument names. Selecting in the title invokes the functions which are the values of the window properties TITLE.LEFTBUTTONFN and TITLE.MIDDLEBUTTONFN (not in the calling sequence; set by the user if desired; called with a single argument - WINDOW; defaulted to a function which provides a menu of UPDATE and SHOW.GRAPH.SPEC (see functionality below)). The graph is created according to the GRAPH.SPECIFICATION (see below) to depth DEPTH, starting from ROOTS which are (DATUM . STATE) pairs. CONTEXT is an extra argument which is a passed along to all accessing expressions.

A GRAPH.SPECIFICATION is a property list of STATE.SPECIFICATIONs where the properties are the state names. A STATE.SPECIFICATION is a property list whose properties and values are as follows (in this, EXPR means a LISP form which will be evaluated in an environment in which DATUM is bound to the node’s datum, STATE to the node’s state, and CONTEXT to context):

LABEL:an expression returning something which will be printed as the label of the node; if no LABEL property is provided, the string "???" will be used.

FONT:an expression returning the font to be used for this node; if no FONT property is provided, the default font for the grapher will be used.

SONS:a form indicating a list of (DATUM . STATE) pairs to be used in generating the sons of this node; the acceptable forms are any of the following:

(data-expression state-expression) where data-expression returns a list of datum’s for the son nodes, and state-expression is evaluated in the context of each of these in turn to produce the corresponding state of each.

(LIST (datum-expression state-expression) ... (datum-expression state-expression)) a template of expressions which are evaluated individually to produce a list of sons of the same form, viz. (DATUM . STATE) pairs.

(EVAL expression) the expression returns a list of (DATUM . STATE) pairs of the sons.

(UNION sons-spec ... sons-spec) where each sons-spec is any of these forms (recursively).

(TRACE sons-spec) a device for helping debug graph specifications; the value is the value of sons-specs; the user is given the chance to INSPECT them after they have been generated.

ROOTS:like SONS, except the resulting (DATUM . STATE) pairs are used as possibly additional roots of the graph.

MAKE.GRAPH.CONSTRUCT (GRAPH.SPECIFICATION INITIAL.ROOTS CONTEXT DEPTH)

This is the functional heart of MAKE.GRAPH broken out for those who wish to handle their own interacts with grapher and the window package. It produces a list of graphnodes with labels and sons as specified by GRAPH.SPECIFICATION (see MAKEGRAPH), starting from INITIAL.ROOTS which are (DATUM . STATE) pairs. CONTEXT is an extra argument which is a passed along to all accessing expressions. Returns the list of graphnodes.

MAKE.GRAPH.FIND.ROOTS (GRAPH.SPECIFICATION INITIAL.ROOTS CONTEXT DEPTH)

Finds the real roots from a set of initial roots, using the same processing as MAKEGRAPH uses. This is helpful when you want to hand a "correct" set of roots of a structure to MAKEGRAPH without having to explore the dependencies within that structure. As with MAKEGRAPH, the data structure is processed according to the GRAPH.SPECIFICATION (see MAKEGRAPH), starting from INITIAL.ROOTS which are (DATUM . STATE) pairs. CONTEXT is an extra argument which is a passed along to all accessing expressions. Returns the real roots as a list of (DATUM . STATE) pairs.

Supporting functions:

MAKE.GRAPH.UPDATE.WINDOW (WINDOW)

Uses the window properties (which may have been changed) to reinvoke MAKE.GRAPH on the window.

MAKE.GRAPH.SHOW.SPEC (GRAPH.SPECIFICATION)

Uses MAKE.GRAPH to produced a graph of a GRAPH.SPECIFICATION. It uses as the graph.specification for this layout the value of the variable MAKE.GRAPH.SPEC.SPEC which presents GRAPH.SPECIFICATION (reflectively) as a graph.specification. (GRAPH.SPECIFICATION can serve as a template for other graph.specifications. It is a fairly complex 9-state specification. For a simpler example see below under MAKE.GRAPH.SHOW.LIST.)

MAKE.GRAPH.EXAMPLE.1 ( )

Calls MAKE.GRAPH.SHOW.SPEC on MAKE.GRAPH.SPEC.SPEC.

MAKE.GRAPH.SHOW.LIST (OBJECT)

Uses MAKE.GRAPH to produced a graph of an arbitrary Lisp object. It uses as the graph.specification for this layout the value of the variable MAKE.GRAPH.LIST.SPEC which presents OBJECT as a tree whose nodes are LISTPs and whose leaves are non-LISTPs. (MAKE.GRAPH.LIST.SPEC is the simple 1-state specification below, included here as an example of a graph.specification.

(OBJECT (DOC (ANY LISP OBJECT) - some documentation
LABEL (COND((LISTP DATUM) "( )")
(T DATUM))
SONS ((COND((LISTP DATUM) DATUM)
(T NIL))
(QUOTE OBJECT))
)
)

For a more complex example see above under MAKE.GRAPH.SHOW.SPEC.)

MAKE.GRAPH.EXAMPLE.2 ( )

Calls MAKE.GRAPH.SHOW.LIST on MAKE.GRAPH.LIST.SPEC; that is, produces a graph of this simple graph.specification as a list. Notice that selecting the title command UPDATE in this window will yield a different graph of the same structure, viz. as a graph.specification.

Other useful functions:

MAKE.GRAPH.DATUM (NODE)

Returns the DATUM associated with the graph node NODE.

MAKE.GRAPH.STATE (NODE)

Returns the STATE associated with the graph node NODE.

MAKE.GRAPH.FATHER (NODE)

Returns the graph node which is the father of the graph node NODE.