Information Technology Reference
In-Depth Information
where
b
(
u,v
) is the Euclidean distance between the boundaries of nodes
u
and
v
along the straight line connecting their centres,
p
uv
the number of edges on the
shortest path between nodes
u
and
v
,
an ideal edge length,
w
uv
=(
p
uv
)
−
2
,
and (
z
)
+
=max(
z,
0).
Ideal Edge Lengths.
Instead of using a single ideal edge length
as in (1),
which can result in cluttered areas where multiple nodes are highly connected,
we may assign custom edge lengths
uv
, choosing larger values to separate such
nodes. In Fig. 3 the ideal edge lengths of the two outgoing edges of the
Front-
DropQueue
actor are chosen slightly larger than for the two other edges.
The length of the edge (
ˀ
(
p
)
,ʴ
(
p
)) connecting a port dummy to its parent
node is set to the exact distance from the node's center to the port's center.
Emphasizing Flow.
A common requirement for data flow diagrams is that
the majority of edges point in the same direction (here left-to-right). For this we
introduce separation (
flow
) constraints for edges (
u
,
v
)oftheform
x
u
+
g
x
v
,
where
g>
0 is a pre-defined spacing value, ensuring that
u
is placed left of
v
.
Special care has to be taken for cycles, as they would introduce contradicting
constraints. We experimented with different strategies to handle this. 1) We
introduced the constraints even though they were contradicting (and let the
solver choose which one(s) to reject); 2) We did not generate
any
flow constraints
for edges that are part of a strongly connected component; 3) We employed a
greedy heuristic by Eades et al. [8] (known from the layer-based approach) to
find the minimal feedback arc set, and withheld flow constraints for the edges in
this set. Our experiments showed that the third strategy yields the best results.
≤
Execution.
We perform three consecutive layout runs, iteratively adding con-
straints: 1) Only port constraints are applied, allowing the graph to untangle and
expose symmetry; 2) Flow constraints are added, but overlaps are still allowed
so that nodes can float past each other, swapping positions where necessary; 3)
Non-overlap constraints are applied to separate all nodes as desired.
2.2 Grid-Like Node Alignment
While yielding a good distribution of nodes overall, stress-minimization tends to
produce an organic layout with paths splayed at all angles, which is inappropriate
for data flow diagrams. The layout needs to be
orthogonalized
, i. e., connected
nodes brought into alignment with one another so that where possible edges
form straight horizontal lines, visually emphasizing horizontal flow.
For this purpose we apply the Adaptive Constrained Alignment (ACA) algo-
rithm [10]. Since it respects existing flow constraints, it only attempts to align
edges horizontally. However, our replacement of the given graph
G
by the auxil-
iary graph
G
with port nodes tends to subvert the original intentions of ACA,
so it requires some adaptation. Whereas the original ACA algorithm expected at
