A topology-shape-metrics approach for the automatic layout of UML class diagrams

ABSTRACT

Class diagrams are among the most popular visualizations for object oriented software systems and have a broad range of applications. In many settings it is desirable that the placement of the diagram elements is determined automatically, especially when the diagrams are generated automatically which is usually the case in reverse engineering. For this reason the automatic layout of class diagram gained importance in the last years. Current approaches for the automatic layout of class diagrams are based on the hierarchic graph drawing paradigm. These algorithms produce good results for class diagrams with large and deep structural information, i.e., diagrams with a large and deep inheritance hierarchy. However, they do not perform satisfactorily in absence of this information. We propose in this work a new algorithm for automatic layout of class diagram which is based on the topology-shape-metrics approach. The algorithm is an adaption of sophisticated graph drawing algorithms which have proven their effectiveness in many applications. The algorithm works as well for class diagrams with rich structural information as for class diagrams with few or no structural information. It improves therefore the existing algorithms significantly. An implementation of the algorithm is used in the reverse engineering tool JarInspector.

REFERENCES

• 1: Giuseppe Di Battista , Walter Didimo , Maurizio Patrignani , Maurizio Pizzonia, Orthogonal and Quasi-upward Drawings with Vertices of Prescribed Size, Proceedings of the 7th International Symposium on Graph Drawing, p.297-310, September 01, 1999
• 2: Giuseppe Di Battista , Walter Didimo , A. Marcandalli, Planarization of Clustered Graphs, Revised Papers from the 9th International Symposium on Graph Drawing, p.60-74, September 23-26, 2001
• 3: Paola Bertolazzi , Giuseppe Di Battista , Walter Didimo, Computing Orthogonal Drawings with the Minimum Number of Bends, IEEE Transactions on Computers, v.49 n.8, p.826-840, August 2000 [doi>10.1109/12.868028 ]
• 4: BERTOLAZZI, P., BATTISTA, G. D., AND DIDIMO, W. 2002. Quasi-upward planarity. Algorithmica 32, 3, 474--506.
• 5: Carla Binucci , Walter Didimo , Giuseppe Liotta , Maddalena Nonato, Labeling Heuristics for Orthogonal Drawings, Revised Papers from the 9th International Symposium on Graph Drawing, p.139-153, September 23-26, 2001
• 6: Carla Binucci , Walter Didimo , Giuseppe Liotta , Maddalena Nonato, Computing Labeled Orthogonal Drawings, Revised Papers from the 10th International Symposium on Graph Drawing, p.66-73, August 26-28, 2002
• 7: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 8: BOOCH, G. 1994. Object Oriented Design and Analysis. Addison-Wesley.
• 9: Ulrik Brandes , Markus Eiglsperger , Michael Kaufmann , Dorothea Wagner, Sketch-Driven Orthogonal Graph Drawing, Revised Papers from the 10th International Symposium on Graph Drawing, p.1-11, August 26-28, 2002
• 10: S. R. Chidamber , C. F. Kemerer, A Metrics Suite for Object Oriented Design, IEEE Transactions on Software Engineering, v.20 n.6, p.476-493, June 1994 [doi>10.1109/32.295895 ]
• 11: COFFMAN, E. G., AND GRAHAM, R. L. 1972. Optimal scheduling for two processor systems. Acta Informatica 1, 200--213.
• 12: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 13: EICHELBERGER, H. 2000. Automatisches Zeichnen von UML Klassendiagrammen mit dem Sugiyama-Algorithmus in Tagungsband des GI-Workshops Softwarevisualisierung 2000. Tech. Rep. A/01/2000, Universität des Saarlandes.
• 14: Holger Eichelberger, Aesthetics of Class Diagrams, Proceedings of the 1st International Workshop on Visualizing Software for Understanding and Analysis, p.23, June 26-26, 2002
• 15: Markus Eiglsperger , Michael Kaufmann, An Approach for Mixed Upward Planarization, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.352-364, August 08-10, 2001
• 16: Markus Eiglsperger , Michael Kaufmann, Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size, Revised Papers from the 9th International Symposium on Graph Drawing, p.124-138, September 23-26, 2001
• 17: EIGLSPERGER, M., AND KAUFMANN, M. 2002. An approach for mixed upward planarization. Journal of Graph Algorithms and Applications. submitted.
• 18: Markus Eiglsperger , Ulrich Fößmeier , Michael Kaufmann, Orthogonal graph drawing with constraints, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.3-11, January 09-11, 2000, San Francisco, California, United States
• 19: Qing-Wen Feng , Robert F. Cohen , Peter Eades, Planarity for Clustered Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.213-226, September 25-27, 1995
• 20: Ulrich Fößmeier , Michael Kaufmann, Drawing High Degree Graphs with Low Bend Numbers, Proceedings of the Symposium on Graph Drawing, p.254-266, September 20-22, 1995
• 21: Karlis Freivalds , Ugur Dogrusöz , Paulis Kikusts, Disconnected Graph Layout and the Polyomino Packing Approach, Revised Papers from the 9th International Symposium on Graph Drawing, p.378-391, September 23-26, 2001
• 22: GAMMA, E., HELM, R., JOHNSON, R., AND VLISSIDES, J. 1995. Design Patterns. Addison-Wesley.
• 23: GUTWENGER, C., JÜNGER, M., KLEIN, K., KUPKE, J., LEIPERT, S., AND MUTZEL, P. 2002. Caesar automatic layout of uml class diagrams. In Proceedings of the 9th International Symposium on Graph Drawing (GD'2001), Springer, vol. 2265 of LNCS.
• 24: Gunnar W. Klau , Petra Mutzel, Combining Graph Labeling and Compaction, Proceedings of the 7th International Symposium on Graph Drawing, p.27-37, September 01, 1999
• 25: Gunnar W. Klau , Karsten Klein , Petra Mutzel, An Experimental Comparison of Orthogonal Compaction Algorithms (Extended Abstract), Proceedings of the 8th International Symposium on Graph Drawing, p.37-51, September 20-23, 2000
• 26: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 27: LÜTKE-HÜTTEMANN, D. 1999. Knickminimales Zeichnen 4-planarer Clustergraphen. Master's thesis, Universität des Saarlands.
• 28: OMG, 2001. Unified Modeling Language v1.4. http://www.omg.org/technology/documents/formal/uml.htm.
• 29: H. C. Purchase , R. F. Cohen , M. I. James, An experimental study of the basis for graph drawing algorithms, Journal of Experimental Algorithmics (JEA), 2, p.4-es, 1997 [doi>10.1145/264216.264222]
• 30: Helen C. Purchase , Jo-Anne Allder , David A. Carrington, User Preference of Graph Layout Aesthetics: A UML Study, Proceedings of the 8th International Symposium on Graph Drawing, p.5-18, September 20-23, 2000
• 31: Helen C. Purchase , Matthew McGill , Linda Colpoys , David Carrington, Graph drawing aesthetics and the comprehension of UML class diagrams: an empirical study, Proceedings of the 2001 Asia-Pacific symposium on Information visualisation, p.129-137, December 01, 2001, Sydney, Australia
• 32: Helen C. Purchase, Which Aesthetic has the Greatest Effect on Human Understanding?, Proceedings of the 5th International Symposium on Graph Drawing, p.248-261, September 18-20, 1997
• 33: Jochen Seemann, Extending the Sugiyama Algorithm for Drawing UML Class Diagrams: Towards Automatic Layout of Object-Oriented Software Diagrams, Proceedings of the 5th International Symposium on Graph Drawing, p.415-424, September 18-20, 1997
• 34: SUGIYAMA, K., TAGAWA, S., AND TODA, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11, 2 (February), 109--125.
• 35: Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
• 36: Frank Wagner , Alexander Wolff, A Combinatorial Framework for Map Labeling, Proceedings of the 6th International Symposium on Graph Drawing, p.316-331, August 01, 1998
• 37: WIESE, R., EIGLSPERGER, M., AND KAUFMANN, M. 2001. y les: Visualization and automatic layout of graphs. In Proceedings of the 9th International Symposium on Graph Drawing (GD'01), Springer, LNCS, 453--454.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Keywords:
UML Diagrams, graph drawing