# Hierarchisches Layout

Die Entwicklung von Algorithmen für hierarchisches Layout ist ein Themengebiet der Informatik und beschäftigt sich mit der Definition von Berechnungsvorschriften zum Layout und Zeichnen hierarchischer Graphen. Die Berechnung des Layouts und das Zeichnen der Graphen kann statisch (das Layout wird in einem Durchlauf berechnet und gezeichnet) oder dynamisch (es wird ein Start-Layout berechnet und in mehreren Durchläufen optimiert und gezeichnet) erfolgen.

## Grundlagen

In seiner reinen Form ist der hierarchische Graph ein gerichteter Graph und hat eine Quelle (Knoten ohne eingehende Kanten) sowie mehrere Senken (Knoten ohne ausgehende Kanten). Die zwischen Quelle und Senke liegenden Knoten können abhängig von ihrer Entfernung von der Quelle in Äquivalenzklassen unterteilt werden.

## Layoutansätze

Um die Charakteristik eines hierarchischen Graphen herauszuarbeiten, bieten sich zwei Ansätze für das Layout, also die Anordnung der Knoten und Kanten des Graphen zueinander, an.

### Eiskristall

Ein hierarchisches Layout als Eiskristall ermöglicht viele unterschiedliche konkrete Ausprägungen bei i. d. R. geringem Flächenverbrauch gegenüber einem Layout als Baum, kann aber keine Ordnung zwischen Knoten derselben Äquivalenzebene darstellen.
Bei diesem Layoutansatz steht die Quelle im Mittelpunkt und alle Knoten einer Äquivalenzklasse haben den gleichen Abstand vom Knoten der übergeordneten Äquivalenzklasse. Die konkrete Ausprägung des Layouts unterscheidet sich einerseits dadurch, ob
* alle Kanten im Graph die gleiche Länge aufweisen,
* alle Kanten zu Knoten einer definierten Äquivalenzebene die gleiche Länge aufweisen, aber alle Kanten zu Knoten der untergeordneten Äquivalenzebene eine andere, untereinander wieder gleiche Länge aufweisen oder
* alle Kanten im Graph eine unterschiedliche Länge aufweisen
und andererseits dadurch, ob
* Knoten einer untergeordneten Äquivalenzebene nur von der Quelle weg angeordnet werden oder
* in jeder beliebigen Richtung angeordnet werden.
Der einfachste statische Algorithmus für Eiskristall-Layout berechnet die Anordnung der Knoten auf konzentrischen Kreisen um die Quelle. Er ermittelt das Gewicht jedes Knotens anhand der Anzahl der mit ihm verbundenen Knoten aller untergeordneten Äquivalenzebenen. Dieses Gewicht ist dann Maß für den Winkel, den der Knoten auf dem seiner Äquivalenzebenen zugeordneten konzentrischen Kreis beansprucht. Sowohl die Berechnung des Gewichts der Knoten als auch das Zeichnen von Knoten und Kanten wird durch rekursive Methodenaufrufe realisiert. Für das Zeichnen muss darüber hinaus ein Startwinkel festgelegt werden.

#### Implementierung

Die folgende Klasse gibt ein Beispiel für die Implementierung einer Node-Klasse in C#, anhand derer man die Funktionsweise gut nachvollziehen kann.
Die folgende Methode gibt ein Beispiel für die Implementierung des vollständigen Zeichnens in C#, wobei die Methoden der Node-Klasse für die Berechnung des Gewichtes und das Zeichnen aufgerufen werden.

### Baum

Ein hierarchisches Layout als Baum ermöglicht die Darstellung einer Ordnung zwischen Knoten derselben Äquivalenzebene (z. B. durch horizontale oder vertikale Anordnung), beansprucht aber i. d. R. mehr Fläche als ein Layout als Eiskristall.
Bei diesem Layoutansatz ist eine Richtung (z. B. von oben nach unten) vorgegeben, in der sich der Graph ausbreitet. Alle Knoten einer Äquivalenzklasse liegen auf derselben Ebene. Die konkrete Ausprägung des Layouts wird gekennzeichnet durch die Entwicklungsrichtung (horizontal oder vertikal) je Äquivalenzebene.
Der einfachste statische Algorithmus für Baum-Layout berechnet die Anordnung der Knoten auf allen Äquivalenzebenen in derselben, z. B. horizontalen, Entwicklungsrichtung. Er ermittelt das Gewicht jedes Knotens anhand der Anzahl der mit ihm verbundenen Knoten aller untergeordneten Äquivalenzebenen. Dieses Gewicht ist dann Maß für den Anteil, den der Knoten auf der seiner Äquivalenzebenen zugeordneten Entwicklungsrichtung beansprucht. Sowohl die Berechnung des Gewichts der Knoten als auch das Zeichnen von Knoten und Kanten wird durch rekursive Methodenaufrufe realisiert.

#### Implementierung

Die folgende Methode gibt ein Beispiel einer Implementierung zur Erweiterung der Node-Klasse in C#, anhand derer man die Funktionsweise gut nachvollziehen kann.
Die folgende Methode gibt ein Beispiel für die Implementierung des vollständigen Zeichnens in C#, wobei die Methoden der Node-Klasse für die Berechnung des Gewichtes und das Zeichnen aufgerufen werden.

### Anwendungen hierarchischer Layouts

Hierarchische Graphen eignen sich zur Darstellung von Strukturen ohne Zyklen (Rückschleifen und Zusammenführung von Teilpfaden) wie:
* Organigrammen
* Funktionsbäumen
* Syntaxbäumen