|
|
|
|
|
|
|
|
|
|
|
|
|
Fakultät Lehrstühle, Professuren und Fachgebiete der FIM Theoretische Informatik Projekte VisnaCom
Auf diesen Seiten wird ein Editor für hierarchisch geschachtelte Graphen (engl. compound graphs) vorgestellt. Dieses Programm wurde im Rahmen zweier Diplomarbeiten unter der Betreuung von Marcus Raitner am Lehrstuhl Prof. Dr. Franz Brandenburg der Fakultät für Mathematik und Informatik der Universität Passau erstellt. Beide Diplomarbeiten basieren auf den Ergebnissen der Dissertation "Efficient Visual Navigation of Hierarchically Structured Graphs" von Marcus Raitner.
Grob formuliert lassen sich mit dem Programm Graphen erstellen, welche eine zusätzliche rekursive Komponente enthalten, derart dass ein Knoten des Graphen wiederum einen Graphen enthalten kann (siehe unten, Absatz "Hierarchisch geschachtelte Graphen"). Dabei ist es weiter möglich derartige Knoten zu einem Metaknoten zu kontrahieren, d.h. Information über die im Knoten enthaltenen Knoten auszublenden, bzw. Metaknoten zu expandieren, d.h. ausgeblendete Information wiederherzustellen. Es lassen sich also z.B. Straßenkarten oder Telefonnummerverzeichnisse mit diesem Editor modellieren, und je nach Wunsch des Benutzers können diese mehr oder weniger detailliert in verschiedenen Ansichten dargestellt werden. Editoren, welche solche Datenstrukturen verarbeiten können, existieren zwar bereits, allerdings verwendet der hier vorgestellte Editor neue, effiziente Ansätze für Datenstruktur und Layout-Algorithmus, welche aus oben erwähnter Dissertation stammen. Im Folgenden wird aufgeführt, welche Leistungsmerkmale des Programms in den beiden Diplomarbeiten implementiert wurden.
In der Diplomarbeit "Entwicklung eines Editors für hierarchisch geschachtelte Graphen" (Franz Pfeiffer, 2005) wurde implementiert
In der Diplomarbeit "Visuelle Navigation in Compound Graphen" (Michael Pröbster, 2005) wurde implementiert
Die exakte Definition des Begriffs "Hierarchisch geschachtelter Graph" (engl. compound graph) lautet:
Hierarchisch geschachtelter Graph:
Ein hierarchisch geschachtelter Graph wird geschrieben als G = (V, E, F), wobei V die Knoten, E die (gerichteten) Inklusionskanten und F die (gerichteten oder ungerichteten) Adjazenzkanten bezeichnet. Der Digraph, welcher die Inklusion ausdrückt, ist hier ein Baum und es ist nicht möglich, dass eine Kante aus F Knoten verbindet, welche bzgl. der Inklusionshierarchie in einer Vorgänger/Nachfolger-Beziehung stehen.
Durch den Inklusionsbaum wird also modelliert, welche Knoten in einem anderen Knoten enthalten sind, womit man die hierarchische Komponente erhält. Der Editor unterstützt auch, dass der Benutzer sich in mehreren Frames unterschiedliche Ansichten desselben Graphen ansehen, und durch Änderungen dieser Ansichten auch den eigtl. zugrundeliegenden Graphen verändern kann. In folgender Abbildung wird gezeigt, wie zwei Ansichten des gleichen Graphen dargestellt werden. Die graue Farbe eines (kleinen) Knotens zeigt hier, dass dieser in der entsprechenden Ansicht kontrahiert ist, d.h. Information über enthaltene Knoten ist in der Ansicht ausgeblendet. Wie man sieht geht in diesem Fall die Kante vom kontrahierten Knoten aus (sog. abgeleitete Kante).
Hier wird beschrieben, welche Operationen vom Editor zum Erstellen hierarchischer Graphen angeboten werden.
Neue Knoten einfügen: Es gibt zwei Möglichkeiten, um einen neuen Knoten einzufügen. Einerseits kann man angeben, welcher bereits existierende Knoten den neuen enthalten soll (neues Blatt in Inklusionsbaum), andererseits ist es auch möglich, anzugeben welche Knoten im neuen enthalten sein sollen (in diesem Fall benötigen die angegebenen Knoten den gleichen Vaterknoten im Inklusionsbaum). Für den zweiten Fall ist unten ein Beispiel angegeben.
Knoten entfernen: Knoten können auch wieder entfernt werden. Auch hier gibt es analog zum Einfügen zwei Fälle. Man kann nämlich Knoten entfernen unabhängig davon, ob diese andere Knoten enthalten oder nicht.
Kanten einfügen und entfernen: Es können Kanten zwischen beliebigen Knoten gezogen werden. Beachtet werden muss allerdings, dass Mehrfachkanten und Kanten zwischen Knoten, die im Inklusionsbaum in Vorgänger-/Nachfolger- Beziehung stehen, nicht erlaubt sind. Kanten können natürlich auch wieder gelöscht werden.
Verschieben von Knoten innerhalb Hierarchie: Der Editor erlaubt es dem Benutzer Knoten innerhalb der Inklusionshierarchie zu verschieben. Hierfür ist in der folgenden Abbildung ein Beispiel aufgeführt. Beachtet werden muss, dass die Verschiebung nicht zu ungültigen Kanten (s.o.) führt.
Zusätzlich dazu gibt es zum Aus-/Einblenden von Information und somit zum Erstellen unterschiedlicher Ansichten eines Graphen noch folgende Operationen:
Kontrahieren von Knoten: Mit dieser Operation werden die in dem zu kontrahierenden Knoten enthaltenen Knoten aus der Ansicht entfernt. Dabei werden die zu den entfernten Knoten inzidenten Kanten ebenfalls entfernt und durch sog. abgeleitete Kanten ersetzt.
Expandieren von Knoten: Die zur Kontraktion inverse Operation.
In der folgenden Abbildung kann man sehen wie sich Expansion (bzw. Kontraktion) auswirkt.
Auf dieser Seite wird vorgestellt, welche Funktionalität der Editor zur Verfügung stellt.
In diesem Menü können Editierflächen für neue Graphen bzw. Ansichten bereits bestehender Graphen geöffnet werden. Darüber hinaus können hier Graphen (und deren Ansichten) gespeichert bzw. geladen werden.
Hier erhält der Benutzer Zugang zur Cut-/Copy-/Paste-Funktionalität. Darüber hinaus kann in diesem Menü auf Selektion und Löschen von Elementen zugegriffen werden. Schließlich ist es auch möglich, eine Ansicht vom aktuellen Layout-Algorithmus hier (wieder) neu zeichnen zu lassen.
Hier kann der Benutzer seine Präferenzen einstellen und speichern. Das heißt hier können u.a. Animations- und Layout-Algorithmus bestimmt werden.
Hier kann man sich eine kurze Onlinehilfe und Programminformationen anzeigen lassen.
Über die Toolbar sind nochmals die wichtigsten der oben bereits erwähnten Funktionen zugänglich: Neuer Graph, neue Ansicht, Laden und Speichern, Cut/Copy/Paste.
Mit oben abgebildeten Buttons ist es möglich die einzelnen Editiermodi zu aktivieren. Diese sind von oben nach unten:
In den folgenden UML-Diagrammen wird die Architektur des Editors modelliert. Dabei orientiert sich das Design am Model-View-Controller-Pattern, wobei den einzelnen Teilen dieses Design-Patterns die folgenden Rollen zukommen:
Hier befindet sich die Datenstruktur (DynamicLeaves), also die Implementierung des hierarchischen Graphen. Ferner befindet sich hier die Umsetzung der Ansichten eines Graphen (Klasse View). Hilfsklassen (OrderMaintenance, AncestorAtLevel) implementieren effiziente Algorithmen, welche zur Expansion von Knoten in einer Ansicht benötigt werden.
Im View-Teil des Design-Patterns befinden sich die Klassen, welche zur grafischen Darstellung der Ansichten benötigt werden, also auch Layout- und Animationsalgorithmen.
Hier wird die Benutzeroberfläche realisiert. Das heißt hier befinden sich auch die Listener, welche die Reaktion auf Benutzereingaben umsetzen.
Um Graphen und deren Ansichten speichern zu können, wird eine Erweiterung von 
GraphML verwendet. Eine Erweiterung ist deshalb nötig, weil GraphML zwar das Speichern hierarchischer Graphen ermöglicht, aber Ansichten ergänzt werden müssen.
Eine Ansicht wird in der Erweiterung deklariert als:
<data key="view">
<view>
<node id="0">
<data key="x">221</data>
<data key="y">148</data>
<data key="width">26</data>
<data key="height">26</data>
</node>
<node id="1">
<data key="x">116</data>
<data key="y">108</data>
<data key="width">26</data>
<data key="height">26</data>
</node>
<edge id="0" source="1" target="0">
<data key="poly">237</data>
<data key="poly">63</data>
</edge>
</view>
</data>
Dabei können mit <view> auch mehrere Ansichten begonnen werden. Die GraphML-Attribute bei den Knoten bzw. Kanten geben die Koordinaten der Knoten bzw. Kontrollpunkte bei Polylinien (als Kanten) an.
Wir über uns
Mitarbeiter
Projekte
