5 Application and Performance Evaluation
5.2 Performance Evaluations
( b )
Figure 5.3 Representations of trees
We present in the following some examples of cubes. The layouts of these cubes are generated by the two-dimensional version of DPSMA and appear to be three-dimensional when laid out. In Figure 5.4, (a) represents one cube and (b) represents twin-cubes.
( b ) ( a )
Figure 5.4 Cube and twin-cubes are laid out by the two-dimensional version of DPSMA
We made some experiments to evaluate the performance of DPSMA.
Because the improvements of the algorithm focus on its speed and stability (the problem of vibration phenomenon), these experiments are designed to evaluate the DPSMA in two respects:
1) Evaluate the speed of algorithms;
2) Determine whether or not vibrations phenomena appear.
For the first evaluation object, we use 5 undirected graphs with different complexity to compare the speed of layout between DPSMA and SMA.
Considering the property of automatic graph layout, the comparisons include the comparison of speed in real running time and the comparison of number of layout iterations.
We made the same initialization settings for DPSMA and SMA to make the experiments. The force thresholds are defined as stop conditions of automatic layout. We defined a constant as the force threshold for a given graph in the initialization stage. When the biggest resultant forces among all nodes in the graph become smaller than the predefined force threshold, it means that the layout has reached its stable state and the computation should be stopped. This is the stop condition of the layout for a given graph.
In experiments, the force thresholds are set to 0.01(Newton), 0.05,0.1 and 0.5 respectively to evaluate the performance of DPSMA under different force threshold conditions. The parameters K and are set to be the same with the initialization parameters C and in the SMA respectively. Table 5.1 shows the basic data of 5 graphs in experiments.
s Kr
s Cr
Graph 1 2 3 4 5
Nodes 3 8 27 64 125 Edges 3 12 54 142 294
Table 5.1 Graph data
At first, we compare the number of iterations. In the same environment, we obtained the following results in Table 5.2.
No. of graphForce threshold 0.5 0.1 0.05 0.01
SMA 41 45 47 52
1 DPSMA 29 34 36 41
DPSMA/ SMA 70.7% 75.6% 76.6% 78.8%
SMA 45 64 72 93
2 DPSMA 34 51 53 74
DPSMA/ SMA 75.6% 79.7% 73.6% 79.6%
SMA 127 176 199 261
3 DPSMA 89 149 169 222
DPSMA/ SMA 70.1% 84.7% 84.9% 85.1%
SMA 247 336 384 507
4 DPSMA 176 264 311 386
DPSMA/ SMA 71.3% 78.6% 81.0% 76.1%
SMA 278 479 575 801
5 DPSMA 193 367 432 637
DPSMA/ SMA 69.4% 76.6% 75.1% 79.5%
Table 5.2 Comparison of number of iterations
Figure 5.5 shows the comparison of number of iterations in the case of 4 different force thresholds as stop conditions. The x-axis is the number of graph and the y-axis is number of the iterations.
0 50 100 150 200 250 300 350 400 450 500 Iterations
times
1 2 3 4 5
( force threshold =0.1)
SMA DPSMA
0 50 100 150 200 250 300 Iterations
times
1 2 3 4 5
( force threshold =0.5)
SMA DPSMA
0 100 200 300 400 500 600 700 800 900 Iterations
times
1 2 3 4 5
( force threshold =0.01)
SMA DPSMA
0 100 200 300 400 500 600 Iterations
times
1 2 3 4 5 ( force threshold =0.05)
SMA DPSMA
Figure 5.5 Comparison of number of iterations
We observe from Figure 5.5 that the number of iterations of automatic layout for a given graph by DPSMA is smaller than that obtained by SMA.
The results also show that the DPSMA is more effective than SMA when the graph is complex, with many nodes and edges.
We also compare the real running time between DPSMA and SMA. In this experiment, the same 5 graphs are used to compare the performance.
Because there are many factors that influence the real running time, such as the algorithm itself, optimizations of algorithm, real environment and others, we make the same experiments many times and use the average values as results.
Table 5.3 shows the results of experiments in the case of the 5 given graphs used previously.
No. of graphForce threshold 0.5 0.1 0.05 0.01
SMA
118 125 141 1381 DPSMA
74 84 125 127DPSMA/SMA 62.7% 67.2% 88.7% 92.0%
SMA
132 177 229 3352 DPSMA
117 167 206 302DPSMA/SMA 88.6% 94.4% 90.0% 90.1%
SMA
179 216 267 3673 DPSMA
157 189 234 313DPSMA/SMA 87.7% 87.5% 87.6% 85.3%
SMA
3178 4407 4889 61394 DPSMA
2834 3910 4319 5401DPSMA/SMA 89.2% 88.7% 88.3% 88.0%
SMA
38412 61340 71049 963245 DPSMA
30132 43987 52987 71980DPSMA/SMA 78.4% 71.7% 74.6% 74.7%
Table 5.3 Comparison of real running time (Unit: milliseconds.)
Figure 5.6 shows the comparisons of real running time in the case of different force thresholds as stop conditions for graph 4 and graph 5.
0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 millisecs.
0.5 0.1 0.05 0.01 Graph 5 125nodes,294 edages
SMA DPSMA
0 1000 2000 3000 4000 5000 6000 7000 millisecs.
0.5 0.1 0.05 0.01 Graph 4 64 nodes,142 edages
SMA DPSMA
Figure 5.6 Comparison of real running time
From the comparison of speed in real running time, the DPSMA proves to be better than SMA. Because in DPSMA the computations of dynamic parameter and all-pairs of shortest path occupy real running time in every step of layout, the results are not so effective as in the comparison of number of iterations. The results also show that the DPSMA is more effective in the case of complex graphs.
These two groups of experiments show that the DPSMA is more effective than SMA with respect to both real running time and number of iterations.
We also made some experiments to evaluate the stability of DPSMA. No vibration phenomena are found in the experiments, and this shows that DPSMA is stable. When using the same data, in some cases the vibration phenomena are found in the process of layout in the case of SMA. This shows that SMA is not stable enough.
As for automatic layout for undirected graph, many experiments show that DPSMA is faster and more stable than SMA. For different types of undirected graphs, the efficiency of DPSMA is different. The efficiency in case of complex graphs is higher than that for simple graphs; the efficiency of low-precision graphs is higher than that of high-precision graphs.
Chapter 6
Conclusions
An improved spring model, the Dynamic Parameter Spring Model, which is applied in automatic graph layout for general undirected graphs has been proposed, and its corresponding algorithm, the Dynamic Parameter Spring Modeling Algorithm, has been implemented. The new improved model is based on the well-known Spring Model as the representation of force-directed approach to automatic graph layout. In the original Spring Model while trying to speed up the layout, the vibration phenomenon may appear and this can lead to an unstable algorithm.
Our model solves the existing problem in the original Spring Model and speeds up the process of automatic graph layout while avoiding the appearance of vibration phenomenon.
Using the new improved algorithm, a quick and stable automatic graph layout is provided and the user can understand the information in the given graph easily and intuitively. Our approach can also be used in various applications of information visualization.
Acknowledgements
I wish to have this opportunity to express my heartfelt thanks and profound gratitude to my supervisor Dr. Jiro Tanaka, Professor, University of Tsukuba, for his invaluable guidance, advice, supervision and constant encouragement during the course of the present study. It would not have been possible to complete the study without his generous training.
I am highly obliged to Dr. Buntarou Shizuki; Dr. Motoki Miura of Tsukuba University for their guidance and great deal of helpful advice for my research work.
I thank Mr. Tohru Ogawa; Mr. Kazuhisa Iizuka for their constructive and valuable advices and comments for my research work and all other members of VS group, Mr. Hideto Yamada; Mr. Okamura Toshiyuki; Mr.
Masakazu Kanda for useful discussions for my research work.
I am grateful to all the reviewers who critically read my thesis and their comments improved the quality of this work.
Special thanks to Ms. Simona Mirela Vasilache; Mr. Iftikhar Azim Niaz;
Ms. XiaoPing Ying, Mr. Hiroya Itoga and all other members of IPLAB, University of Tsukuba, for useful discussions, constructive criticism and timely help.
I wish to express my thanks to all my friends in China and Japan for their encouragement and helps.
Bibliography
[1] N. Quinn and M. Breur. A Force Directed Component Placement Procedure for Printed Circuit Boards. IEEE Transactions of Circuits and Systems, 26(6): 377-388, 1979.
[2] P. Eades. A Heuristic for Graph Drawing. Congressus Numerantium 42, 149-160, 1984.
[3] T. Fruchterman and E. Reingold. Graph Drawing by Force-Directed Placement.
Software – Practice and Experience 21, 1129-1164, 1991.
[4] T. Kamada. Visualizing Abstract Objects and Relations, World Scientific, 1989.
[5] T. Kamada and S. Kawai. An Algorithm for Drawing General Undirected Graph.
Information Processing letters, 31(1): 7-15, 1989.
[6] K. Sugiyama and K. Misue. Graph Drawing by Magnetic-Spring Model, Res.
Rep. ISIS-RR-94-14E, Inst. Social Information Science, Fujitsu Labs Ltd., 1994.
[7] T. Miyashita and J. Tanaka. Integrating Three-dimensional Spring Model and Augmented Directed Manipulation technique. Transactions of IPSJ, 42(3): 565-576, 2001(in Japanese).
[8] C. Ware, G. Frank, M. Parkhi, T. Dudley. Layout for Visualizing Large Software Structures in 3D. Proceedings of VISUAL’97, 215-223, 1997.
[9] X. Liu, B. Shizuki and J. Tanaka. Dynamic Parameter Spring Modeling Algorithm for Graph Drawing, Proceedings of the International Symposium on Future Software Technology (ISFST 2001), ZhengZhou, China, Nov. 5-8, 52-57, 2001.
[10] K. Sugiyama. Automatic graph drawing methods and their applications, The Society of Instrument and Control Engineers, 1993.
[11] C. Wetherell and A. Shannon. Tidy Drawing of Trees. IEEE Transaction on Software Engineering, SE-5(5): 514-520, 1979.
[12] E. Reingold and J. Tilford. Tidier Drawing of Trees, IEEE Transaction on Software Engineering, SE-7(2): 223-228, 1981.
[13] P. Eades, T.Lin, and X. Lin. Two Tree Drawing Conventions, International Journal of Computational Geometry and Applications, 3(2): 133-153, 1993.
[14] A. Lempel, S. Even and I. Cederbaum. An Algorithm for Planarity Testing of Graphs, Theory of Graphs: Internae Symposium, Rome, 215-232, 1967.
[15] G.D. Battista and R. Tamassia. Algorithms for Plane Representations of Acyclic Digraphs, Theoretical Computer Science, 61: 175-198, 1988.
[16] K.Sugiyama, S.Tagawa and M. Toda. Method for Visual Understanding of
Hierarchical System Structures, IEEE Trans. Syst. Man Cybern, 11(2): 109-125, 1981.
[17] K.Sugiyama. A Cognitive Approach for Graph Drawing. Cyberrerics and
Systems, 18(6): 447-488, 1987.
[18] A. Frick, A. Ludwig and H. Mehldau. A Fast Adaptive Layout Algorithm for Undirected Graphs. Proceedings of the Symposium on Graph Drawing GD’95, Springer-Verlag, 389-403, 1994.
[19] J. Nagumo and J. Tanaka. Introducing Fisheye-view into Graph Drawing
Algorithm, Transactions of IEICE, 82-D-II(6): 1042-1048, 1999 (in Japanese).
[20] G.D. Battista, P. Eades, R. Tamassia and I.G. Tollis. Graph Drawing Algorithm for the Visualization of Graphs. Prentice-Hall, Inc,1999.
[21] T.H. Corman., C.E. Leiserson. and R.L. Rivest, Introduction to Algorithm, MIT Press, 558-562, 1990.
[22] J. Tanaka. PP: Visual Programming System for Parallel Logic Programming Language GHC, Parallel and Distributed Computing and Network’97, 188-193, 1997.
[23] P.T. Cox, F.R. Glies and T. Pietrzykowski. Prograph: A Step towards Liberating Programming form Textual Conditioning, IEEE Workshop on Visual Language, Rome, 150-156, 1989.