Information Technology Reference
In-Depth Information
F
IG
. 12. Access patterns for our running example using the Least-Cost Path method.
4 . 1 A p p r o x i m a t e L i n e a r O r d e r A l g o r i t h m
Definition 3.
In a DAG representation of a complex object, an independent node is
a node that has either one or no parent. In
Fig. 6
, node
e
is an independent node
whereas node
h
is not. A graph containing only independent nodes makes up a for-
est.
Heuristic rules
:
Order the children of a node based on their number of descendants in ascend-
ing order—the child with the least number of descendants is placed first in the
sequence.
Once a node is selected, all of its descendants should be visited and placed
on the sequence in a depth first manner, without any interruption from breadth
siblings.
If a node has a non-independent child, with all of its parents already visited,
the non-independent child should be inserted in the linear sequence before any
independent child.
The ApproximateLinearOrder is a greedy algorithm based on the aforementioned
heuristic rules. It starts by selecting a node with an in-degree of zero and out-degree
of at least one
[16]
.
ApproximateLinearOrder Algorithm
1)
traverse DAG using DFS traversal and as each node is traversed
2)
append the traversed node
N
to the sequence
3)
remove
N
from {nodes to be traversed}
4) if
{non-independent children of
N
having all their parents in the sequence}
=∅
