Java Reference
In-Depth Information
Node
Preds
(
Y
)
IN
Y
Soln
(
Y
)
NeedEvaluate
(
Z
)
Again?
Y
Marker
94
Marker
95
Marker
96
Marker
97
1
{
4
}
{}
{}
{}
3
{
1
}
{}
{
3
}
{
4
}
4
{
3
,
8
}
{
3
}
{
3
}
{
5
,
6
,
1
}
true
6
{
4
}
{
3
}
{
3
,
6
}
{
7
}
7
{
6
}
{
3
,
6
}
{
3
,
6
,
7
}
{
8
}
8
{
7
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{
4
}
true
5
{
4
}
{
3
}
{
3
}
{}
2
{
1
}
{}
{}
{}
1
{
4
}
{
3
}
{
3
}
{
2
,
3
}
3
{
1
}
{
3
}
{
3
}
{
4
}
4
{
3
,
8
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{
5
,
6
,
1
}
true
6
{
4
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{
7
}
7
{
6
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{}
8
Not evaluated
5
{
4
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{}
2
{
1
}
{
3
}
{
3
}
{}
1
{
4
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{
2
,
3
}
3
{
1
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{
4
}
4
{
3
,
8
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{}
6
Not evaluated
7
Not evaluated
8
Not evaluated
5
Not evaluated
2
{
1
}
{
3
,
6
,
7
}
{
3
,
6
,
7
}
{}
Figure 14.54: Evaluation of the framework from Figure 14.53.
erative evaluation proceeds using the graph's interval order [ 1
,
3
,
4
,
6
,
7
,
8
,
5
,
2]
then the computation proceeds as shown in Figure 14.54.
The first pass propagates the solution
to node 8. After that first
pass, information from node 8 is available for node 4. After the second pass,
the information from node 8, present now at node 4, is available for node 1.
This example demonstrates that for some frameworks the number of passes
required for convergence is related to the number and structure of the graph's
back edges. Each pass can propagate all available information forward in
topological order, but extra passes are required to propagate information along
the back edges.
If
p
is the longest path in the flow graph comprised only of back edges, then
the length of
p
determines howmany passes are required to obtain convergence
{
3
,
6
,
7
}
