MAKEGRAPH documentation D. Austin Henderson, Jr. Last revised: March 21, 1984 - rrb 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.LIST (OBJECT) This is a simple example function. Suppose we wanted to layout list structure as a graph. In the graph, we wanted a list to be labeled by "()" and its sons to be the elements of the list. For example, the graph of '(A B (C D)) should look something like: A / ( )-B C \ / ( ) \ D MAKE.GRAPH.SHOW.LIST uses MAKE.GRAPH to produce such graphs. It presents OBJECT as a tree whose nodes are LISTPs and whose leaves are non-LISTPs. The layout specification that it uses (saved in the value of the variable MAKE.GRAPH.LIST.SPEC) is included here as an example of a simple, 1-state graph.specification. (OBJECT (DOC (ANY LISP OBJECT) - some documentation LABEL (COND ((LISTP DATUM) "( )") (T DATUM)) SONS ((COND ((LISTP DATUM) DATUM) (T NIL)) (QUOTE OBJECT)) )) 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.MAKE.GRAPH.SHOW.LIST) MAKE.GRAPH.EXAMPLE.1 ( ) Calls MAKE.GRAPH.SHOW.SPEC on MAKE.GRAPH.SPEC.SPEC. 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. GACHA UU3GACHA =GACHA UU3GACHA  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN Y TIMESROMAN  TIMESROMAN * TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN Z TIMESROMAN  TIMESROMAN C TIMESROMAN  TIMESROMAN TIMESROMAN  TIMESROMAN  TIMESROMAN UU3GACHA  TIMESROMAN UU 3GACHA UU 3GACHA k TIMESROMAN U3GACHA 4 TIMESROMAN UU 3GACHA k TIMESROMAN UU 3GACHA TIMESROMAN y GACHA TIMESROMAN y GACHA TIMESROMAN y GACHA TIMESROMAN  GACHA  TIMESROMAN  TIMESROMAN  TIMESROMAN  GACHA  TIMESROMAN  TIMESROMAN P TIMESROMAN  GACHA  TIMESROMAN  TIMESROMAN S TIMESROMAN  GACHA  TIMESROMAN  TIMESROMAN X TIMESROMAN TIMESROMAN N TIMESROMAN  GACHA p TIMESROMAN y GACHA F TIMESROMAN U3GACHA  TIMESROMAN UU 3GACHA G TIMESROMAN U3GACHA 0 TIMESROMAN GACHA  TIMESROMAN GACHA ! TIMESROMAN U3GACHA ^ TIMESROMAN UU 3GACHA  TIMESROMAN U3GACHA  TIMESROMAN <GACHA = TIMESROMAN GACHA * TIMESROMAN U3GACHA { TIMESROMAN UU 3GACHA  TIMESROMAN U3GACHA 3 TIMESROMAN UU 3GACHA A TIMESROMAN UU 3GACHA  TIMESROMAN U3GACHA r TIMESROMAN TIMESROMAN y TIMESROMAN  TIMESROMAN  TIMESROMAN GACHA  TIMESROMAN GACHA  TIMESROMAN U3GACHA 6 TIMESROMAN UU 3GACHA  TIMESROMAN U3GACHA 6 TIMESROMAN UU 3GACHA  TIMESROMAN U3GACHA B TIMESROMAN UU 3GACHA rz