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