Information Technology Reference
In-Depth Information
5)
Set
←
{non-independent children of
N
having all their parents in the
sequence}
6) else
7) if
{
independent children of
N } =∅
8)
Set
←{
independent children of
N }
9)
NextNode
←
node
∈
Set
| node has least # of descendants among the nodes
in
Set
The depth-first search (DFS) in line 1 satisfies the second heuristic. The first
if
statement (line 4) guarantees the third heuristic, and finally, the node selection
process in line 9 satisfies the first heuristic.
Applying this algorithm to the graph of
Fig. 6
, we can generate either the fifth
or eleventh sequence. This is dependent on whether
c
or
d
was chosen first as the
child with the least number of independent-children. It should be noted that neither
of these sequences is the optimal sequence. However, they are reasonably better than
other sequences and are obtained in polynomial time. Nodes with in-degree and out-
degree of zero are considered harmful and thus are not handled by the algorithm.
Having them in the middle of the sequence introduces delays between objects along
the sequence. Therefore, they are excluded from the set of nodes to be traversed and
handled by being appended to the end of the sequence. In addition, when multiple
DAGs are to be mapped along the air channel, the mapping should be done with no
interleaving between the nodes of the DAGs.
4 . 2 P a r t i a l l y L i n e a r O r d e r A l g o r i t h m
In a DAG representation of a complex objects, nodes are connected through se-
mantic links with different degrees of connectivity—the frequency of access pat-
tern
[23]
. This observation is the basis of the PartiallyLinearOrder algorithm that
clusters strongly connected objects closer to each other. This algorithm assumes a
weighted DAG as its input and produces a linear sequence. It combines the nodes
(single_node) of the graph into multi_nodes in a descending order of their connec-
tivity (semantic links). The insertion of single_nodes within a multi_node respects
the linear order at the granularity level of the single_nodes. The multi_nodes are
merged (with multi_nodes or single_nodes) at the multi_node granularity, without
interfering with internal ordering sequences of a multi_node
[14]
.
PartiallyLinearOrder Algorithm
1) for
every weight
w
s
in descending order
2)
for
every two nodes
N
1
&
N
2
connected by
w
s
3)
merge
N
i
&
N
j
into one multi_node
