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 (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

• Manual selection: point at individual nodes with the mouse, or drag a rectangle which contains all nodes to be selected, etc. If the group of nodes is very large and accidentally not placed closely together, manual selection is awkward and involved.
• Algorithmic selection: an algorithm to traverse the graph is used to collect the selected nodes. The user has only to select the kind of traversal.

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:

• the path region of a set S of start nodes, a set T of end nodes and a class C is the set of nodes reachable from a start node by a path of edges of class C which does not contain an end node . Folding parts of a control flow graph (Fig. 29, middle and right) is done by selecting the path region between two delimiting nodes, and collapsing it into one node.
• the neighbor region of S and C with radius n is the set of nodes reachable from a start node by a path of edges of class C with the maximum length n. Folding a subtree (Fig. 28) is done by selecting the neighbor region of the subtree root node with radius , and collapsing it into one node.

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).