Graph Explorer

Informationsvisualisierung VO/UE SS 2006

Martin Suntinger 0405478, Martin Schreiber 0425891

Basierend auf:
Yee K., Fisher D., Dhamija R., Hearst M.: Animated Exploration of Dynamic Graphs with Radial Layout, University of California, Berkeley


Inhalt

Die verwendeten Techniken aus dem Paper
  Konzept des Papers
Radial Layout
Space Allocation
Smooth Animation
Das Programm
  Verwendete Technologien
Eingabedaten
Features & Gui
Bemerkungen
Download

Die Verwendeten Techniken aus dem Paper

Konzept des Papers

Das Paper beschreibt eine Technik zur interaktiven, animierten Erforschung eines Graphen, dessen Ansicht durch das Selektieren eines bestimmten Fokusknotens bestimmt wird. Der Graph wird nach einer solchen Selektion neu nach dem entsprechenden Knoten ausgerichtet. Hierbei werden Transitionstechniken verwendet, die dem Benutzer ein intuitives und übersichtliches Erforschen ermöglichen sollen. Darstellbar sind alle möglichen Arten von ungerichteten Graphen wie beispielsweise soziale Netzwerke. Allerdings muss der Graph zusammenhängend sein, also es muss von jedem Knoten aus über einen Weg jeder andere erreichbar sein.

Radial Layout

Im radialen Layout werden die Knoten eines Graphen in konzentrischen Kreisen um einen Fokusknoten als Mittelpunkt angeordnet. Mittles einer Breitensuche wird vom Fokusknoten ausgehend ein Baum aus dem Graphen erstellt. Die direkten Nachbarknoten dieses Baumes werden jeweils auf dem n ächsten oder vorhergehenden Ring positioniert.

Space Allocation

Knoten können ein variables Gewicht bzw. variable Größen besitzen. Je nachdem, wie viel Gewicht ein Knoten zusammen mit den Kindern seines Subbaumes hat, desto mehr Platz wird im zugeteilt. Jeder Knoten bekommt nach dieser Berechnung einen Kreissektor ensprechender Größe auf dem aktuellen Ring zugeteilt. Alle Kinder des Knotens auf diesem Subbaum befinden sich dann ebenfalls in diesem Sektor. Dieser Algorithmus für die Platzallokation läuft dann rekursiv weiter.

Smooth Animation

Wird ein neuer Fokusknoten gewählt, erscheint der Graph oft in einer komplett anderen Anischt als zuvor. Ohne einer entsprechenden Animation, die während der Transition stattfindet, würde sehr bald die Übersicht verlorengehen. Anstatt jedoch einfach die Knotenposition linear zu interpolieren, was naheliegen würde, wird im Paper die Interpolation der Polarkoordinaten vorgeschlagen. Dies hat den Effekt, dass sich alle Knoten bei der Transition auf Kreisbahnen entweder im oder gegen den Uhrzeigersinn bewegen, und nicht in alle erdenklichen Richtungen gleichzeitig wandern.
Außerdem wird eine Technik namens Slow-In-Slow-Out verwendet, bei der die Animationsgeschwindigkeit dem Namen entsprechend reguliert wird. Hierbei erscheint die Geschwindigkeit unter Zuhilfenahme einer Arcus-Tangens-Funktion bei Beginn der Animation langsam, erhöht sich im weiteren Verlauf und nimmt gegen Ende hin wieder ab.

    zum Inhalt

Das Programm

Verwendete Technologien

Das Programm wurde mit der Programmiersprache JAVA realisiert. Um die graphische Darstellung zu erleichtern, wurde das Open Source Framework Piccolo verwendet. Die Eingabedaten werden mit einem XML-File eingelesen.

Eine Javadoc ist hier einzusehen: Graph Explorer Javadoc (online HTML)
oder hier downzuloladen: Graph Explorer Javadoc(.ZIP Folder)
Das Programm kann als .jar File downgeloadet werden, welches auch die Source Files enthält: Graph Explorer executable JAR (.jar File)

    zum Inhalt

Eingabedaten

Das Einlesen der Daten für den Graphen erfolgt über ein XML-File.

Das File hat einer bestimmten Struktur zu entspechen.
Details dazu finden sie hier: XML-Struktur

    zum Inhalt

Features & Gui

Folgende Features wurden implementiert und werden nun anhand des graphischen Interfaces erklärt:

Bereiche im Gui:

Display Options: Setzen sämtlicher Parameter für die Darstellung des Graphen. Wird weiter unten näher erläutert.
Content Explorer: Liste der vohandenen Knoten, die über diesen Bereich direkt anwählbar sind.
Color Legend: Farblegende, die dem Benutzer die Bedeutung der Farben erklären.
Graph: Bereich, in dem der Graph dargestellt wird. Durch klicken auf einen Knoten wird dieser als Fokusknoten selektiert. Eine aufklappbare Infobox liefert weitere Content-Informationen.

Die folgende Abbildung zeigt die Oberfläche des Graph Explorer mit einem geladenen Beispielgraph, bei dem Icons zur Knotenrepräsentation verwendet werden. Dies ist eine optionale Erweiterung der Darstellung. Sind keine Icons vorhanden, werden die Knoten durch farbige Kreise repräsentiert, wobei die Farbcodierung einem Datenattribut entspricht.

    zum Inhalt

Display Options im Detail

Settings:
Hier gibt es zwei Schieberegler:
Mit "Scale Ring Offset" kann man den Abstand zwischen 2 Ringen regulieren.
Mit "Fish Eye Effect" kann man die Intensität des Fischaugeneffekts regulieren, welcher der Anstand der Ringe nach außen hin weiter verringert.
Attributes:
Hier kann man die Attribute bestimmen, die im Graph angezeigt werden sollen.
Size Attribute: das Größenattribut.
Color Attribute: das Farbattribut.
Colors:
Hier kann man, sofern man es wünscht, die Farbe des Hintergrundes und die Farbe der Ringe bestimmen.
Canvas Color: Hintergrundfarbe
Ring Color: Ringfarbe
Animation:
Mit dem Schieberegler "Animation Speed" kann man die Animationsgeschwindigkeit regulieren.
Connections:
Bei Selektion von "Tree Connections only" werden keine Querverbindungen, die nicht im Baum vom Fokusknoten aus liegen, angezeigt.
Wird "All Connections" selektiert, kann man über den Schieberegler "CrossRef alpha" die Transparenz besagter Linien regulieren.
Nodes:
Hier können sie über den Schieberegler "Node Size" die Größe aller Knoten regulieren.
Wählen Sie "Use Icons", werden die den Knoten zugewiesenen Icons angezeigt.
Wählen Sie "Scale Icons", werden die Icons außerdem nach dem gerade gewählten Größenattribut skaliert.
    zum Inhalt

Bemerkungen

Zum Leistungstest wurde ein Testdatengenerator erstellt, mit dem man einen Graphen beliebiger Größe erzeugen kann. Ein solcher Graph erhält dann pro Knoten 1-2 Querverweise, sowie 5 zufällig gewählte Farb-und Größenattribute. Auf dem Testgerät (1.73 Ghz Centrino, 1024 MB RAM) war ein Graph mit ca. 1300 Knoten darstellbar, Animationen waren jedoch nicht mehr sinnvoll durchfürbar.

Beispiele für große Graphen:

    zum Inhalt

Download

Eine Javadoc ist hier einzusehen: Graph Explorer Javadoc(online HTML)
oder hier downzuloladen: Graph Explorer Javadoc(.ZIP Folder)
Die Beispieldaten können gibt es ebenfalls als .zip file: Graph Explorer Beispiele (.zip)
Das Programm kann als .jar File downgeloadet werden, welches auch die Source Files enthält: Graph Explorer executable JAR (.jar File)

    zum Inhalt