18.1 Graph Formatting Functions

format-graph-from-roots  root-objects object-printer inferior-producer &key stream orientation cutoff-depth merge-duplicates duplicate-key duplicate-test generation-separation within-generation-separation center-nodes arc-drawer arc-drawing-options graph-type (move-cursor t) [Function]

Draws a graph whose roots are specified by the sequence root-objects. The nodes of the graph are displayed by calling the function object-printer, which takes two arguments, the node to display and a stream. inferior-producer is a function of one argument that is called on each node to produce a sequence of inferiors (or nil if there are none). Both object-printer and inferior-producer have dynamic extent. [annotate]

The output from graph formatting takes place in a normalized +y-downward coordinate system. The graph is placed so that the upper left corner of its bounding rectangle is at the current text cursor position of stream. If the boolean move-cursor is true (the default), then the text cursor will be moved so that it immediately follows the lower right corner of the graph. [annotate]

The returned value is the output record corresponding to the graph. [annotate]

stream is an output recording stream to which output will be done. It defaults to *standard-output*. [annotate]

orientation may be either :horizontal (the default) or :vertical. It specifies which way the graph is oriented. CLIM implementations are permitted to extend the values of orientation, for example, adding :right or :left to distinguish between left-to-right or right-to-left layouts. [annotate]

cutoff-depth specifies the maximum depth of the graph. It defaults to nil, meaning that there is no cutoff depth. Otherwise it must be an integer, meaning that no nodes deeper than cutoff-depth will be formatted or displayed. [annotate]

If the boolean merge-duplicates is true, then duplicate objects in the graph will share the same node in the display of the graph. That is, when merge-duplicates is true, the resulting graph will be a tree. If merge-duplicates is false (the default), then duplicate objects will be displayed in separate nodes. duplicate-key is a function of one argument that is used to extract the node object component used for duplicate comparison; the default is identity. duplicate-test is a function of two arguments that is used to compare two objects to see if they are duplicates; the default is eql. duplicate-key and duplicate-test have dynamic extent. [annotate]

Note: I think it might be desirable if the duplicate-test argument were to be limited to one of the family of functions that is acceptable as :test for MAKE-HASH-TABLE. That would permit an easy constant-time lookup to detect duplicate nodes. There doesn't seem like a substantial offsetting downside to this limitation, since you have complete freedom to define the duplicate-key. [edit]-- Robert Goldman 2005-07-21 17:56Z

1. To follow up to my own comment, I've become convinced by other developers that this restriction WOULD violate the specification. And it seems relatively easy to make a method that's optimized for the common case where one of the hash-compatible equality predicates is used.

2. The sentence beginning "That is, when merge-duplicates is true..." seems backward. If merge-duplicates is true, than the graph can only be a tree by the happy accident of there being no duplicates! In general, it must be a graph type that accepts either cycles or cycles in its undirected dual.

[edit]-- Robert P. Goldman 2005-08-10 00:57Z

generation-separation is the amount of space to leave between successive generations of the graph; the default should be chosen so that the resulting graph is visually pleasing. within-generation-separation is the amount of space to leave between nodes in the same generation of the graph; the default should be chosen so that the resulting graph is visually pleasing. generation-separation and within-generation-separation are specified in the same way as the inter-row-spacing argument to formatting-table. [annotate]

When center-nodes is true, each node of the graph is centered with respect to the widest node in the same generation. The default is false. [annotate]

arc-drawer is a function of seven positional and some unspecified keyword arguments that is responsible for drawing the arcs from one node to another; it has dynamic extent. The positional arguments are the stream, the "from" node's object, the "to" node's object, the "from" x and y position, and the "to" x and y position. The keyword arguments gotten from arc-drawing-options are typically line drawing options, such as for draw-line*. If arc-drawer is unsupplied, the default behavior is to draw a thin line from the "from" node to the "to" node using draw-line*. [annotate]

graph-type is a keyword that specifies the type of graph to draw. All CLIM implementations must support graphs of type :tree, :directed-graph (and its synonym :digraph), and :directed-acyclic-graph (and its synonym :dag). graph-type defaults to :digraph when merge-duplicates is true, otherwise it defaults to :tree. Typically, different graph types will use different output record classes and layout engines to lay out the graph. However, it is permissible for all of the required graph types to use exactly the same graph layout engine. [annotate]


Note: Argh! Why is this function not &key &allow-other-keys? Without this admittedly compatible extension, it's insanely hard to write other forms of graph formatting. [edit]-- Christophe Rhodes 2005-05-10 18:39Z