Automatic layout of UML class diagrams : a topology-shape-metrics approach

Abstract

Class diagrams are among the most popular tools for the analysis and the modeling of object-oriented software systems. They are ubiquotous in today's software development processes. The Unified Modeling Language (UML), which replaced earlier modeling languages, is the established standard notation for class diagrams. A class diagram describes the static relationships between classes and objects in a software system. There are three different relationships between classes in object-oriented systems: dependencies, associations and generalizations. The graphical representation of each of them follows its own conventions. Particularly generalizations play a special role and are represented generally as upward pointing polyline curves.

In some scenarios the contents of a class diagram is known, but not its graphical representation, especially not the placement of the elements in the diagram. This is the case when the diagram hasn't been created interactively but comes from another source. Possible sources are applications for the automatic documentation of software or reverse-engineering tools. If a human beholder wants to gain insight from such a diagram, it has to be drawn in a readable fashion.

In this work we will present new algorithms for the automatic and interactive layout of class diagrams. Since class diagrams can be modeled by graphs, we will use methods and techniques from the field of graph drawing. Especially we will use a technique known as the "topology-shape-metrics" approach.

For this purpose we enhance the topology-shape-metrics approach to a practical tool which can consider the conventions for drawing class diagrams and extend all three phases of it. For each phase we present new algorithms along with an analysis of their performance. We show in an experimental evaluation, that the new algorithms outperform significantly previous approaches for the automatic layout of class diagrams. All extensions to the topology-shape-metrics approach are of a very general nature and apply also to other application domains than class diagrams. With these new algorithms we extend the number of application domains of the topology-shape-metrics approach dramatically.

Klassendiagramme sind ein weitverbreitetes Hilfsmittel in der Modellierung und Analyse von objekt-orientierten Softwaresystemen und sind heutzutage aus der modernen Softwareentwicklung nicht mehr wegzudenken. Dabei hat sich die Unified Modeling Language (UML), welche eine Vereinheitlichung verschiedener Modellierungssprachen darstellt, als gängige Notation durchgesetzt. Ein Klassendiagramm beschreibt die statischen Beziehungen von Klassen und Objekten in einem Softwaresystem. Man unterscheidet dabei zwischen drei Arten von Beziehungen (Abhängigkeiten, Assoziationen und Vererbungen), für welche jeweils unterschiedliche Konventionen in der Darstellung gelten. Insbesondere die Vererbungsrelation spielt eine gesonderte Rolle und wird üblicherweise als aufwärtsgerichteter Polygonzug realisiert. In manchen Anwendungsfällen ist zwar der Inhalt des Diagramms bekannt, aber nicht die Anordnung der einzelnen Elemente. Dies ist der Fall, wenn ein Diagramm nicht von einem Benutzer erstellt wurde, sondern aus einer anderen Quelle stammt. Mögliche Quellen sind Programme zur automatischen Dokumentation oder Analyse-Werkzeuge zum Reverse-Engineering. Will ein menschlicher Benutzer aus diesen Diagrammen Erkenntnisse ziehen, ist es in diesen Fällen notwendig, eine übersichtliche Zeichnung der Diagrammelemente zu bestimmen.

In dieser Arbeit werden Verfahren zum automatischen und interaktiven Erstellen hochqualitativer Zeichnungen von UML-Klassendiagrammen vorgestellt. Da Klassendiagramme auf Graphen zurückgeführt werden können, verwenden wir dazu Methoden und Techniken aus dem Bereich des Graphenzeichnens und konzentrieren uns in dieser Arbeit insbesondere auf das "Topology-Shape-Metrics"-Paradigma zum Zeichnen von Graphen.

Dazu entwickeln wir den "Topology-Shape-Metrics"-Ansatz zu einem praktisch nutzbaren Verfahren weiter, welches die speziellen Konventionen und Anforderungen von UML-Klassendiagrammen berücksichtigt. Dazu werden neue Ansätze und Algorithmen für alle drei Phasen des "Topology-Shape-Metrics"-Ansatzes vorgestellt und analysiert. Wie unsere Experimente zeigen, sind diese neuen Verfahren den bisherigen Verfahren für diese Anwendung weit überlegen. Die Erweiterungen des Verfahrens sind dabei so allgemein gehalten, dass sie auch für andere Anwendungsgebiete relevant sind und somit die Anwendbarkeit des "Topology-Shape-Metrics"-Ansatzes stark erweitern.