Compound Graphs and Dynamic Grouping next up previous
Next: Layout of Compound Graphs Up: Grouping and Folding Previous: Grouping and Folding

Compound Graphs and Dynamic Grouping

In all these cases, we don't deal any more with flat graphs G = (V, E), but with compound graphs. A compound graph consists of a set V of primitive nodes, a set F of frames, a nesting relation tex2html_wrap_inline2838 (inclusion relation) and a set of primitive edges tex2html_wrap_inline2840 . Since no frame can be nested into a primitive node or into itself, the nesting relation can be seen as a tree tex2html_wrap_inline2842 with tex2html_wrap_inline2844 as inner nodes and tex2html_wrap_inline2236 as leaves.

Figure 27: Compound Graph

If the structure of the graph is static (as in applications such as Fig. 25 and 26) the nesting is defined in the graph specification. It is also useful to group nodes dynamically by user operations. For instance, during the analysis of large syntax trees, it is convenient to fold interactively parts of the tree that are currently not in the focus of interest (Fig. 28). Another example is to approximate paths of the control flow graph if only the reachability of statements but not the exact path between statements must be inspected (Fig. 29, middle and right). There are several possibilities for grouping selections:

Figure 28: Folding of Syntax Tree

Figure 29: Path Compression and Annotation Hiding in Control Flow Graph

Henry [He92] describes a system with a generic interface for selection of groups of nodes, and shows applications of algorithmic selections by reachability or shortest path algorithms. In compiler construction, the graphs are usually partitioned such that there are different classes of edges. For instance, the program graph of Fig. 25 is an interwoven compound graph consisting of edges of the classes file dependencies, procedure calls, and control flow. By including edge classes in the graph specification, it is possible to make detailed algorithmic selections. Examples:

Many compiler graphs have annotations, e.g. syntax trees with type attributes, control flow graphs with data flow information etc. In these cases, we have a main graph (tree, control flow graph) and smaller annotations (type trees, data flow lists) at each node of the main graph. To hide or expose all annotations at once, we select a node class. With hidden nodes, also all adjacent edges disappear (Fig. 29, left and middle).

next up previous
Next: Layout of Compound Graphs Up: Grouping and Folding Previous: Grouping and Folding

Georg Sander
Thu Aug 1 15:27:34 PDT 1996