© Anton Balazh, 123rf.com

Egal ob Netzwerke, Community-Beziehungen, Stammbäume oder Straßenkarten – die Werkzeuge Aisee, Gephi, Graphtea und Tulip versprechen beliebige Graphen anschaulich zu präsentieren. Ihr Funktionsumfang unterscheidet sich jedoch deutlich voneinander.

Wer die kürzeste Autobahnverbindung zwischen Dortmund und München sucht, der kann die Städte als Punkte und die Straßen zwischen ihnen als Verbindungslinien aufmalen. Mathematik und Informatik bezeichnen solch ein Gebilde allgemein als Graph. Die Punkte heißen Knoten, und die sind wiederum über Kanten miteinander verbunden. Graphen repräsentieren nicht nur Straßenkarten, sondern auch Rohrleitungssysteme, Netzwerktopologien, Beziehungen in einem sozialen Netzwerk oder die Abhängigkeiten von Softwarepaketen.

Es gibt unzählige Algorithmen, um schnell wichtige Informationen aus Graphen zu extrahieren – etwa den kürzesten Weg zwischen Dortmund und München, die maximale Wassermenge, die durch einen Kanal fließen kann, oder eine Liste mit Softwarepaketen, die das Malprogramm Gimp verlangt.

Die meisten Werkzeuge spezialisieren sich auf ein bestimmtes Anwendungsgebiet, während die Testkandidaten dieser Bitparade beliebige Graphen anzeigen, verändern und analysieren. Aisee [1], Gephi [2], Graphtea [3] und Tulip [4] sind als Allrounder besonders geeignet, um schnell etwas zu visualisieren oder einen Graphen in eine Bilddatei umzuwandeln. Die Tools können auch mit Graphen umgehen, die ein Skript oder ein anderes externes Programm erzeugt hat, etwa mit einem von einem Debugger aufgezeichneten Kontrollfluss.

Als Datei-Austauschformat hat sich weitgehend das XML-basierte Graph ML [5] durchgesetzt, der Nachfolger der Graph Modelling Language (GML, [6]). Aus der Reihe tanzt lediglich der erste Kandidat: Aisee verwendet die Graph Description Language (GDL, [7]). Die Tester untersuchten neben den Im- und Exportformaten auch die Darstellungsformen und Zeichenalgorithmen und ob die Programme Teile des Graphen zu Subgraphen zusammenfassen und diese ein- und ausblenden können. Sie überprüften ebenfalls, ob Analysealgorithmen aus unterschiedlichen Bereichen vorhanden sind, um beispielsweise den kürzesten Weg zwischen zwei Knoten zu ermitteln.

Als Testsystem diente dafür Ubuntu 12.10 mit 4 GByte Hauptspeicher, der Java-Laufzeitumgebung von Oracle (Java 7, Revision 21) und einer Nvidia-Grafikkarte, die der proprietäre Treiber ansteuerte.

Aisee

Der erste Testkandidat stammt aus der Saarbrücker Softwareschmiede Absint Angewandte Informatik GmbH. Aisee [1] steht unter einer proprietären Lizenz und ist für nicht-kommerzielle Zwecke kostenlos erhältlich. Eine Einzelplatzlizenz für kommerzielle Zwecke kostet knapp 400 Euro; Rabatte gibt es bei der Abnahme mehrerer Lizenzen und im akademischen Umfeld.

Im Downloadbereich der Homepage finden Anwender Binaries für Windows, OS  X und Linux (32 und 64 Bit). Nach dem Auspacken des Tar.gz-Archivs übernimmt ein Installationsprogramm die Einrichtung. Im Test trat die Version 3.0.12 vom April 2010 an.

Aisee ist primär zur Visualisierung von Graphen gedacht, Benutzer können über das GUI weder Knoten anlegen noch löschen. Dies passiert ausschließlich in Quellen, also in den GDL-Dateien. Über die Maximalgröße von Graphen schweigt sich der Hersteller aus; das Programm sei “selbst für riesige Graphen mit Tausenden von Knoten” geeignet. Die getestete Version bietet nur fünf Layoutmethoden, die Anwender umständlich in einem separaten Dialog auswählen und einstellen.

Gute Aussicht

Über das Menü »View« erreichen Nutzer verschiedene Ansichtsmodi. In der so genannten »Pan View« fährt Aisee aus der Detaildarstellung heraus, blendet den gesamten Graphen ein und hebt den vorher betrachteten Ausschnitt hervor (siehe Abbildung 1). Mit der Maus verschieben Anwender den Bereich und springen so schnell zu einer anderen Stelle. Außerdem dürfen sie Lesezeichen setzen, um schneller zwischen den Knoten hin und her zu springen.

Abbildung 1: Die Pan View hebt Ausschnitte hervor, was bei der Orientierung und schnellen Navigation innerhalb großer Graphen hilft.

Zudem ist es möglich, die direkten Nachbarn eines Knotens anzuzeigen (Abbildung 2) und über die Liste direkt anzusteuern. Die Suche spürt einzelne Knoten über reguläre Ausdrücke auf und blendet auf Wunsch alle nicht zu den Suchkriterien passenden Knoten aus.

Abbildung 2: Aisee listet direkte Nachbarn in einem Dialog auf und erlaubt es, diese gezielt anzuspringen.

Die Knoten malt das Programm mit vom Benutzer vorgegebenen Bitmaps. Kanten weisen sie frei wählbaren Klassen zu, Aisee blendet diese dann abhängig von der Klasse aus und ein. Subgraphen kann das Tool rekursiv verschachteln. All dies muss die bereits erwähnte GDL-Datei vorgeben. Die Benutzeroberfläche bietet keine Funktionen, um Knoten einen anderen Look zu verpassen oder Kanten einer neuen Klasse zuzuordnen.

Aisee exportiert wahlweise den kompletten Graphen oder Teile davon. Optional dürfen Nutzer dies auf der Kommandozeile ohne Umweg über das GUI erledigen. So wandelt der folgende Aufruf den Graphen direkt in eine PNG-Datei um:

aisee test.gdl --export test.png

Das Programm bietet ebenfalls einen Servermodus. Beim Aufruf über »aisee –server« geben Anwender eine Portnummer an und steuern das Programm fortan über einfache Textkommandos.

Gephi

Der zweite Kandidat steht unter der GPLv3 und der CDDL 1.0: Gephi [2] ist in Java geschrieben und benötigt eine Laufzeitumgebung in Version 6 oder neuer. Oracles Java-Software ist unbedingt erforderlich, denn Gephi arbeitet nicht mit dem Open JDK zusammen. Darüber hinaus verlangt das Graph-Visualisierungstool noch Open GL.

Die Tester schauten sich Version 0.8.2 beta an, die unter Linux, Windows und OS  X Graphen visualisiert. Linuxer, die den Quellcode nicht selbst übersetzen möchten, laden ein Tar.gz-Archiv mit einem vorkompilierten Binary herunter, entpacken es und starten das Programm aus dem Verzeichnis »bin« .

Die Benutzeroberfläche wirkt auf den ersten Blick etwas überladen, da Gephi alle Funktionen und Daten in einem Fenster versammelt. Einsteiger sollten daher einen Blick ins Gephi-Wiki [8] werfen, das ausführliche Anleitungen, Tipps und Tricks enthält. Zudem lohnt sich ein Besuch im Gephi-Marketplace [9], der zahlreiche Plugins feilbietet, mit denen Anwender den Funktionsumfang erweitern. Das Repository für die Erweiterungen zapfen sie auch direkt aus Gephi heraus bequem an.

Gephi nutzt zum Darstellen der Graphen die Open-GL-Schnittstelle und somit die 3-D-Fähigkeiten der Grafikkarte. Knoten dürfen Anwender zwar frei im Raum anordnen, aber lediglich das ganze Gebilde kippen und es nicht frei drehen (siehe Abbildung 3). Das Java-Programm visualisiert bis zu 50 000 Knoten und eine Millionen Kanten. Um in solch gigantischen Objekten den Überblick zu behalten, blendet Gephi nicht markierte Teile des Graphen dezent aus.

Abbildung 3: Obwohl Gephi eine korrekte 3-D-Ansicht zeigt, dürfen Nutzer den Graphen nur in der Horizontalen kippen.

Die Navigation ist etwas gewöhnungsbedürftig: Mit dem Mausrad vergrößern und verkleinern Nutzer die Darstellung, mit gedrückter rechter Maustaste verschieben sie den Ausschnitt. Die Kantengröße stellen sie bequem über einen Regler ein, für die Knoten gibt es jedoch kein Pendant. Eine Drehung des Graphen findet nur in 90-Grad-Schritten statt. Dazu wenden Benutzer den entsprechenden Rotations-Algorithmus auf ihn an. Layout-Algorithmen müssen sie explizit starten und können dann die Einstellungen in Echtzeit so lange verändern, bis die Anzeige stimmt.

Filter sorgen für mehr Überblick und zeigen nur noch Knoten und Kanten an, die eine vom Anwender festgelegte Bedingung erfüllen. So blendet Gephi beispielsweise auf Wunsch alle Knoten aus, die weniger als zwei Kanten besitzen. Die gefilterte Ansicht überführt Gephi zudem in einen neuen Graphen und reduziert so die Datenmenge. Den gerade sichtbaren Ausschnitt speichert eine eingebaute Screenshot-Funktion.

Anders als bei Aisee dürfen Benutzer in Gephi selbst Knoten und Kanten hinzufügen beziehungsweise bestehende verändern, ohne den Quelltext im Editor anzufassen. Für jede Operation existiert ein eigenes Werkzeug. Zusätzlich gibt es gleich mehrere Färbe- und Auswahlwerkzeuge. Punktabzug gibt es hier für die fehlende Undo-Funktion.

Gephi bietet viele Metriken und Statistiken an. So berechnet das Tool etwa den Durchmesser des Graphen (Diameter), zählt die Zusammenhangskomponenten oder ermittelt die durchschnittliche Länge aller kürzesten Pfade. Die Ergebnisse sichert es als HTML-Seiten.

Um den kürzesten Weg zwischen zwei Knoten zu ermitteln, steht ein Spezialwerkzeug bereit, das den Pfad zusätzlich grafisch hervorhebt. Das Heatmap-Werkzeug errechnet zum angeklickten Knoten alle kürzesten Wege und färbt näher liegende Knoten dunkler ein. Alle in den Knoten und Kanten gespeicherten Werte lassen sich in der Data-Laboratory-Ansicht nachschlagen und dort auch verändern (siehe Abbildung 4).

Abbildung 4: Die Data-Laboratory-Ansicht von Gephi zeigt alle Eigenschaften der Knoten und Kanten in einer Tabelle an.

Farbrausch

Gephi malt Knoten und Kanten auch abhängig von den gespeicherten Werten an. So erscheinen etwa alle Knoten für Städte mit über 300 000 Einwohnern rot, alle kleineren dagegen grün. Die Abstufungen sind frei wählbar: Je dichter eine Stadt zum Beispiel an die 300 000 Einwohner herankommt, desto dunkler ist das Grün.

Einige Algorithmen hinterlegen an den Knoten und Kanten eigene Werte, die Benutzer als Grundlage fürs Einfärben definieren. Die Berechnung aller kürzesten Pfade liefert für jeden Knoten auch die Information, wie zentral die entsprechende Stadt liegt. Wählen Nutzer auf dieser Basis beispielsweise ein Rot, stechen die besonders zentralen Städte leuchtend rot hervor.

Neben Subgraphen kann Gephi über die Louvain-Methode Cluster bilden, um etwa Communities in großen Netzwerken darzustellen. Das Visualisierungstool kann Graphen auch anhand der Knoten- und Kantenattribute in Partitionen einteilen. So identifizieren Anwender etwa Ballungsräume in Straßenkarten und heben sie farblich hervor. Wie viele Städte welchen Ballungsräumen angehören, zeigt zudem ein Tortendiagramm.

Veränderungen eines Graphen im Laufe der Zeit präsentiert und analysiert Gephi ebenfalls (Dynamic Network Analysis, DNA). Auf diese Weise verfolgt das Tool zum Beispiel veränderte Beziehungen in sozialen Netzwerken. Es bietet dazu eigens eine Zeitleiste, über die Benutzer gezielt Punkte ansteuern. Die Daten erwartet Gephi im extra für solche Zwecke geschaffenen GEXF-Format. Das erwähnte Plugin-Repository stellt Erweiterungen bereit, mit denen Nutzer solche Daten zu Gephi streamen können.

Gut gefällt die Vorschaufunktion beim Exportieren in andere Formate, sie ermöglicht es Anwendern, noch einmal Hand anzulegen, die Optik oder die Farben zu verändern. Alle hier gemachten Einstellungen speichert das Programm auf Wunsch als Vorlage.

Graphtea

Auch der dritte Kandidat läuft als Java-Programm unter Windows, OS  X und Linux. Graphtea [3] steht unter der GPLv2. Zu den Installationsvoraussetzungen schweigen sich die Macher aus. Die Version vom 6. Mai 2013 aus dem Git-Masterbranch arbeitete klaglos mit Oracles Java 7, Revision 21, zusammen. Das früher als Graphlab bekannte Programm soll laut Homepage vor allem beim Lehren und Studieren der Graphentheorie helfen. Wer nicht die neueste Version aus dem Git-Repository testen möchte, der findet auf der Projektseite ein Archiv mit einer vorkompilierten Fassung. Auch wenn der letzte Eintrag in den Readme-Dateien vom März 2012 ist, läuft die Entwicklung auf vollen Touren.

Wie in einem Malprogramm klicken Anwender ihre Graphen zusammen. Dabei erhalten sie Unterstützung von einem Assistenten, der fertige Graphen zufällig oder nach einem bestimmten Schema auf die Zeichenfläche bringt. So ziehen Nutzer mit nur zwei Mausklicks einen kompletten binären Baum auf. Für besonders große Objekte eignet sich Graphtea nicht, denn schon bei kleineren Modellen mit über 100 Kanten bricht die Verarbeitungsgeschwindigkeit spürbar ein. Zudem bietet das Tool keine Undo-Funktion.

Über den Bereich »Properties« , den Nutzer am linken Rand auf- und zuklappen, weisen sie markierten Knoten und Kanten Farben zu, versehen sie mit einer Beschriftung, verändern die Größe oder verschieben sie an eine neue Position. Knoten dürfen unterschiedliche Formen annehmen (Kreis, Rechteck, verschiedene Sterne und so weiter), für Kanten wählt der Benutzer die Breite und eine Pfeilspitze, bei den Beschriftungen einen Font und die Größe.

Schrittweise

Auf Wunsch fertigt Graphtea verschiedene Statistiken (Reports) an und verrät etwa die Anzahl der Zusammenhangskomponenten oder der gebildeten Dreiecke. Je nach Report erscheinen die Ergebnisse in einem eigenen Fenster, als Beschriftungen an den Knoten und Kanten oder als Farben. Einfluss darauf hat der Anwender allerdings kaum. Statistiken, die nur einen Wert liefern, etwa die Anzahl der Knoten und Kanten, erscheinen im Hauptfenster übersichtlich in einem eigenen Bereich zusammengefasst (siehe Abbildung 5). Ein Mausklick genügt, um einen Wert zu berechnen.

Abbildung 5: Am linken Rand blendet Graphtea die Eigenschaften sowie statistische Informationen zum Graphen ein.

Dass Graphtea für Studium und Lehre gedacht ist, merken Anwender spätestens dann, wenn sie einen Algorithmus wie die Breitensuche oder Kruskal starten. Deren Ablauf visualisiert das Programm, indem es die gerade behandelten Knoten und Kanten farblich hervorhebt (siehe Abbildung 6). Darüber hinaus kann es die Berechnung pausieren und die Ablaufgeschwindigkeit verändern. Die einzelnen Arbeitsschritte protokolliert zudem ein Textfenster.

Abbildung 6: Anwender können in Graphtea Algorithmen Schritt für Schritt nachvollziehen – hier eine Breitensuche.

Java-Programmierer erweitern den Funktionsumfang mit eigenen Erweiterungen. Auch diese können die schrittweise Ausführung nutzen, sofern der Entwickler im Java-Code die entsprechenden Funktionen aufgerufen hat. Graphtea exportiert seine Graphen nicht nur ins PNG-Format und als Textdatei, sondern erstellt auch direkt Latex-Dokumente – ein echter Gewinn für Benutzer, die wissenschaftliche Arbeiten erstellen.

Tulip

Der vierte und letzte Kandidat liegt allen großen Distributionen als Paket bei. Wer die neueste Tulip-Version einsetzen möchte, der sollte den Quellcode von der Projektseite [4] herunterladen und selbst kompilieren. Die Tester schauten sich Tulip 4.2 an, das unter der LGPLv3 steht und genau wie die anderen vorgestellten Programme unter Windows, OS  X und Linux läuft.

Ähnlich wie Gephi sieht sich Tulip als Framework, das Anwender über selbst geschriebene Erweiterungen an die eigenen Bedürfnisse anpassen. Es setzt allerdings nicht auf Java, sondern auf C++ und Qt, was für eine flottere Verarbeitungsgeschwindigkeit sorgt. Das macht sich vor allem bei großen Graphen und rechenintensiven Algorithmen bemerkbar. Wer lieber in Python als in C++ programmiert, der darf Python-Skripte schreiben, für die Tulip in der Benutzeroberfläche sogar eine kleine Entwicklungsumgebung bereitstellt. Die Projektseite führt zu einem Plugin-Repository, das derzeit allerdings nur die bereits enthaltenen Erweiterungen vorhält und aktualisiert.

Tulip nutzt die 3-D-Fähigkeiten der Grafikkarte via Open GL und soll nach Angaben seiner Macher Graphen mit über zehn Millionen Elementen verwalten und anzeigen können. Der tatsächliche Wert hängt von der Hardware und deren Speicher ab. Anders als Gephi dürfen Benutzer nicht nur die Knoten und Kanten im dreidimensionalen Raum anordnen, sondern auch den Graphen grenzenlos um alle Achsen drehen. Das erlaubt ganz neue Einsichten.

Tulips Hauptfenster wirkt etwas überladen. Am linken Rand finden Anwender eine gut sortierte Liste aller verfügbaren 39 Layout-Algorithmen. Im rechten Bereich des Hauptfensters darf der Anwender verschiedene Ansichten auf den Graphen einblenden, die so genannten Panels (siehe Abbildung 7). Hier steht sogar eine Darstellung der Adjazensmatrix zur Verfügung – Tulip ist der einzige Kandidat, der dies anbietet. Die Ansichten dürfen neben-, über- oder untereinander liegen, je nachdem, was der Monitor hergibt.

Abbildung 7: Tulip auf einem breiten Monitor: Links steht die Liste mit den Algorithmen, in der Mitte eine Tabelle, rechts ein Ausschnitt des Graphen.

Die Bedienung der Graphen-Ansicht ähnelt der von Gephi: Das Mausrad zoomt heran, den Ausschnitt verschiebt der Anwender bei gedrückter linker Maustaste. Zusätzlich steht hier eine kleine Übersichtskarte bereit, auf der Nutzer den Ausschnitt direkt verschieben. Eine Lupe und ein Fischauge heben gezielt Bereiche hervor. Genau wie Gephi gibt es in Tulip ein Werkzeug, das mit nur zwei Mausklicks den kürzesten Pfad zwischen zwei Knoten markiert. Da das Programm die Knoten in der Voreinstellung als kleine Punkte zeichnet, wirkt das Ganze zwar übersichtlich, wird aber beim Bearbeiten zu einer ziemlichen Fummelei.

Malwerkzeuge sind auch enthalten, um Graphen zu erstellen und zu verändern. Auf Wunsch generiert Tulip Graphen per Zufall, es fehlen jedoch Vorlagen für häufig auftretende Formen. Wer beispielsweise einen sternförmigen Graphen benötigt, der muss ihn mühsam selbst zusammenklicken. Dafür punktet Tulip mit anderen Automatismen und erstellt beispielsweise automatisch Graphen aus der Verzeichnisstruktur der Festplatte (siehe Abbildung 8), aus den Links einer Webseite oder den Freundschaftsbeziehungen aus Facebook.

Abbildung 8: Das Dateisystem als Graph: Tulip hat einige Automatismen an Bord, die lokale Festplatten, Webseiten und sogar Facebook einbeziehen.

Mehrwertspeicher

Knoten und Kanten färben Anwender von Hand oder abhängig von den gespeicherten Werten ein. Auch die Algorithmen beeinflussen die Farbgebung und stellen so ihre Ergebnisse dar. Dabei gilt es zu beachten, dass Knoten und Kanten bestimmte Eigenschaften besitzen, etwa Farbe oder Beschriftung. Die von einem Algorithmus berechneten Ergebnisse müssen Anwender explizit diesen Eigenschaften zuweisen.

Wer die berechneten Werte nur speichern möchte, muss zunächst dem Knoten oder der Kante eine neue Eigenschaft hinzufügen. Das ist umständlich: Nutzer öffnen dazu das unscheinbare Register »Properties« , klicken mit der rechten Maustaste auf die Liste und wählen »New« . Die Tester entdeckten dieses Versteck erst nach etlichen Experimenten.

Nach dem gleichen Prinzip arbeitet die Suchfunktion, die gleichzeitig als Filter dient. Zunächst stellt der Anwender – basierend auf den vorhandenen Eigenschaften – die gewünschten Kriterien ein und fordert Tulip dann auf, alle davon betroffenen Knoten oder Kanten zu markieren. Da die Suche so fest mit den Eigenschaften verbunden ist, kann Tulip nicht einfach alle Knoten mit mehr als drei Kanten aufspüren.

Es ist möglich, Teile des Graphen zu Subgraphen zusammenzufassen. Wie diese zusammenhängen und ineinander verschachtelt sind, zeigt Tulip in einer Hierarchie an. Die Subgraphen behandelt das Programm wie eigene Graphen – so lassen sie sich in einem eigenen Panel anzeigen und manipulieren.

Beim Export enttäuschte Tulip zunächst. Als Formate bietet das Programm lediglich das eigene und GML an; Bildformate fehlen. Einen Ausweg fanden die Tester über die Screenshot-Funktion. Diese legt den gerade angezeigten Ausschnitt als Grafikdatei ab.

Sehenswürdig

Alle Programme erfordern entsprechendes Hintergrundwissen. Der Nutzer muss selbst entscheiden, welche der angebotenen Algorithmen in welchem Fall sinnvoll sind. So können Flussalgorithmen nicht nur die maximale Wassermenge liefern, sondern unter Umständen auch den maximalen Datendurchsatz in einem Computernetzwerk ermitteln.

Auch bei der Interpretation der Ergebnisse ist der Nutzer auf sich gestellt: Was der minimale Spannbaum aussagt, hängt vom vorliegenden Graphen ab. Die Dokumentation der Testkandidaten schwankt zwischen nicht vorhanden (Graphtea), deutlich veraltet (Tulip), nicht ganz auf dem aktuellen Stand (Gephi) und gut lesbar (Aisee).

Für Aisee sprechen die einfache Bedienung und der Betrieb als Server. In allen anderen Bereichen läuft das Programm der Konkurrenz hinterher. Die größte Hürde dürfte das eigene Dateiformat sein, in das Benutzer zunächst ihre Graphen konvertieren müssen. Graphtea richtet sich vor allem an Lernende und Lehrende. Während der Export nach Latex überzeugt, sind die mitgelieferten Algorithmen von unterschiedlicher Qualität.

Den größten Funktionsumfang bieten Gephi und Tulip. Zu welchem der Werkzeuge der Anwender greift, hängt von den eigenen Bedürfnissen, der verwendeten Programmiersprache und den Vorlieben ab. Gephi basiert auf Java und ist somit portabel, Tulip ist in C++ geschrieben und bei fast allen Distributionen dabei. Beide Tools erfordern allerdings eine gewisse Einarbeitungszeit, und es dauert, bis sich Einsteiger in den Benutzeroberflächen zurechtfinden.