Ein Graph ist eine Datenstruktur, die eine Gruppe von Entitäten, so genannten Knoten, darstellt,
die durch eine Reihe von Links verbunden sind.
Ein Knoten kann auch als Scheitelpunkt oder Vertex bezeichnet werden.
Ein Link kann auch als Kante oder Verbindung bezeichnet werden.
In technischen Anwendungen werden Graphen häufig verwendet, um zahlreiche Dinge zu modellieren:
Computernetze, Softwareprogrammstrukturen, Projektmanagementdiagramme usw.
Graphen sind leistungsfähige Modelle, weil sie Anwendungen ermöglichen, die Ergebnisse der Forschung in der
Graphentheorie zu nutzen.
Es sind beispielsweise effiziente Methoden für die Ermittlung des kürzesten Pfads
zwischen zwei Knoten, des Pfads mit den geringsten Kosten usw. verfügbar.
Layout eines Graphen
Das Graphenlayout wird in grafischen Benutzerschnittstellen
von Anwendungen verwendet, die Graphenmodelle anzeigen müssen.
Einen Graphen anzulegen (Layout) bedeutet, den Graphen so zu zeichnen, dass eine angemessene
lesbare Darstellung erzeugt wird.
Im Wesentlichen werden dabei die Position der Knoten und die Form der Links
bestimmt.
Bei einigen Anwendungen sind die Positionen der Knoten bereits bekannt (z. B. anhand der geografischen Positionen der Knoten).
Bei anderen Anwendungen sind die Position nicht bekannt (ein rein "logischer" Graph), oder
die bekannten Positionen, sofern verwendet, erzeugen eine nicht lesbare Zeichnung des Graphen.
In diesen Fällen muss die Position der Knoten berechnet werden.
Was ist mit einer "angemessenen" Zeichnung eines Graphen gemeint?
In technischen Anwendungen muss die Graphenzeichnung häufig bestimmten Qualitätskriterien entsprechen.
Diese Kriterien können je nach Anwendungsfeld oder festgelegtem Darstellungsstandard
variieren.
Es ist häufig schwierig zu sagen, woraus ein gutes Layout besteht.
Jeder Benutzer kann andere, subjektive Kriterien haben, nach denen er ein Layout als "gutes" Layout
einstuft.
Alle Kriterien und Standards haben jedoch ein gemeinsames Ziel: Die Zeichnung muss leicht verständlich
sein und eine einfache Navigation durch die komplexe Struktur des Graphen bieten.
Was ist ein gutes Layout?
Für die verschiedenartigen Anforderungen unterschiedlicher Anwendungen
wurden viele Klassen von Graphenlayoutalgorithmen entwickelt. Ein Layoutalgorithmus
widmet sich je nach Typ des Graphen und den Features des Algorithmus beim Anlegen eines Graphen
einem oder mehreren Qualitätskriterien.
Die gängigsten Kriterien sind im Folgenden beschrieben:
- Minimierung der Anzahl der Linkkreuzungen (siehe link crossing)
- Minimierung des Gesamtbereichs der Zeichnung
- Minimierung der Anzahl der Kurven (in orthogonalen Zeichnungen)
- Maximierung des kleinsten Winkels, der durch aufeinanderfolgende Einfallslinks gebildet wird
- Maximierung der Anzeige von Symmetrien
Wie kann ein Layoutalgorithmus alle diese Qualitätskriterien und Standards der Darstellung erfüllen?
Wenn sich die einzelnen Kriterien ansehen, werden Sie feststellen, dass einige
für zumindest einige Klassen von Graphen leicht zu erfüllen sind.
Für andere Klassen kann es schwierig sein, eine Zeichnung zu erstellen, die den Kriterien entspricht.
So ist beispielsweise die Minimierung der Anzahl an Linkkreuzungen für Baumstrukturen
(d. h. Graphen ohne Zyklen) relativ einfach.
Für allgemeine Graphen hingegen ist die Minimierung der Anzahl der Linkkreuzungen ein
mathematisches "NP-vollständig"-Problem (siehe NP-complete)
(d. h. mit allen bekannten Algorithmen nimmt die erforderliche Zeit für die Ausführung des Layouts
mit der Größe des Graphen schnell zu).
Wenn verschiedene Kriterien gleichzeitig erfüllt werden sollen, ist möglicherweise
keine optimale Lösung für jedes einzelne Kriterium vorhanden, da sich viele Kriterien widersprechen.
Es können zeitaufwendige Kompromisse erforderlich sein.
Außerdem ist es keine leichte Aufgabe, jedem Kriterium eine Gewichtung zuzuordnen.
Die Optimierung mit mehreren Kriterien ist in vielen Fällen für eine Implementierung zu komplex
und viel zu zeitaufwendig.
Aus diesen Gründen basieren Layoutalgorithmen häufig auf heuristischen Verfahren
und bieten unter Umständen nicht optimale Lösungen in Bezug auf ein oder mehrere Kriterien.
Erfreulicherweise liefern die Layoutalgorithmen in technischer Hinsicht häufig einigermaßen lesbare Zeichnungen.
Methoden für die Verwendung von Layoutalgorithmen
Layoutalgorithmen können auf verschiedene Arten in den verschiedenen Anwendungen, in denen sie verwendet
werden, eingesetzt werden.
Die gängigsten Verwendungen eines Algorithmus werden im Folgenden beschrieben:
-
Abgesehen vielleicht von der Auswahl des zu verwendenden Layoutalgorithmus führt der Layoutalgorithmus alle Aktionen ohne Benutzereingriff aus. Manchmal kann ein Regelsatz codiert werden, damit der am besten geeignete Layoutalgorithmus für den jeweiligen anzulegenden Graphen automatisch ausgewählt wird.
-
Der Anwendungsbenutzer hat die Möglichkeit, das Ergebnis der automatischen Layoutprozedur manuell zu verbessern. Manchmal kann der Benutzer Knoten an gewünschte Positionen verschieben und dort "fixieren" und das Layout erneut ausführen. In anderen Fällen wird ein Teil des Graphen automatisch schreibgeschützt, und der Benutzer kann den Rest des Layouts ändern.
- Neues LayoutDer Layoutalgorithmus wird jedesmal, wenn der Graph geändert wird, vollständig wiederholt ("neu").
- Inkrementelles LayoutWenn der Layoutalgorithmus ein zweites Mal für einen geänderten Graphen ausgeführt wird, versucht er, die Stabilität des Layouts soweit wie möglich zu bewahren. Das Layout wird nicht neu ausgeführt. Außerdem versucht der Layoutalgorithmus, CPU-Zeit einzusparen, indem er das vorherige Layout als Anfangslösung verwendet. Einige Layoutalgorithmen und Layoutstile sind von ihrer Spezifik her inkrementell. Bei anderen ist ein inkrementelles Layout unter Umständen nicht möglich.