Information Technology Reference
In-Depth Information
(a)
(b)
(c)
(d)
Fig. 3.
Awareness of ports is important to achieve good node positioning. (a) and (c)
show internal representations of what is passed to the layout algorithm, (b) and (c)
show the resulting drawings. (a) is unaware of ports and yields node positions that
introduce an edge crossing in (b). In (c) ports are considered and the unnecessary
crossing is avoided in (d). Note, however, while the chance is higher that (c) is cross
free, it is not guaranteed.
2.1 Constrained Stress-Minimizing Node Positioning
Traditional stress models for graph layout expect a simple graph without ports,
so a key idea in order to handle data flow diagrams is to create a small node
to represent each port, called a
port node
or
port dummy
,asinFig.3c.If
D
is
the set of all these, and
ʴ
:
P
D
maps each port to the dummy node that
represents it, we construct a new graph
G
=(
V
,E
)where
V
=
V
ₒ
∪
D
,and
E
=
{
(
ʴ
(
p
1
)
,ʴ
(
p
2
)) : (
p
1
,p
2
)
∈
E
}∪{
(
ˀ
(
p
)
,ʴ
(
p
)) :
p
∈
P
}
includes one edge representing each edge of the original graph, and an edge
connecting each port dummy to its parent node. We refer to the
v
∈
V
as
proper
nodes.
Depending on the specified port constraints (R2) we restrict the position of
each port dummy
ʴ
(
p
) relative to its parent node
ˀ
(
p
) using separation con-
straints. For instance, for a rigid relative position we use one separation con-
straint in each dimension, whereas we retain only the
x
-constraint if
ʴ
(
p
) need
only appear on the left or right side of
ˀ
(
p
). The use of port nodes allows the
constrained stress-minimizing layout algorithm to untangle the graph while be-
ing aware of relative port positions, resulting in fewer crossings, as illustrated in
Fig. 3, and a better overall placement of nodes.
Our constrained stress-based layout uses the methods of Dwyer et al. [3] to
minimize the
P-stress
function [7], a variant of
stress
[9] that does not penalise
unconnected nodes being more than their desired distance apart:
w
uv
(
p
uv
−
b
(
u,v
))
+
2
−
2
(
b
(
u,v
)
)
+
2
+
(
u,v
)
∈E
−
(1)
u<v
∈
V
