Programm: AEODGWRL
Dokumentation: JavaDoc
Quellcode: src.zip
How to Use:
Die GUI ist in drei Bereiche eingeteilt: Anzeigefenster/Canvas ganz rechts, dynamischer Hilfe-Text darüber und links die Bedienfläche.
Der Canvas wird mit der Maus gesteuert: mit gedrückter Maustaste (Maus 1) ziehen bewegt den Bildausschnitt, Mausradscrollen zoomt in bzw aus dem Bildausschnitt, und mit Doppelcklick (Maus 1) werden Knoten selectiert/fokusiert.
Die Bedienfläche wird in drei Bereiche unterteil: NODE (Interaktion mit Knoten), MANAGE DATA (zum Laden, Speichern und Graph Generieren) und CHANGE VIEW (zum ändern von Anzeigeparametern).
NODE:
Insert: Click auf den Button, dann Doppelclick auf einen den Knoten, der Vaterknoten des einzufügenden Knotens werden soll und dann im Pop-Up-Dialog Name, Größe und Bild des neuen Knotens bestimmen.
Edit: Click auf den Button, dann Doppelclick aud den zu verändernden Knoten und dann im Pop-Up-Dialog Name, Größe und Bild des Knotens bestimmen.
Remove: Click auf den Button, dann Doppelclick aud den zu löschenden Knoten.
Insert Edge: Click auf den Button, dann Doppelclick auf den ersten und dan Doppelclick auf den zweiten Knoten der einzufügenden Kante.
MANAGE DATA:
Load Graph: Click auf den Button, dann im Filedialog die zu ladende Datei auswählen.
Save Graph: Click auf den Button, dann im Filedialog den Speicherort und Speichernamen bestimmen.
Generate Graph: Click auf den Button.
CHANGE VIEW:
Scale Rings: Bewege den Slider um die Größe der Ringe des Radialen Layout zu verändern.
Disort Rings: Bewege den Slider um den Gößenunterschied der äußeren Ringe zu verkleinern.
Animation Time: Bewege den Slider um die Animationszeit von einem Layout zum nächsten zu verlängern oder zu verkürzen.
show Names: Selektiere die Checkbox um die Namen der Knoten anzuzeigen, deselektiere sie um sie auszublenden.
show None-Tree Edges: Selektiere die Checkbox um die Kanten des Graphs, die im radialen Layout nicht Baum-Kanten sind, anzuzeigen, deselektiere sie um sie auszublenden.
Paperbeschreibung:
Ziel: Wir haben das Paper Animated Exploration of Dynamic Graphs with Radial Layout ("Animierten Erkundung dynamischer Graphen mit radialem Layout") implementiert, dessen Ziel es ist, große, dynamisch
veränderliche Graphen von der Perspektive verschiedener Knoten aus zu betrachten mit Augenmerk auf die
Distanzen zu anderen Knoten im Graphen. Diese Perspektive soll der User von einem Knoten zum anderen
wechseln können, ohne dabei den Kontext zu verlieren, daher animiert man diesen Wechsel des Layouts, um
dem User ein Verfolgen der Knotenbewegung zu ermöglichen, wenn er den Fokus auf einen anderen Knoten
ändern möchte.
Durch obige Voraussetzungen soll es möglich sein eine gut zu erkundende und leicht zu verstehende Darstellung
von Netzwerkstrukturen, Netzwerkkommunikation und Sozialen Netzwerken und vor allem der Entfernungen
einzelner Knoten zueinander zu realisieren.
Radiales Layout: Beim radialen Layout eines Graphen werden dessen Knoten auf konzentrischen Kreisen, im Folgenden auch Ringe genannt, angeordnet. Dazu wird der Graph in einer Art Baumstruktur angeordnet, wobei aber Zyklen erlaubt sind. Ein Knoten, in unserem Fall der Knoten auf dem der User den Fokus gerichtet hat, wird als Wurzel bestimmt. Dieser wird in den Mittelpunkt der konzentrischen Kreise gesetzt. Alle benachbarten Knoten werden als dessen Kinder betrachtet und auf den innersten Ring gelegt. Alle benachbarten Knoten eines Kindes (außer schon betrachtete Knoten, da wir ja Zyklen erlaben) werden zu Kindern des Kindes und werden auf den 2. Ring gesetzt. Dieser Vorgang wird wiederholt, bis man alle Knoten des Graphen betrachtet und auf einem Ring platziert hat. Wenn man diesen Algorithmus mit Breitensuche umsetzt, repräsentiert die Distanz vom Knoten zum Mittelpunkt die minimale Entfernung zum Knoten auf dem der User gerade den Fokus hat. Um eine gleichmäßige Verteilung der Knoten auf den Ringen zu garantieren und Kantenüberschneidungen zu minimieren, wird jedem Knoten ein Sektor zugeordnet, in dessen Mitte der Knoten selbst platziert wird. Die Sektorgröße berechnet sich aus der Knotengröße durch die Entfernung zum Mittelpunkt. Ist jedoch die Summe der Sektoren der Unterbäume des Knotens größer, wird dieser Wert als Sektorgröße des Knotens genommen.
Animation: Um dem User den Wechsel von einem fokussierten Knoten (im Mittelpunkt dargestellt) zu einem
anderen zu erleichtern, ist eine gute und weiche Animation notwendig und ein resultierendes Layout, das sich
nicht zu sehr vom Ursprungs-Layout unterscheidet, um die Bewegung der Knoten gering zu halten, damit der
User der Animation folgen kann und nicht nur verwirrt wird.
Wird die eine Knotenbewegung nicht durch Interpolation der kartesischen Koordinaten, sondern der
Polarkoordinaten vollführt. Dadurch kommt es zu weniger Kollisionen, also Überdeckungen, der Knoten,
wodurch dem User das Verfolgen einzelner Knoten ermöglicht wird. Bei einer Interpolation der kartesischen
Koordinaten, was in einer Bewegung der Knoten auf einer Geraden zu ihrer neuen Position resultieren würde,
käme es zu Haufenbildungen im Zentrum des Layouts (vor allem bei Graphen mit vielen Knoten), die nicht mehr
nachvollziehbar wäre.
Beim Start und Ende der Knotenbewegung ist eine Beschleunigung bzw. Verlangsamung der Bewegung
hilfreich, da dies der menschlichen Wahrnehmung vertrauter ist und deshalb leichter zu erfassen ist. Es kann z.B
statt einer linearen Interpolation eine Interpolation mittels des Arcustangens verwendet werden (smoothin/
smooth-out).
Damit sich das Layout möglichst wenig verändert wird folgende Heuristik verwendet:
1. Die Orientierung der Kante des neu fokussierten Knoten zu seinem Vaterknoten soll im neuen Layout
beibehalten werden, damit sich der Graph nicht zu sehr verdreht.
2. Die Reihung der Ausgangswinkel der Kanten eines Knotens soll gleich bleiben, um Überschneidungen zu
verhindern und somit die allgemeine Struktur so gut wie möglich beizubehalten.
Implementierung: Die Implementierung findet in der Programmiersprache Java sowie mithilfe der
Entwicklungsumgebung Eclipse statt.
Weiters verwenden wir Batik, eine SVG Bibliothek, zur Darstellung des Graphen.
Der grobe Algorithmische Vorgang zur Darstellung des Graphen schaut folgendermaßen aus. Zuerst berechnet
die Breitensuche Vater-Kind-Beziehungen. Die danach folgende Tiefensuche ermittelt die Position des Knotens
auf dem Ring, wobei zuvor rekursiv die Winkelbreite der einzelnen Knoten ermittelt wird. (Innerhalb des
Sektors der mit dieser Winkelbreite definiert wird, kann nun der Knoten sowie dessen Unterbaum graphisch
dargestellt werden.)
Am Schluss werden die Verhältnisse auf einen vollen Winkel mittels nochmaliger Breitensuche normiert, da
während dieser Aufrechnung die Winkel der Nachbarn berücksichtig bzw. das Total aller Winkel der Knoten
dieser Ebene berechnet werden müssen.
Die grobe Klassenstruktur des Knoten schaut wie unten dargestellt aus.
Aufgrund von Performanceüberlegungen entscheiden wir uns dazu die Nachbarknoten sowie den Vaterknoten
zusätzlich innerhalb eines Knotens zu speichern, um die Aufrechterhaltung der Übergangsbedingungen während
der Übergangsanimationen des Graphen effizienter zu bewerkstelligen.
