ob im Liniennetzplan von
Verkehrsunternehmen, bei der Routenplanung im Auto oder bei der Dynamik
von Freundschaftsbeziehungen in sozialen Netzwerken: Detailreiche
Informationen können vom Menschen am besten visuell erfasst werden. Doch
damit entsprechende Graphen gut lesbar sind, müssen Computer ein gutes
Layout – also eine optimale Positionierung aller Knotenpunkte und
Verbindungen berechnen. Bei großem Detailreichtum ist dafür eine enorme
Rechenleistung notwendig. Um diesen Zeichenprozess zu beschleunigen,
haben Informatiker des Karlsruher Instituts für Technologie (KIT) das
Graphzeichnungstool „KaDraw“ entwickelt, welches ab sofort unter einer
General Public License zum Download bereitsteht.
Die Qualitätskriterien für eine lesbare
grafische Darstellung komplexer Beziehungen sind hoch. Beispielsweise
müssen die Knotenpunkte weit genug auseinander liegen, um als solche
erfasst werden zu können. Gleichzeitig muss das Graphzeichnungstool alle
Kanten so anordnen, dass sie für den Betrachter erkennbar bleiben und
nicht willkürlich übereinander liegen. Alle zu beachtenden Kriterien
werden deshalb in einer Zielfunktion formuliert. Um diese zu optimieren
und gleichzeitig die Effizienz bei der Berechnung zu steigern, hat das
Team um Christian Schulz, Henning Meyerhenke und Martin Nöllenburg vom
Institut für Theoretische Informatik am KIT das Graphzeichnungstool
„KaDraw“ entwickelt.
Bei „KaDraw“ kommen zwei Methoden zum
Einsatz. Zum einen bedient man sich der Parallelisierung durch Nutzung
von Mehrkernprozessoren. So kann die Rechenleistung gesteigert werden,
indem die Rechenlast auf mehrere Prozessorkerne verteilt wird. Zum
anderen werden innovative Algorithmen verwendet. Diese Algorithmen
erzeugen aus dem komplexen Eingabegraphen zunächst eine Hierarchie von
immer kleiner werdenden Graphen. Um eine gute Darstellung des
Eingabegraphen zu erhalten, wird zunächst der kleinste Graph gezeichnet.
Die Zeichnung wird danach stückweise auf die größeren Graphen
übertragen und auf jedem größeren Level verbessert. „Mit dieser Methode
können wir den Zeichenvorgang um ein Vielfaches beschleunigen. KaDraw
kann Graphen etwa 30 Mal schneller zeichnen als vorherige Werkzeuge.
Dabei bleibt die Qualität des Ergebnisses immer noch vergleichbar“,
berichtet Christian Schulz.
Doch nicht nur statische Graphen können durch
„KaDraw“ schneller gezeichnet werden. Auch dynamische Graphen, also
Graphen, deren Beziehungen sich im Laufe der Zeit verändern, können mit
dem Karlsruher System deutlich effizienter bearbeitet werden. Ein
Beispiel für dynamische Graphen sind die Freundschaftsbeziehungen in
sozialen Netzwerken. Diese unterliegen – etwa durch hinzukommende
Freundschaften – einer stetigen Veränderung. „Bei dynamischen Graphen
kann man eine bereits vorhandene Zeichnung in unser System eingeben und
daraus ein neues Layout mit neuen Beziehungen zeichnen lassen“, erklärt
Henning Meyerhenke.
Freie Software
Als Nächstes möchten die Wissenschaftler ein
noch effizienteres Verfahren entwickeln. „Durch Verbesserung der
algorithmischen Komplexität möchten wir die Effizienz des Verfahrens
noch weiter steigern“, sagt Martin Nöllenburg. Doch bevor man sich den
neuen Aufgaben widmet, wird „KaDraw“ der Öffentlichkeit zur Verfügung
gestellt. Ab sofort steht das Graphenzeichnungstool unter einer General
Public License (GPL) zur Verfügung. Zeitgleich präsentieren die
Wissenschaftler ihr Tool auf der Fachtagung „Graph Drawing and Network
Visualization“.
Link zum Download von KaDraw: http://algo2.iti.kit.edu/kadraw/
Weiterer Kontakt:
Nils Ehrenberg, Presse, Pressereferent, Tel.: +49 721 608-48122, Fax: +49 721 608-45658, E-Mail: nils.ehrenberg@kit.edu
Das Karlsruher Institut für
Technologie (KIT) vereint als selbständige Körperschaft des öffentlichen
Rechts die Aufgaben einer Universität des Landes Baden-Württemberg und
eines nationalen Forschungszentrums in der Helmholtz-Gemeinschaft. Seine
Kernaufgaben Forschung, Lehre und Innovation verbindet das KIT zu einer
Mission. Mit rund 9 400 Mitarbeiterinnen und Mitarbeitern sowie 24 500
Studierenden ist das KIT eine der großen natur- und
ingenieurwissenschaftlichen Forschungs- und Lehreinrichtungen Europas.