Java Reference
In-Depth Information
Node Chord or Tree Cross or Back
Semi
Edge from
Edge from
Va l ue
13
11
11
12
11
11
13
11
11
2
2
12
11
10
9
9
9
3
3
8
4
4
9
3
7
6
6
12
2
6
5
5
8
3
10
3
5
4
4
6
3
4
3
3
2
2
3
2
2
1
1
5
2
2
1
1
1
∅
∅
∅
Figure 14.22: Computing the semidominators for the graph shown in
Figure 14.13.
depth-first numbering. For each node
Y
, all nodes semidominated by
Y
are
examined at Marker
49
. Recall that these nodes can be retrieved using the
linked list managed at Markers
42
and
43
in Figure 14.21.
Lemma 14.12
The node sdom
(
Z
)
dominates Z if and only if for all ancestors t
of Z between itself and sdom
(
Z
)
,sdom
(
t
)
<
sdom
(
Z
)
.
Proof: Left as exercise Exercise 20. For intuition, consult the example in
Figure 14.23.
Each node
Z
that is semidominated by
Y
is tested against the condition spec-
ified in Lemma 14.12 by Marker
51
.AtMarker
50
, semidominators have
already been computed for all nodes. Therefore, the result returned
eval
(
Z
)
