Java Reference
In-Depth Information
where s isaproperancestorof W , which is a proper ancestor of Y ,and
there is no path p in the graph from s that reaches Y without including W .
We then have the relation
s W Y
which precludes s from immediately dominating Y .
Definition 14.7 Consider nodes A, B, and C in a DFST. Node B is between A
and C i ff A B, B C, A B, and B C. In other words, A is a proper ancestor
of B and B is a proper ancestor of C.
The intervening ancestors between A and C are defined as the set of all nodes
that are between AandC.
In Figure 14.19(b), nodes X and Y are the intervening ancestors between s
and Z .
Based on Lemma 14.6, imagine that an ancestor s of Y tries to establish
itself as Y 's immediate dominator. It can do so by using a path that avoids all
nodes in the DFST between itself and Y . Such a path can be as simple as an
edge from s to Y .
Definition 14.8 Nodesisa sneaky ancestor of Y if s can reach Y using a path
that avoids all ancestors between s and Y.
The manner in which node s can be a sneaky ancestor of Y can be analyzed
with respect to the flow graph edge classification given in Section 14.2.4:
( s −→
tree
Y ) : TheDFSTparent of Y is vacuously sneaky. There are no intervening
ancestors, and parent ( Y ) can certainly reach Y .
( s −→
chord Y ) : If ( s , Y )
∈E f ,then s is sneaky by definition.
( s +
T −→
cross Y ) : If Y is the target of a cross edge, then Figure 14.19(a) shows
how s could initiate a path that avoids intervening ancestors and con-
cludes with the edge T Y .Thee
E f contained the
edge ( s , Y ), as shown by the dashed edge in Figure 14.19(a).
In this case, we say that s is sneaky using the cross edge T Y .
ff
ect is the same as if
( s +
Z −→
back Y ) : If Y is the target of a back edge, then Figure 14.19(b) shows
how s could initiate a path that avoids intervening ancestors, enters the
depth-first spanning subtree rooted at Y , and concludes with the edge
Z Y .Thee
E f contained the edge ( s , Y ), as shown
by the dashed edge in Figure 14.19(b).
In this case, we say that s is sneaky using the back edge Z Y .
ff
ect is the same as if
 
Search WWH ::




Custom Search