Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | anne-marie-lais |
View: | 103 times |
Download: | 0 times |
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 1 von 58
Seminar „Graphenlayoutalgorithmen“
Visualisierung von UML-Diagrammen
Christian M. [email protected]
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 2 von 58
„A New Approach for Visualizing UML Class Diagrams“
Einleitung
Vorstellung des GoVisual-AlgorithmusArtikel von Gutwenger, Jünger, Klein, Kupke, Leipert und Mutzel:
Visualisierung von UML-Diagrammen » Einleitung
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 3 von 58
EinleitungGrundlagenMotivationZieleGoVisual AlgorithmusZusammenfassungSoftware und Links
Visualisierung von UML-Diagrammen » Agenda
Agenda
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 4 von 58
EinleitungGrundlagenMotivationZieleGoVisual AlgorithmusZusammenfassungSoftware und Links
Visualisierung von UML-Diagrammen » Agenda
Agenda
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 5 von 58
Graph
Graph G = (V, E) mitV KnotenmengeE Kantenmenge
Visualisierung von UML-Diagrammen » Grundlagen » Graphen
gerichteter Graph ungerichteter Graph
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 6 von 58
Einbettung, Planarität
Einbettung: Darstellung eines Graphen in der Ebene
Knoten sind PunkteKanten sind Verbindungslinien
Planar: Der Graph kann ohne Kreuzungen in der Ebene eingebettet werden
Visualisierung von UML-Diagrammen » Grundlagen » Graphen
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 7 von 58
UML = Unified Modeling LanguageModellierungssprache für SoftwareStandardisiert von der OMG (Object Management Group)
Visualisierung von UML-Diagrammen » Grundlagen » UML
UML
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 8 von 58
Visualisierung von UML-Diagrammen » Grundlagen » UML
1991
1994
1995
1996
1997
2003
Booch: OOAD
Rumbaugh: OMT
Unified Method 0.8
Jacobsen: OOSE
Coad/Yourdan: OOA/OOD
Hewlett Packard
MicrosoftOracle
Unified Modeling Language 0.9
Unified Modeling Language 2.0
Unified Modeling Language 1.0 und 1.1(von der OMG zum Standard erklärt)
Entwicklung der UML
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 9 von 58
Abstrakter als ProgrammierspracheEinheitliche Beschreibungen im ProjektSprachenunabhängigVerschiedene Sichten: statisch, dynamischVerständigung zwischen Entwicklern, Architekten, Designer, Auftraggeber,…Dokumentation
Visualisierung von UML-Diagrammen » Grundlagen » UML
Warum UML?
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 10 von 58
Graphische Interpretation der Modelle:
Visualisierung von UML-Diagrammen » Grundlagen » UML
Use-Case-Diagramm Klassendiagramm Interaktionsdiagramm Zustandsdiagramm
Sequenzdiagramm DeploymentdiagrammKomponentendiagramm Timingdiagramm
Diagramme
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 11 von 58
Beliebtestes DiagrammStatische Struktur der SoftwareKlassenBeziehungen
Visualisierung von UML-Diagrammen » Grundlagen » UML
Klassendiagramm
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 12 von 58
DatentypAttribute und Methoden
Visualisierung von UML-Diagrammen » Grundlagen » UML
ClassName
– privateOperation()
# protectedOperation()
+ publicOperation()
– attribute1: Type
– attribute2: Type
Klassenname
Attribute
Methoden
Modifier
– private# protected+ public
Klassen
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 13 von 58
GeneralisierungAttribute und Methoden werden „geerbt“
Visualisierung von UML-Diagrammen » Grundlagen » UML
SuperClass
SubClass
Oberklasse
Subklasse,Kindklasse
Generalisierung,
Vererbung
Beziehungen (1)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 14 von 58
AssoziationBeziehung zwischen 2 oder mehr TypenNavigierbarkeit, Multiplizität
Einfache Assoziation:
Aggregation:
Komposition:
Visualisierung von UML-Diagrammen » Grundlagen » UML
Class1 Class2
Class1 Class2
Class1 Class3
Beziehungen (2)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 15 von 58
Klassendiagramm als Graph
Generalisierungen sind gerichtetAssoziationsrichtung für automatische Layoutalgorithmen unwichtigDaher: semi-gerichteter GraphG = (V, A, E) mit
V KlassenmengeA Gerichtete GeneralisierungskantenE Ungerichtete Assoziationskanten
Visualisierung von UML-Diagrammen » Grundlagen » UML
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 16 von 58
EinleitungGrundlagenMotivationZieleGoVisual AlgorithmusZusammenfassungSoftware und Links
Visualisierung von UML-Diagrammen » Agenda
Agenda
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 17 von 58
UML-Diagramme sind großLayout von Hand ist aufwändigAutomatisches Layout für MDA notwendigViele Tools für automatisches GraphenlayoutAnbindung an führende Case-Tools:
Rational RoseTogetherMicrosoft Visio
Visualisierung von UML-Diagrammen » Motivation
Motivation (1)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 18 von 58
Aber: Tools haben viele NachteileHierarchische Vererbungsstrukturen werden nicht behandeltÜbersicht ist oft unzureichendÄsthetische Mängel
Spezielle Algorithmen für UML-Diagramme sinnvoll
Visualisierung von UML-Diagrammen » Motivation
Motivation (2)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 19 von 58
Visualisierung von UML-Diagrammen » Probleme
Viele Kreuzungen
Unnötige Knicke
Nicht orthogonal
Einzelne Vererbungspfeile
Überlappung Assoziation-Klasse
Probleme (1)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 20 von 58
Visualisierung von UML-Diagrammen » Probleme
Richtung der Vererbungspfeile
Fehlende Hierarchie
Probleme (2)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 21 von 58
Visualisierung von UML-Diagrammen » Probleme
Verschachtelte Hierarchien
Probleme (3)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 22 von 58
Kriterien für ästhetische UML-Diagramme:Minimale KreuzungenMinimale KnickeEinheitliche Richtung in HierarchienKeine verschachtelten HierarchienBeziehungen je nach Semantik betrachtenOrthogonales LayoutKombinierte VererbungspfeileGut lesbare Kantenbeschriftungen
Visualisierung von UML-Diagrammen » Ziele
Ziele
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 23 von 58
Visualisierung von UML-Diagrammen » Ziele
Beispiel
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 24 von 58
EinleitungGrundlagenMotivationZieleGoVisual AlgorithmusZusammenfassungSoftware und Links
Visualisierung von UML-Diagrammen » Agenda
Agenda
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 25 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 26 von 58
Generalisierungen sollen verbunden werdenDadurch ergeben sich u.U. neue KreuzungenBleiben bei Planarisierung unerkannt
Visualisierung von UML-Diagrammen » Algorithmus » Vorberechnung
Vorberechnung (1)
v
w1 w2 w3
v
w1 w2 w3
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 27 von 58
Lösung: Zwischenknoten einfügen
Visualisierung von UML-Diagrammen » Algorithmus » Vorberechnung
Vorberechnung (2)
v
w1 w2 w3
v
w1 w2 w3
dv
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 28 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Vorberechnung
Vorberechnung (3)
v
w1 w2 w3
dv
O(|V|)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 29 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 30 von 58
Generalisierungen bilden Hierarchien
Zusammenhängende Subgraphen von (V, A)
Tiefensuche, O(|V|+|A|)
Visualisierung von UML-Diagrammen » Algorithmus » Hierarchien
Hierarchie
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 31 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 32 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Gleichrichten und Planarisieren
Gleichgerichtete Graphen
Alle Kanten zeigen in die gleiche Richtung
SuperClass1
SuperClass2Class1
SubClass
Class2
Class3
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 33 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Gleichrichten und Planarisieren
Gleichgerichtete Graphen
Alle Kanten zeigen in die gleiche RichtungSuperClass
1
SuperClass2Class1
SubClass
Class2
Class3
SuperClass1
SuperClass2
Class2Class3 Class1
SubClass
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 34 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Gleichrichten und Planarisieren
Hierarchien gleichrichten
Hierarchien werden gleichgerichtet bessere ÜbersichtHierarchien sofort erkennbar
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 35 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Gleichrichten und Planarisieren
Planarisieren
Planare gleichgerichtete Einbettung findenAber: Nicht immer möglich
Planar, aber nicht gleichgerichtet
planar
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 36 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Gleichrichten und Planarisieren
Algorithmen
G ist gleichgerichtet planar und G hat genau eine Senke:
Algorithmus von Bertolazzi (1998)O(|VH|), Algorithmus gibt Einbettung zurück
Mehrere Senken: Supersenke verwenden
sonst: NP-schwer, Kreuzungen durch Dummy-Knoten ersetzen, Algorithmen von Sugiyama oder Eades/Kelly,…
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 37 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 38 von 58
Quelle: Knoten s, nur ausgehende Kanten
Senke: Knoten t, nur eingehende Kanten
ST-Graph: Graph mit genau einer Quelle s, einer Senke t und einer Kante (s, t)
Visualisierung von UML-Diagrammen » Algorithmus » ST-Graph
ST-Graph (1)
s
t
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 39 von 58
Graph mit mehreren Quellen/Senken kann in ST-Graph umgewandelt werden:
Visualisierung von UML-Diagrammen » Algorithmus » ST-Graph
ST-Graph (2)
SuperClass1
SuperClass2
Class
SubClass1 SubClass2
Class
SubClass1 SubClass2
Sink
SuperClass1
SuperClass2
Source
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 40 von 58
Visualisierung von UML-Diagrammen » Algorithmus » ST-Graph
ST-Graph (3)
Class
SubClass1 SubClass2
Sink
SuperClass1
SuperClass2
Source
O(|V|)
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 41 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 42 von 58
Assoziationen innerhalb der Hierarchie H einfügen, Beispiel Composite-Pattern:
Kantenmenge: {(u, v) E | u VH v VH}
Algorithmen von Battista oder Gutwenger
Visualisierung von UML-Diagrammen » Algorithmus » Assoziationen einfügen
Assoziationen einfügen
Leaf Composite
Component
Source
Leaf Composite
Component
Source
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 43 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 44 von 58
Cluster-Graph: C = (G, T) mit G = (V, E) Graph und T = (VT, ET) gerichteter Baum
Cluster: C(v) = (G(v), T(v)) T definiert Inklusionsrelation auf G
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Cluster-Graph
v1
v2
v3
v4
v5
v6 v1 v2 v3 v6v5
v4
c4
c3c2
c1 TG
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 45 von 58
Jede Vererbungshierarchie H bildet ClusterGleichgerichtet planare Einbettungin PH vorhanden
Gesucht: Planare Einbettung des gesamten Graphen, Cluster sollen beachtet werden
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Clusterhierarchien
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 46 von 58
Facette: Flächen, die von Kanten eingeschlossen werden
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Facetten
v1
v4
v2
v3
v7v6
v5
äußere Facette
innere Facette
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 47 von 58
Wheel-Graph: Äußere Knoten bilden einen Kreis, Zentrum c ist mit allen äußeren Knoten verbunden.
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Wheel-Graph
v1
v4
v2
v3
cv5
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 48 von 58
Knoten der äußeren Facette von PH bilden den Kreis des Wheel-Graphen
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Wheel-Graph bilden
v1
v4
v2
v3
cv5c2
c1
v3
v4
v5
v2
v1
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 49 von 58
Assoziationen zu anderen Wheel-GraphenPlanare Einbettung eines Subgraphen finden
Außenknoten des Wheel-Graphen verändert
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Planarisierung
v1
v4
v2
v3
c1
v5u1
u2u3
c2
v1
v4
v2
v3
c1
v5u2
u1u3
c2
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 50 von 58
Wheel-Graph gibt Eingangsreihenfolge vor:
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Cluster-Eingänge
v1
v4
v2
v3
cv5
v1
v4
v2
v5
cv3
v1
v3
v4
v2
v5
v1
v3
v4
v2
v5
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 51 von 58
Alle Wheel-Graphen durch die berechnete planare Einbettung der Hierarchien ersetzenFehlende Kanten zwischen den Hierarchien einfügen (Battista)Dummy-Kanten und -Knoten entfernen
Visualisierung von UML-Diagrammen » Algorithmus » Cluster-Graph erstellen
Cluster-Graph erstellen
v1
v4
v2
v3
c1
v5u2
u1u3
c2
c2
c1
v3
v4
v5
v2
v1
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 52 von 58
Visualisierung von UML-Diagrammen » Algorithmus » Übersicht
Algorithmus
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 53 von 58
Knoten vom Grad ≥ 4 durch Cage ersetzen
Knickminimierung nach TamassiaVerschiedene Nebenbedingungenlinearer Zeitaufwand
Fläche minimierenConstructive flow-based compactionnach Klau, Klein und Mutzel
Visualisierung von UML-Diagrammen » Algorithmus » Orthogonalisieren
Orthogonalisieren
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 54 von 58
EinleitungGrundlagenMotivationZieleGoVisual AlgorithmusZusammenfassungSoftware und Links
Visualisierung von UML-Diagrammen » Agenda
Agenda
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 55 von 58
Visualisierung von UML-Diagrammen » Zusammenfassung
Zusammenfassung
Vorberechnung Hierarchien finden Gleichrichten und planarisieren
ST-Graph erstellen
Assoziationen einfügen Wheel-Graph bilden
OrthogonalisierenPlanare Einbettung finden Wheel-Graphen ersetzen
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 56 von 58
Visualisierung von UML-Diagrammen » Zusammenfassung
Resultate
Microsoft Visio Oreas GDE
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 57 von 58
GoVisual wird von oreas entwickeltDiagramm Editor frei erhältlichBibliotheken & Plug-Insfür Case-Tools werden kommerziell vertrieben
Visualisierung von UML-Diagrammen » Software und Links
Software und Links
http://www.oreas.com
Seminar „Graphenlayoutalgorithmen“, Christian M. Meyer, 24. Juni und 1. Juli 2006 Folie 58 von 58
Seminar „Graphenlayoutalgorithmen“
Vielen Dank für die Aufmerksamkeit
Fragen zum Vortrag?
Folien zum Download:http://uni.christian-meyer.org