Hierarchische Information ist allgegenwärtig: Stammbäume, Organigramme, Taxonomien oder auch Produktstrukturpläne. Eine gute graphische Darstellung ermöglicht einen schnellen Überblick. Allerdings ist die manuelle Erstellung einer schönen Zeichnung mit hohem Aufwand verbunden. Hier soll gezeigt werden, wie ein derartiger Vorgang automatisch durchgeführt werden kann.

Ein sehr grober hierarchischer Aufbau (Produktstrukturplan) eines Autos könnte folgendermaßen aussehen:

Die Zeichnung aus Abbildung 1 hat einige sehr positive Eigenschaften:

• Die hierarchische Struktur (Vater-Kind-Beziehung) ist deutlich erkennbar.
• Die einzelnen Teilbäume (z.B. Fahrwerk und Motor) sind klar voneinander getrennt (engl.: “subtree separation”).
• Die Zeichnung ist platzsparend und wurde so angefertigt, dass sie gut im Querformat ausgedruckt werden kann.

Klassische Darstellung vs. Tip-over-Layout

Die klassische Darstellung von Baumstrukturen ist weniger auf Kompaktheit ausgelegt (siehe Abb. 2). Schön an dieser Darstellungsweise ist, dass die Vater-Kind-Beziehungen noch ein wenig besser hervorstechen als in Abbildung 1, allerdings ist das Seitenverhältnis der Zeichnung deutlich schlechter für die Darstellung am Monitor oder zum Ausdrucken geeignet.

Der Grund hierfür ist, dass die Kindknoten eines Vaterknotens immer horizontal angeordnet werden müssen. Bei Tip-over-Layouts können die Kinder entweder horizontal oder vertikal angeordnet werden (siehe Abb. 1). Durch diese Wahlfreiheit entstehen Variationsmöglichkeiten, die es ermöglichen, die Zeichnung auf unterschiedliche Platz-Anforderungen zu optimieren.

Kostenfunktionen

Der Platzverbrauch eines Tip-over-Layouts kann bzgl. einer gegebenen Kostenfunktion mit den Variablen Breite b und Höhe h minimiert werden (siehe [1]). Einige Beispiele:

• Fläche: b · h
• Umfang: 2 · (b + h)
• Minimales umfassendes Quadrat: max (b, h)
• Minimales umfassendes Rechteck, wobei das Seitenverhältnis r = b / h fest vorgegeben ist: max (b, h · r)

Will man z.B. eine Zeichnung so optimieren, dass sie gut auf ein Blatt Papier im DIN A4-Querformat passt, kann man die letzte Kostenfunktion mit r = 29,7 cm / 21 cm ≈ 1,414 verwenden. Das selbe Seitenverhältnis kann natürlich auch für alle anderen DIN A-Querformate (A0, A1, A2, A3, etc.) verwendet werden.

Zurück in die reale Welt

Reale Anwendungsfälle sind natürlich deutlich komplexer als das Beispiel aus Abbildung 1. Hunderte oder sogar Tausende von Knoten sind keine Seltenheit und einzelne Knoten können dabei sehr viele Unterknoten haben, was zu viel ungenutztem Platz führt. Das macht nicht nur die Darstellung am Monitor schwierig, sondern auch besonders das Ausdrucken auf Papier. In Abbildung 3 ist eine Zeichnung zu sehen, die zwar auf DIN A-Querformat optimiert ist, aber die Möglichkeiten des Algorithmus sind in diesem Fall nicht ausreichend, da er – wie immer bei Verwendung eines Tip-over-Layouts – alle Kindknoten eines Vaterknotens entweder nebeneinander oder untereinander anordnen muss. Beides kann bei einer großen Anzahl von Kindknoten sehr ungünstig sein.

Bei großen Zeichnungen kann es so sehr schnell passieren, dass man die Beschriftungen der Knoten nicht mehr lesen kann, selbst wenn man sehr große Formate, wie DIN A0, verwendet.

Bäume aufteilen und herumjonglieren

Man kann platzsparende Zeichnungen manuell erstellen. Der Ersteller einer Zeichnung wird in Fällen wie in Abbildung 4 normalerweise zu folgendem Trick greifen, um Platz zu sparen: Ist die Anzahl der Kindknoten eines Vaterknotens besonders groß, dann teile die Kindknoten in mehrere Gruppen ein (siehe Abb. 5). Innerhalb dieser Gruppen werden alle Kindknoten horizontal angeordnet und die Gruppen selbst werden vertikal angeordnet (siehe Abb. 6).

Bei großen Zeichnungen ist eine manuelle Erstellung äußerst mühsam und zeitaufwändig. Es können sich auch jederzeit kleine Fehler oder Unregelmäßigkeiten einschleichen, die die Qualität der Zeichnung beeinträchtigen. Außerdem muss bei jedem entfernten oder neu hinzugefügten Knoten erneut Hand angelegt werden.

Lockermachen mit TreeJuggler

Die Software TreeJuggler kann automatisch kompakte Zeichnungen erstellen. Sie wurde als Teil des Open Source Projekts Gravisto (siehe auch [2]) im Rahmen meiner Diplomarbeit implementiert, und setzt ein Verfahren um, das die Struktur von Bäumen zunächst automatisch auflockert, um dann platzsparende Tip-over-Layouts erstellen zu können. Der folgende Algorithmus wird vom TreeJuggler-Kommandozeilen-Interface (TreeJugglerCLI) genutzt:

1. Der Baum wird zunächst von einem Baum mit sehr hohem Grad (viele Kindknoten pro Vaterknoten) in einen Baum mit lediglich zwei Kindknoten pro Vaterknoten umgewandelt. Diese Umwandlung geschieht – analog zu Abb. 5 – durch das Einfügen von Hilfsknoten (siehe Abb. 7).
   

   Abb. 7: Auflockern eines Baums, so dass jeder Knoten nur noch zwei Kinder hat.

2. Ein Tip-over-Layout des Baums unter Berücksichtigung der gewählten Kostenfunktion wird berechnet.
3. Nicht benötigte Hilfsknoten (in denen kein Richtungswechsel von horizontal nach vertikal oder umgekehrt stattfindet) werden entfernt.
4. Hat sich der Wert der Kostenfunktion weiter verringert, dann gehen wir zurück zu Schritt 2, andernfalls gehen wir weiter zu Schritt 5.
5. Die verbliebenen Hilfsknoten werden durch Knicke in den Kanten ersetzt.

TreeJuggler im Einsatz

Abbildung 8 zeigt ein mit TreeJuggler vollautomatisch erzeugtes Tip-over-Layout, das die selben Daten darstellt wie in Abbildung 3, allerdings ist der Platzverbrauch um den Faktor 4,65 geringer.

TreeJuggler ist ein Gravisto-Plugin und kann daher auch zum manuellen Zeichnen mit Hilfe einer grafischen Benutzeroberfläche verwendet werden. Zu diesem Zweck gibt es die TreeJuggler-Toolbox (siehe Toolbar in Abb. 9), mit der die einzelnen Algorithmen von TreeJuggler manuell auf den ganzen Baum oder auch nur auf bestimmte Teilbäume angewendet werden können.

Es können auch Zusatz-Anforderungen (z.B. ein Knoten soll ganz links in der Zeichnung erscheinen, muss seine Kinder horizontal anordnen, etc.) formuliert werden. Dies geschieht mit Hilfe von speziellen Knoten-Attributen.

TreeJuggler wird bereits seit einigen Jahren bei Airbus Space (früher Astrium GmbH) erfolgreich eingesetzt. Es wird dort zum automatischen Zeichnen von Produktstrukturplänen im Rahmen des Projekts Grafischer Baum verwendet. Die visualisierten Daten werden hierfür aus dem firmeneigenen SAP-System als Materialstücklisten extrahiert.

Zum Ausprobieren von Gravisto und TreeJuggler gibt es Informationen auf der Gravisto-Homepage auf Github. Bitte beachten, dass die frühere Gravisto-Homepage nicht mehr verfügbar ist (siehe hierzu Neues Zuhause für Gravisto). Nach dem Checkout des Java-Source-Codes mit Hilfe der bereitgestellten Datei gravisto.psf steht eine Launch Configuration für 64 und 32 Bit in der Eclipse IDE zur Verfügung.

Literatur

1. 1. EADES, Peter; LIN, Tao; LIN, Xuemin. Two tree drawing conventions. International Journal of Computational Geometry & Applications, 1993, 3. Jg., Nr. 02, S. 133-153.
   2. Gravisto: Graph Visualization Toolkit (Poster), Graph Drawing Conference, GD 2004. [PDF]