Information Technology Reference
In-Depth Information
improvements have been proposed. Even if these methods do not scale to large
datasets, they guarantee the convergence of the system.
All force-based algorithms follow the same concept, and algorithm 1 summarizes
the four main steps of these methods. In the following, we compare three of the most
commonly used implementations for each step of the algorithm (
Eades
,
1984
;
Frick
et al.
,
1995
;
Fruchterman & Reingold
,
1991
).
Data: A graph
Result: A force directed layout
Calculate Initial Position (CIP)
while not equilibrium do
Compute Attractive/Repulsive Forces (CARF)
Compute Displacement Vector (CDV)
Move Nodes (MN)
end
Force-directed algorithms can be summarized in four steps. CIP initializes the
system before running the simulation, CARF implements the interaction rules of
the system, CDV manages convergence of the system and MN applies the result to
the system.
Eades (
1984
):
To speed up the convergence of the system Eades (
1984
) proposed replacing the
Hooke's forces or Hooke's law with his own force model where
P
u
is the coordinates
of a node
u
,
−−→
p
u
p
v
is the unit vector co-directional with
−−→
P
u
P
v
,
dist
(
u
,
v
)
is the norm
of
−−→
c
re p
are two constants
that define the strength of the spring. Attractive and repulsive forces are given by
the following formulas:
P
u
P
v
,
l
is the ideal length of an edge (i.e., spring), and
c
att
,
log
dist
(
u
,
v
)
·
−−→
f
att
(
u
,
v
)=
c
att
·
p
u
p
v
(6.1)
length
c
re p
dist
2
·
−−→
f
re p
(
u
,
v
)=
p
v
p
u
(6.2)
(
u
,
v
)
and the total force exerted on a node
u
is as follows:
)=
∑
(
)+
∑
(
f
total
(
(
,
(
,
)
u
f
att
u
v
f
re p
u
v
(6.3)
u
,
v
)
∈
E
u
,
v
)
∈
E
Note that the repulsive forces are computed between all pairs of non-neighbor
nodes. Because the MN phase is performed in a synchronous way, i.e., all nodes
are moved at the same time, Eades' method used a constant
to limit the
movements of a nodes. The displacement vector is computed as follows:
δ
∈
[
0
,
1
]
disp
(
u
)=
δ
·
f
total
(
u
)
(6.4)
Search WWH ::
Custom Search