Automatic layout of UML class diagrams [Elektronische Ressource] : a topology-shape-metrics approach / vorgelegt von Markus Eiglsperger

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2004
• Nombre de lectures: 66
• Langue: Deutsch
• Poids de l'ouvrage: 3 Mo

Extrait

Automatic Layout of
UML Class Diagrams:
A Topology-Shape-Metrics Approach
Dissertation
der Fakultat fur Informations- und¨ ¨
Kognitionswissenschaften
der Eberhard-Karls-Universitat Tubingen¨ ¨
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Inform. Markus Eiglsperger
aus Wangen am Bodensee
Tubingen¨
2003Tag der mundlichen Qualifikation: 26. November 2003¨
Dekan: Prof. Dr. Martin Hautzinger
1. Gutachter: Prof. Dr. Michael Kaufmann
2.hter: Prof. Dr. Wolfgang Kuc¨ hlin
3. Gutachter: Prof. Dr. Ulrik BrandesZusammenfassung der Arbeit
In dieser Arbeit werden Verfahren zum automatischen und interaktiven Er-
stellen hochqualitativer Zeichnungen von UML Klassendiagrammen vorge-
stellt. Da Klassendiagramme auf Graphen zuruckgefuhrt werden konnen,¨ ¨ ¨
verwenden wir dazu Methoden und Techniken aus dem Bereich des Gra-
phenzeichnens, und konzentrieren uns in dieser Arbeit insbesondere auf das
Topology-Shape-Metrics“ Paradigma zum Zeichnen von Graphen.
”
Klassendiagramme sind ein weitverbreitetes Hilfsmittel in der Modellie-
rung und Analyse von objekt-orientierten Softwaresystemen. Ursprun¨ glich
in den sechziger Jahren entwickelt, erlebten objekt-orientierte Techniken in
den neunziger Jahren eine Renaissance und sind heutzutage aus der moder-
nen Softwareentwicklung nicht mehr wegzudenken. Zur Beschreibung von
objekt-orientierten Softwaresystemen hat sich die Unified Modeling Lan-
guage (UML), welche eine Vereinheitlichung verschiedener Modellierungs-
sprachen darstellt, als lingua franca durchgesetzt. Die UML definert ein se-
mantischesModelleinesobjekt-orientiertenSoftwaresystemsundeineReihe
von Diagrammarten, welche Teile eines semantischen Modells visualisieren.
Klassendiagramme sind dabei die mit Abstand am meisten verwendete Dia-
grammartundbeschreibendiestatischenBeziehungenvonKlassenundOb-
jektenindemSoftwaresystem.ManunterscheidetdabeizwischendreiArten
von Beziehungen: Abhangigkeiten, Assoziationen und Vererbungen.¨
ImklassischenAnwendungsfallwerdenKlassendiagrammeinteraktivvon
einemBenutzermitHilfeeinesWerkzeugserstellt,wobeidieAnordnungder
einzelnen Bestandteile des Diagramms vom Benutzer vorgegeben wird. Es
gibt allerdings auch Anwendungsf¨alle, in denen zwar der Inhalt des Dia-
grams bekannt ist, aber nicht die Anordnung der einzelnen Elemente. Dies
ist der Fall wenn ein Diagramm nicht von einem Benutzer erstellt wurde,
sondernauseineranderenQuellestammt.Moglic¨ heQuellensindProgramme
zur automatischen Dokumentation oder Analyse-Werkzeuge zum Reverse-
Engineering. Will ein menschlicher Benutzer aus diesen Diagrammen Er-
kenntnisse ziehen, ist es in diesen Fallen notwendig, eine ubersichtliche An-¨ ¨
ordnung der Diagrammelemente zu bestimmen.
Um eine solche ub¨ ersichliche Anordnung zu berechnen, entwickeln wir
neue Verfahren, die auf dem Topology-Shape-Metrics“ Paradigma zum
”
Zeichnen von Graphen basieren. Bisher werden fur¨ praktische Anwendun-iv
gen des Graphenzeichnens hauptsachlich zwei andere Ansatze verwendet:¨ ¨
der kraft¨ e-basierte Ansatz fur¨ ungerichtete Graphen und der hierarchische
AnsatzfurgerichteteGraphen.BeidelassensichindenGrundvariantenrela-¨
tiv einfach implementieren und sind sehr robust in Bezug auf Eingabedaten
und Erweiterungen. Da die Vererbungsbeziehung eine gerichtete Substruk-
tur in Klassendiagrammen bildet, basieren die meisten existierenden Ver-
fahren zum automatischen Zeichnen von Klassendiagrammen sowohl in der
wissenschaftlichen Literatur wie auch in der Implementierung von Software-
Werkzeugen auf dem hierarchischen Ansatz.
Im Gegensatz dazu steht das Topology-Shape-Metrics Paradigma im
Schatten dieser beiden dominierenden Ansatze¨ . Es erfreut sich zwar in der
Forschung großer Beliebtheit, konnte sich in praktischen Anwendungen aber
bis jetzt noch nicht durchsetzen. Die Algorithmen, die auf diesem Paradig-
ma basieren, gelten weder als leicht zu implementieren, noch als ausgespro-
chen robust oder erweiterungsfahi¨ g. Um diese Behauptungen zu widerlegen,
wollen wir anhand einer Beispielanwendung zeigen, dass auch der Topology-
Shape-MetricsAnsatzfurpraktischeProblemeeinsetzbarist.Wirhabenda-¨
zu das automatische Zeichnen von Klassendiagrammen ausgewahl¨ t, da trotz
der großen praktische Bedeutung des Problems die meisten verfugbaren Im-¨
plementierungen fur¨ automatisches Zeichnen von Klassendiagrammen nur
sehr schlechte Ergebnisse liefern. Am Beispiel dieser Anwendung entwickeln
wir den Topology-Shape-Metrics Ansatz zu einem praktisch nutzbaren Ver-
fahren weiter, welches, wie unsere Experimente zeigen, fur diese Anwen-¨
dung den bisherigen Verfahren weit ub¨ erlegen ist. Die Erweiterungen des
Verfahrens sind dabei so allgemein gehalten, dass sie auch fur andere An-¨
wendungsgebiete relevant sind und somit die Anwendbarkeit des Topology-
Shape-Metrics Ansatzes stark erweitern.
Die Komplexitat des automatischen Zeichnens von Klassendiagrammen¨
wird maßgebend von den Konventionen bestimmt, die fur¨ ihre Darstellung
existieren und die zu berucksichtigen sind, damit ein durchschnittlicher Be-¨
nutzer eine Zeichnung als ub¨ ersichtlich erachtet. Die Vererbungsbeziehung
nimmt aufgrund ihrer strukturbildenden Eigenschaft eine Sonderstellung in
Klassendiagrammen ein. Um die von der Vererbungsbeziehung definierte
Hierarchie zu verdeutlichen, sollen alle Kurven, die diese Beziehungen re-
pr¨asentieren, monoton in eine Richtung gezeichnet werden, normalerweise
im Diagramm von unten nach oben zeigend. Zusatzlich werden oft mehrere¨
¨Kurven an einem Punkt zu einer Kurve zusammengefasst um die Ubersicht-
lichkeitimDiagrammzuerhohen.¨ DieseNotationistauchunterdemNamen
Hyperkanten-Notation“ bekannt. Weiterhin ist es ublich, Beziehungen als¨
”
orthogonale Kurven darzustellen, d.h. als Linienzug, der alternierend aus
horizontalen und vertikalen Segmenten besteht.
¨In Kapitel 2 werden diese Konventionen sowie weitere Asthetikkriterien,
welche die Lesbarkeit eines Diagramms beeinflussen, diskutiert. Dies ermog-¨
lichtesuns,dasProblemdesautomatischenZeichnensvonUMLKlassendia-v
grammenzuformalisierenundaufeinemathematischeGrundlagezustellen.
EswerdendieexistierendenVerfahrenfur¨ diesesProblembeleuchtetundih-
re Starken und Schwachen analysiert. Aufbauend auf diese Analyse werden¨ ¨
die Grundzuge¨ eines neuen Verfahrens fur¨ das automatische Zeichnen von
Klassendiagrammen vorgestellt. Das Verfahren basiert auf dem Topology-
Shape-Metrics Paradigma und besteht aus den drei Phasen Planarisierung,
Orthogonalisierung und Kompaktierung. Die oben beschriebenen speziellen
Anforderungen von Klassendiagrammen haben die Entwicklung neuartiger
Algorithmen fur¨ alle drei Phasen notwendig gemacht, welche in den darauf-
folgenden Kapiteln behandelt werden.
Kapitel 3 beschreibt die Planarisierungsphase des Zeichnenalgorithmus.
In der Planarisierungsphase wird fur einen gegebenen Graphen eine planare¨
Einbettung berechnet. Um Kantenrichtungen behandeln zu k¨onnen, wurden
die Konzepte Planaritat und Aufwartsplanaritat zu dem neuen Konzept der¨ ¨ ¨
gemischten Aufw¨artsplanarit¨at erweitert und ein neuer Planarisierungsalgo-
rithmus entworfen.
In Kapitel 4 werden neue Orthogonalisierungsalgorithmen vorgestellt.
Diese Algorithmen sind Erweiterungen des bekannten Kandinsky Algorith-
mus. Zuerst stellen wir eine Variante des Kandinsky Algorithmus vor, wel-
che bestimmte Nebenbedingungen fur¨ Knicke und Winkel behandeln kann.
Die speziellen Anforderungen von Klassendiagrammen, insbesondere das
Richtungskriterium und die korrekte Behandlung von Hyperkanten, konn¨ en
mitHilfedieserNebenbedingungenformuliertwerden,wasunszueinemOr-
thogonalisierungsalgorithmus fur¨ Klassendiagramme fuh¨ rt. Zus¨atzlich ana-
lysieren wir die Komplexitat verschiedener Knickminimierungsprobleme im¨
Kandinsky-Modell und pr¨asentieren neue heuristische Verfahren fur¨ diese
Probleme.
InKapitel5stellenwireinenneuenKompaktierungsalgorithmusvor,der
inderLageist,festeKnotengr¨oßenzurespektieren.Diesisteinedergrundle-
genden Anforderungen fur das automatische Zeichnen von Klassendiagram-¨
men.DerAlgorithmushatlineareLaufzeit,waseinedrastischeVerbesserung
gegenuber existierenden Algorithmen fur dieses Problem bedeutet.¨ ¨
Der in den bisherigen Kapiteln vorgestellte Algorithmus errechnet eine
Zeichnung vollautomatisch, ohne Interaktion mit dem Benutzer. In Kapi-
tel 6 wird ein Algorithmus vorgestellt, welcher interaktiv mit dem Benutzer
eine Zeichnung erstellt. Der Algorithmus kann sowohl neue Elemente in ein
Diagramm integrieren, ohne es allzu stark zu ver¨andern, als auch auf Be-
nutzerwun¨ sche reagieren.
In Kapitel 7 wird die Implementierung der vorgestellten Algorithmen
besprochen und ihre experimentelle Evaluierung vorgenommen. Wir ver-
gleichen hierzu die Implementierung unseres Algorithmus mit SugiBib, der
Implementierung eines Algorithmus zum automatischen Zeichnen von Klas-
sendiagrammen, welche dem hierarchischen Paradigma folgt.