Information Technology Reference
In-Depth Information
Tabl e 1.
Evaluations of 110 flat diagrams with 10-23 nodes (9-30 edges) and 10
compound diagrams with 12-38 nodes (12-52 edges). Figures for stress, average edge
length, variance in edge length, and area are given as the ratio of CoDaFlow divided by
KLay Layered. Values below 1 indicate a better performance of CoDaFlow. An average
value shows the general tendency while minimal and maximal values show the best and
worst performance.
Stress
EL Variance
EL Average
Area
Min Avg Max
Min Avg Max
Min Avg Max
Min Avg Max
Comp. 0.27
0.75
0.97
0.11
0.29
0.61
0.39
0.57
0.79
0.50
0.88
1.28
Flat
0.34
0.77
1.13
0.03
0.60
1.92
0.34
0.84
1.10
0.62
1.11
2.01
Tabl e 2.
Results for the metrics aspect ratio, crossings, and average bends per edge.
As opposed to Table 1, figures are absolute values.
Aspect Ratio
Crossings
Bends/Edge
Min Avg Max
Min Avg Max
Min Avg Max
1.27
1.83
2.51
0.00
3.40
10.0
0.92
1.25
1.56
Comp.
CoDaFlow
1.51
2.76
4.94
0.00
1.20
6.00
0.68
0.97
1.22
KLay
0.32
2.47
5.96
0.00
1.25
11.0
0.42
1.16
2.31
CoDaFlow
Flat
0.37
2.77
9.00
0.00
1.02
7.00
0.22
1.04
1.73
KLay
at all, thus the increased average. As can be seen in Fig. 1, the small number of
additional crossings are not ruinous to diagram readability, and they could be
easily avoided by introducing further constraints, as discussed in Sect. 5.
As seen in Fig. 6, the current CoDaFlow implementation performs signifi-
cantly slower than KLay Layered, but it still finishes in about half a second even
on a larger diagram of 60 nodes. There is room for speedups, for instance, by
avoiding re-initialization of internal data structures between pipeline stages. In
addition, we plan to improve the incrementality of constraint solving in the ACA
stage, as well as performing faster satisfiability checks wherever full projections
are not required.
Compared to KLay Layered our approach is both easier to understand and
implement, and more flexible in its application.
In addition to the five main phases of KLay Layered, about 10 to 20
interme-
diate processes
of low to medium complexity are used during each layout run.
Dependencies between these units have to be carefully managed and the phases
have to be executed in strict order, e.g., the edge routing phase requires all
previous phases.
CoDaFlow optimizes only one goal function and addresses the requirements
of data flow diagrams by successively adding constraints to the optimization
process. While we divide the algorithm into multiple stages, each stage merely
introduces the required constraints. CoDaFlow's stages can be used indepen-
dently of each other, e.g., to improve existing layouts. Also, users can fine-tune
generated drawings using interactive layout [6] methods.
