Information Technology Reference
In-Depth Information
4) for
every multi_node
MN
5)
w
m
= w
s
−
1
6) for
every weight
w
m
in descending order
7) while
∃
adjacent_node
AN
connected to
MN
8) if
∃
an edge in both directions between
MN
&
AN
9)
compute
WeightedLinearDistance
MN
_
AN
&
WeightedLinearDistance
AN
_
MN
10)
merge
MN
&
AN
into one multi_node, based on the appropriate
direction
In the algorithm, the
for loop
in line 2 merges single_nodes together to generate
multi_nodes. The
for loop
starting at line 4 merges the multi_nodes with adjacent
multi_nodes or single_nodes (note that
AN
could be either a multi_node or a sin-
gle_node). To guarantee a minimum distance among related objects, the ordering of
a merge between a multi_node and an adjacent node is based on the shorter weighted
linear distances between the two of them in both directions.
Figure 13
depicts an ex-
ample of the running process of this algorithm.
(a)
(b)
bfgacheijd
(c)
F
IG
. 13. Application of PartiallyLinearOrder algorithm. (a) Original graph; (b) First and second iter-
ations; (c) Third iteration.