## Back Edges and Reducibility

**Introduction:** A back edge is an edge a -> b whose head b dominates its tail a. For any flow graph, every back edge is retreating, but not every retreating edge is a back edge. A flow graph is said to be reducible if all its retreating edges in any depth-first spanning tree are also back edges. In other words, if a graph is reducible, then all the DFST's have the same set of retreating edges, and those are exactly the back edges in the graph. If the graph is non-reducible (not reducible), however, all the back edges are retreating edges in any DFST, but each DFST may have additional retreating edges that are not back edges.

These retreating edges may be different from one DFST to another. Thus, if we remove all the back edges of a flow graph and the remaining graph is cyclic, then the graph is non-reducible, and conversely. Flow graphs that occur in practice are almost always reducible. Exclusive use of structured flow-of-control statements such as if-then-else, while-do, continue, and break statements produces programs whose flow graphs are always reducible. Even programs written using goto statements often turn out to be reducible, as the programmer logically thinks in terms of loops and branches.

**Depth of a Flow Graph: **Given a depth-first spanning tree for the graph, the depth is the largest numberof retreating edges on any cycle-free path. We can prove the depth is nevergreater than what one would intuitively call the depth of loop nesting in theflow graph. If a flow graph is reducible, we may replace "retreating" by "back"in the definition of "depth," since the retreating edges in any DFST are exactlythe back edges. The notion of depth then becomes independent of the DFSTactually chosen, and we may truly speak of the "depth of a flow graph," ratherthan the depth of a flow graph in connection with one

**Figure 9.44: Execution of Algorithm 9.41 on the flow graph in Fig. 9.43**

of its depth-first spanningtrees.

**Example:** In Fig. 9.42, the depth is 3, since there is a path

**10 -> 7 -)> 4 ->• 3**

with three retreating edges, but no cycle-free path with four or more retreating edges. It is a coincidence that the "deepest" path here has only retreating edges; in general we may have a mixture of retreating, advancing, and cross edges in a deepest path.