Graphzeichnen

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Graphzeichnen (engl. Graph Drawing) ist ein Themengebiet der Informatik und der Diskreten Mathematik, das sich damit beschäftigt, Graphen geometrisch zu realisieren. Eine zentrale Rolle beim Graphzeichnen bilden Algorithmen, die für einen gegebenen Graphen eine 2-dimensionale Einbettung in den Euklidischen Raum berechnen. Die Knoten des Graphen werden in der Regel durch einfache geometrische Objekte wie Punkte,Kreise, oder Quadrate realisiert. Gibt es eine Kante zwischen zwei Knoten, wird dies in der Zeichnung durch eine Jordan-Kurve dargestellt, welche die den Knoten zugeordneten Objekte verbindet.

Das Graphzeichnen ist in zwei Felder unterteilt: Im statischen Graphzeichnen soll ein Graph dargestellt werden, während im dynamischen Graphzeichnen ganze Sequenzen von Graphen (meist in einer Animation) visualisiert werden sollen.

Ansätze[Bearbeiten]

Im Graphzeichnen gibt es keine universellen Techniken, die einen Graphen zeichnen können. Je nach Anwendungsgebiet sind unterschiedliche Ansätze notwendig, die den jeweilig zu erzielenden Effekt unterstreichen. Die folgenden Erklärungen gelten sowohl für das statische, als auch für das dynamische Graphzeichnen.

Hierarchisches Zeichnen[Bearbeiten]

Hierbei versucht man aus einem gerichteten Graph eine Hierarchie auszulesen und diese dann angemessen darzustellen. Dazu wird die Knotenmenge in Äquivalenzklassen aufgeteilt, so dass Knoten einer Äquivalenzklasse auf einer Höhe gezeichnet werden. Dadurch entsteht eine Zeichnung, die die im Graph vorherrschende Hierarchie herausstellt.

In der Geschäftsprozessmodellierung werden hierarchische Graphen u. a. für Wertschöpfungskettendiagramme oder Organigramme verwendet.

Ausrichtung am längsten Pfad[Bearbeiten]

Dabei wird zwischen allen Start-Knoten (Knoten ohne Vorgänger) und End-Knoten (Knoten ohne Nachfolger) diejenige Kombination ermittelt, bei der der Pfad zwischen Start- und End-Knoten die größte Anzahl dazwischen liegender Knoten aufweist. Dieser längste Pfad wird dann zur Basis für die Ausrichtung aller Knoten und Kanten, wobei die im längsten Pfad liegenden Knoten und Kanten möglichst an einer Gerade ausgerichtet werden die nicht im längsten Pfad liegenden Knoten und Kanten um die Gerade herum angeordnet werden.

In der Geschäftsprozessmodellierung werden am längsten Pfad ausgerichtete Graphen u. a. für EPKs verwendet. Dabei ist die Anwendung von Autolayout-Algorithmen zur Berechnung eines am längsten Pfad ausgerichteten Graphen ein Problem mit erheblichem Entwicklungspotential.

In der Softwaremodellierung kann diese Darstellung in den Notationen BPMN und UML verwendet werden.

Kräftebasiertes Zeichnen[Bearbeiten]

Diesem Ansatz liegt das Modell zugrunde, dass auf alle Knoten Kräfte wirken. Diese Kräfte ergeben sich in diesem Modell durch die Kanten. Anschließend bestimmt man die Gesamtkraft, die auf jeden Knoten wirkt und kann so die Positionen der Knoten in der Zeichnung erhalten. Kanten werden bei diesem Ansatz immer durch gerade Linien repräsentiert[1]. Darüber hinaus können komplexere mathematische oder pseudo-physikalische Modelle für die Berechnung der Kräfte angewandt werden. So können sich z.B. alle Knoten gegenseitig abstoßen (ähnlich einer elektrostatischen Kraft). Knoten können auch mit unterschiedlicher Dichte in einem flüssigen Medium simuliert werden, so dass einzelne Knoten mehr oder weniger Auftrieb erfahren. Auf diese Weise ergeben sich natürlicher anmutendende und oft intuitiver interpretierbare Zeichnungen des Graphen [2].

Skizzenbasiertes Zeichnen[Bearbeiten]

In diesem Fall liegt bereits eine Skizze eines Graphen vor. Daraus wird dann ein Bild für den Graph erzeugt. Diese Methode findet zum Beispiel beim Vereinfachen von Landkarten Anwendung: Bestimmte Orte werden aus der Landkarte herausgefiltert und anschließend werden Straßen zwischen den ausgewählten Orten durch Kanten repräsentiert. In einer Zeichnung dieses Graphen werden dann alle Knoten an die Positionen gezeichnet, an denen sie schon in der Landkarte erschienen. Kanten verlaufen dann (meist als gerade Linien) gegenseitig ausgerichtet. Das resultierende Bild kann zum Beispiel als Anfahrtskizze oder für Busfahrpläne benutzt werden.

Arten von Zeichnungen[Bearbeiten]

Je nach gewünschtem Ergebnis teilt man die Art der Zeichnungen in folgende Klassen ein:

Orthogonale Zeichnung[Bearbeiten]

Orthogonale Verbindung von Knoten eines Graphen

Kanten sind in orthogonalen Zeichnungen immer als Polygonzüge dargestellt, die an Ecken miteinander verbunden sind. Alle Linienzugsegmente verlaufen dabei innerhalb der Zeichnung vertikal oder horizontal, aber nie diagonal. Beispiele sind u.a. Organigramme[3][4].

Spline-Zeichnung[Bearbeiten]

Spline-Verbindung von Knoten eines Graphen

Die Kanten werden hierbei durch geschwungene Linien repräsentiert, die keine Knicke aufweisen. Dies kann zum Beispiel durch den Einsatz von Bezierkurven oder B-Splinekurven erreicht werden.

Beispiele hierzu siehe [5][6]

Anforderungen an Zeichnungen[Bearbeiten]

Die Darstellung eines Graphen sollte auf einen Betrachter auf keinen Fall verwirrend wirken, sondern sollte die besonderen Eigenschaften des zugrundeliegenden Graphen betonen. Dabei ist die Auswahl des Algorithmus zur Berechnung der Darstellung ausschlaggebend. Dieser Algorithmus soll eine möglichst ästhetische Darstellung des Graphen realisieren. Was als möglichst ästhetische Darstellung angesehen wird ist jedoch einerseits vom persönlichen Empfinden des Betrachters und andererseits vom beabsichtigten Zweck der Darstellung abhängig. Es gibt dennoch messbare Kriterien, nach denen die Eignung der Darstellung für einen beabsichtigten Zweck beurteilt werden kann, wie

  • den minimalen Abstand und die minimale Größe der Knoten, beeinflusst durch die Auflösung des darstellenden Gerätes,
  • den maximalen Abstand und die maximale Größe der Knoten, beeinflusst durch die Anzeigefläche des darstellenden Gerätes,
  • die Varianz der Kantenlängen und Knotengrößen (gleiche Größe, am goldenen Schnitt abgestuft, beliebige Größe),
  • die Anzahl der Kantenkreuzungen,
  • die Anzahl der Kantenknicke (bei orthogonalen Kanten) oder Kantenstützpunkte (bei Spline-Kanten),
  • den Abstand benachbarter Knoten zueinander (als Maß für die freie Fläche zwischen zwei Knoten) oder
  • Symmetrien wie horizontale, vertikale, diagonale, radiale Ausrichtung oder gleichartige Strukturen in Teilgraphen.

Eine besondere Eigenschaft von Graphen sind zum Beispiel das Vorhandensein von Quellen (Knoten ohne eingehende Kanten) oder Senken (Knoten ohne ausgehende Kanten). Diese Eigenschaft wird von einem hierarchischen Layoutalgorithmus oder einem Layoutalgorithmus zur Ausrichtung am längsten Pfad besonders hervorgehoben.

Im dynamischen Graphzeichnen ist zusätzlich wichtig, dass aufeinanderfolgende Graphen nicht zu unterschiedlich gezeichnet werden. Knoten, die beispielsweise von einem Graph zum nächsten beibehalten werden, sollten möglichst ihre Position behalten. An dieser Stelle geht man davon aus, dass ein Graph eine sogenannte Mental Map besitzt, die von einem Betrachter meist unterbewusst wahrgenommen wird. Das Ziel ist es nun, die Mental Map über die gesamte Sequenz zu erhalten.

Anwendungen[Bearbeiten]

Graphzeichnen findet Anwendung beim automatischen Anordnen von auf Graphen basierenden Diagrammtypen unterschiedlichster Art, etwa bei der Geschäftsprozessmodellierung oder der Softwaremodellierung. Die Autolayout-Algorithmen zum Erstellen der Zeichnungen finden sich auch in spezialisierten kommerziellen Software-Bibliotheken[7].

Software Anwendungen wie der Diagrammeditor yEd bieten umfangreiche Unterstützung für hierarchisches, kräfte- und skizzenbasiertes Zeichnen und ermöglichen sowohl statisches als auch dynamisches Graphzeichnen.

Einzelnachweise[Bearbeiten]

  1. Force-directed layout (in Englisch)
  2. Found in Space — 3-dimensionale Anzeige für agile semantische Netze
  3. Organigramm
  4. aiSee.com Graphen-Datenbank (in Englisch)
  5. Unix-Evolution
  6. aiSee.com Graphen-Datenbank, Splines Examples (in Englisch)
  7. Graphzeichnen Software-Bibliotheken

Weblinks[Bearbeiten]