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 (inclusion relation) and a set of primitive edges . Since no frame can be nested into a primitive node or into itself, the nesting relation can be seen as a tree with as inner nodes and 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).