Java Reference
In-Depth Information
1
2
3
11
4
9
12
13
5
8
10
6
7
Figure 14.10: Sample flow graph.
computed for that graph is shown in in Figure 14.12.
The algorithm does not consider successors of node
X
in any particular
order at Marker
26
. A graph's DFST is therefore not necessarily unique. It
is convenient to depict a DFST so that its children are drawn left-to-right in
the order of their discovery by depth-first search, as shown in Figure 14.12.
However, the algorithm collects the children of node
X
by insertion at the
head
of a linked list (Markers
27
and
28
). The resulting list therefore contains
children in the
reverse
order of their discovery:
•
The last child of
X
discovered bydepth-first searchwill appear as
child
(
X
).
•
The child of
X
discovered just before node
Y
will appear as
sibling
(
Y
).
The traversal shown in Figure 14.11 therefore has the e
ect of traversing the
DFST in
right-to-left preorder
, which is an order conducive to evaluation of
data flow framework as discussed in Section 14.5.
A DFST is constructed using some of a graph's edges. For those graph
edges not participating in the tree, some algorithms make use of their relation-
ship to the structure of the DFST. Figure 14.13 shows all edges of Figure 14.10
ff
