Java Reference
In-Depth Information
Node
Header
0 1
2
0
X
1
X
10
X
2
X
8
X
9
X
3
X
4
X
5
X
6
X
7
X
Figure 14.37: Nodes from Figure 14.32 listed in interval order. The
interval header for each node is marked with an X.
the outermost interval strongly connected. All nodes except the flow graph
root
could then be processed by the algorithm prior to Marker
74
.
Although intervals could have been constructed as they were discovered,
the algorithm postpones construction until Marker
75
,sothatnodescanbe
organized into intervals using the following special order:
Definition 14.21
Consider a flow graph
G
f
=
(
N
f
,E
f
)
and its associated depth-
first spanning tree T.
1. The
topological order
of
G
f
using T is defined by the partially ordered set
TopOrder
(
G
f
,
T
)
=
(
N
f
,
)
:
X
Y
⇐⇒
(
X
,
Y
)
∈E
f
and Y
X
Thus, nodes X and Y are topologically ordered i
ff
they are related by a tree,
chord, or cross edge in their flow graph.
2. Given an interval h constructed from
G
f
using T, the
interval order
of
h is a total ordering of the interval's nodes that respects the partial order
TopOrder
(
G
f
,
T
)
.
As described in Section 14.5.1, algorithms that propagate information through
paths of an interval are most e
cient if nodes are visited in interval order.
Recalling the discussion in Section 14.2.4, interval order is obtained by adding
nodes to intervals in a right-to-left preorder traversal of the depth-first span-
ning tree. Figure 14.37 lists nodes in this order and shows how they are
partitioned into intervals.
