Thomas Kramer

IT-COW | All posts tagged 'Walker-Algorithmus'

Übersicht freier Baumzeichnen-Komponenten bzw. Implementierungen

By Administrator at Juni 25, 2012 19:05
Filed Under: Algorithmen

Der Walker-Algorithmus ist ein Verfahren zur Berechnung der x-Koordinaten jedes Knotens eines Baumes, der 1990 von J. Walker II. in seiner Arbeit "A node-positioning algorithm for general trees" vorgestellt wurde. Allerdings stellte sich heraus dass die Laufzeit seiner Implementierung nicht immer linear, sondern in schlechten Fällen Big Omega(n^3/2) ist.

 

Deswegen stellten Buchheim, Jünger und Leipert 2002 einen verbesserten Algorithmus vor, der lineare Laufzeit erreicht. Ihre Arbeit trägt den Titel "Improving Walker's Algorithm to Run in Linear Time" und kann bei SpringerLink für 24,95 Euro online in elektronischer Form gekauft werden.

 

Was Wikipedia zu dem Thema ausspuckt ist übrigens sehr mager. Es gibt im Internet nicht viel Dokumentation zu dem Thema und noch weniger freie Implementierungen. Trotzdem habe ich ein paar interessante Links gefunden.

 

Als erstes muss da das Skript der Universität Konstanz "Der Algorithmus von Walker und seine Verbesserung" genannt werden. Der originale Walker-Algorithmus ist mit Pseudo-Code in der Seminar-Arbeit "Zeichnen von Bäumen" von Lina Wolf skizziert, allerdings fehlt der "SecondWalk" und was "TEILB_TRENNUNG" bedeuten soll ist mir nicht ganz klar. Der optimierte Walker-Algorithmus wird auch in der Diplomarbeit von Frank Benteler der Universität Paderborn behandelt.

 

Das ist dann auch schon so ziemlich alles was sich an frei zugänglicher Dokumentation dazu im Internet finden lässt. Ich habe vier verschiedene Implementierungen dazu im Internet gefunden:

 

  • 1. Die optimierte Walker-Implementierung von abego-TreeLayout (BSD-Lizenz): Link. In der TreeLayout-Klasse gibt es da bekannte Methoden wie ancestor, moveSubtree, apportion, executeShifts, firstWalk und secondWalk.
  • 2. Die optimierte Walker-Implementierung ImprovedWalker gehört zu den Addons der Data Visualization Software Tulip und ist in C++ programmiert (LGPL-Lizenz). Sie enthält bekannte Methoden wie moveSubtree, executeShifts, firstWalk und secondWalk.
  • 3. Die Ontologie-Software TooCoM benutzt ebenfalls den optimierten Walker-Algorithmus und steht unter GPL-Lizenz, ist also für kommerzielle Projekte tabu. Ihr Quellcode kann auf koders.com eingesehen werden.
  • 4. Unter dem Titel "Graphic JavaScript Tree with Layout" gibt es auf codeproject.com eine JavaScript-Komponente zum Baumzeichnen, diese scheint den originalen Walker-Algorithmus zu benutzen - jedenfalls ist als Referenz unten nur Walkers Arbeit angegeben, nicht die Optimierungen von Buchheim, Jünger und Leipert. Die Komponente steht unter einer eigenen, CPOL genannten Lizenz.

 

Erfahrungen mit TooCoM

 

habe ich mittlerweile ausgelagert in einen eigenen Artikel: Link.

 

Allgemeines bzw. Ergänzungen

 

Laut abego-Dokumentation enthält die Netbeans Visual API bereits einen Algorithmus zum Baumzeichnen, wobei TreeLayout in einigen Fällen platzsparendere Resultate zurückliefern soll.

 

Die Open Source Graph Visualization Software Graphviz müsste eigentlich auch den Walker-Algorithmus implementiert haben - auf 4webmaster.de gibt es eine deutschsprachige Anleitung dazu.

 

In der sehr interessanten Ausarbeitung User Interface Engineering der Universität Magdeburg werden außerdem verschiedene Visualisierungs-Frameworks für Graphen, darunter auch Tulip, vorgestellt.

 

Update 14.07.2012: Außerdem habe ich für das .net-Framework noch QuickGraph und Dot2WPF gefunden. Kommerzielle Komponenten gibt es natürlich auch noch, aber das Angebot bezüglich freier Bibliotheken finde ich bislang sehr mager.

 

Ich habe einmal versucht mittels dem Java-Compiler gcj und dem Tutorial den abego TreeLayout-Sourcecode als EXE-Datei zu kompilieren, aber das scheitert gemäß den Fehlermeldungen daran dass der gcj keine Generics beherrscht - zumindest bei Interfaces. Und beim import-Befehl kommt er mit dem static-Schlüsselwort nicht zurecht. Schade, denn die TreeLayout-Bibliothek gibt es nur für Java.

 

Ich wollte eine EXE-Datei generieren die die x-Koordinaten in eine Textdatei ausgibt, um die Bibliothek so auch aus anderen Programmiersprachen heraus verwenden zu können - aber wenn das mit gcj nicht geht und man weiterhin Java zum Aufrufen verwenden muss kann man die Bibliothek auch direkt benutzen.

 

TreeLayout besteht aus 13 Klassen respektive Interfaces - eine komplette Portierung scheint möglich, aber nicht ganz unaufwendig zu sein. Natürlich könnte man bei einer Portierung sich auch allein auf den Walker-Algorithmus beschränken, der in der TreeLayout-Klasse enthalten ist. Wie gesagt, TreeLayout steht unter BSD-Lizenz, möglich ist das schon aber man muss natürlich die Copyright-Notizen drin lassen.

 

Am besten man implementiert den Algorithmus einmal selbst oder man verwendet transparent sowas wie Graphviz.

 

Update 15.07.2012: Die Diskussionsseite von stackoverflow offenbart noch weitere Alternativen wie Graph#, Microsoft Automatic Graph Layout (280 Dollar), das ältere GLEE (kostenlos), Microsoft Chart Controls for ASP.NET und WinForms. QuickGraph selbst scheint eine Portierung der Boost Graph Library zu sein.

 

Aber wenn ich das richtig sehe scheinen mir das meistens allgemeine Graphen-Algorithmen zu sein, nicht immer auch für Bäume. Bäume sind eine Unterform der Graphen, aber es gibt natürlich auch noch andere Arten.

 

Tag-Wolke

Monats-Liste