Java Reference
In-Depth Information
foreach
Y
∈N
eg
do
Soln
(
Y
)
←
NeedEvaluate
(
Y
)
91
←
true
NodeOrder
←
[ Right-to-left preorder ]
repeat
again
←
false
foreach
Y
∈N
eg
order
(
NodeOrder
)
do
92
if
NeedsEvaluate
(
Y
)
then
NeedsEvaluate
(
Y
)
93
←
false
OldSoln
←
Soln
(
Y
)
IN
Y
←
(
Soln
(
X
))
94
X
∈
Preds
(
Y
)
Soln
(
Y
)
←
f
Y
(
IN
Y
)
if
Soln
(
Y
)
95
OldSoln
then
foreach
Z
∈
Succs
(
Y
)
do
NeedEvaluate
(
Z
)
←
true
96
again
←
again
or
Z
Y
97
until
again
=
false
Figure 14.51: Better iterative evaluation.
•
Nodes could be considered in a better order at Marker
86
.Ifnodesare
chosen in order [ 1
ce instead of the 4 passes
shown in Figure 14.50. Actually, the solution is achieved in a single pass,
but the extra pass is required by Figure 14.48 to detect termination.
To obtain the fastest results, a node
Y
should be visited only after all
of its predecessors have updated their solutions. When an evaluation
graph has a cycle, such ordering is possible only to a certain extent. The
algorithm shown in Figure 14.11 is based on Definition 14.21. Nodes are
visited in a right-to-left preorder traversal of their depth-first numbering
(
interval order
). Except for back edges, this traversal visits all prede-
cessors of
Y
before visiting
Y
. The right-to-left preorder traversal of the
nodes in Figure 14.49 is [ 1
,
3
,
4
,
5
,
2 ], then 2 passes su
,
3
,
4
,
5
,
2].
•
The outer loop at Marker
85
need execute only if information changes
along a
back edge
.Thetestforabackedge(
)atMarker
97
can be
performed in
constant time
, as discussed in Section 14.2.4.
These improvements are incorporated in the algorithm shown in Figure 14.51.
Marker
92
considers the nodes in interval order, using right-to-left pre-
order. Only those nodes marked for evaluation are considered at Marker
93
.
