Hierarchisches Layout

Das hierarchische Layoutverfahren hebt die hierarchische Beziehung der Knoten in einem gerichteten Graphen hervor. Dieses Verfahren ist für eine Vielzahl von Anwendungsgebieten ideal geeignet. Hervorzuheben sind

Das hierarchische Layoutverfahren verläft in drei Phasen.

In der ersten Phase werden die Knoten in verschiedene hierarchische Schichten eingeteilt. Dadurch wird auch festgelegt, welche Knoten oberhalb anderer Knoten angeordnet werden.

In der zweiten Phase wird die Reihenfolge der Knoten innerhalb der einzelnen Schichten festgelegt. Hierbei wird typischerweise versucht die Reihenfolge der Knoten so zu wählen, dass sich möglichst wenige Kanten kreuzen.

In der letzten Phase schließlich werden den Kanten und Knoten geometrisch angeordnet.

Reiter 'Anordnung'

Hier befinden sich Optionen für die geometrische Anordnungsphase.

Minimaler Schichtabstand

Legt den minimalen Abstand zwischen Knoten fest, die sich auf benachbarten Schichten befinden.

Minimaler Knotenabstand

Legt den minimalen Abstand zwischen Knoten fest, die benachbart in derselben Schicht liegen.

Minimaler Kantenabstand

Legt den minimalen Abstand zwischen benachbarten Paaren von Kantensegmenten fest. Ebenfalls festgelegt wird durch diese Option der horizontale Mindestabstand zwischen Kantensegmenten und benachbarten Knoten.

Minimale erste Segmentlänge

Legt die minimale Länge des ersten bzw. letzten Kantensegments bei orthogonalem Kantenverlauf fest. Dieser Wert beeinflusst den Mindestabstand des ersten beziehungsweise letzten Kantenknicks vom Schnittpunkt der Kante mit dem Knoten.

Maximale Dauer (sec)

Legt die maximale Dauer der Layoutberechnung fest. Es ist zu beachten, dass die angegebene Dauer nicht immer eingehalten werden kann. Dies ist beispielsweise der Fall, wenn wesentliche Teile der Berechnung noch nicht abgeschlossen sind.

In der Regel verbessert sich das Resultat der Berechung durch Angabe eines höheren Werts. Ebenfalls zu beachten ist, dass die angegebene Dauer von dem Verfahren auch tatsächlich ausgeschöpft wird.

Orientierung

Legt die Hauptrichtung des Layouts fest. Das Verfahren versucht dabei die Knoten so anzuordnen, dass möglichst viele Kanten in diese Hauptrichtung zeigen.

Oben nach unten
Die Hauptrichtung des Layouts verläuft von oben nach unten.
Unten nach oben
Die Hauptrichtung des Layouts verläuft von unten nach oben.
Links nach rechts
Die Hauptrichtung des Layouts verläuft von links nach rechts.
Rechts nach links
Die Hauptrichtung des Layouts verläuft von rechts nach links.

Knotenplatzierung

Beeinflusst den horizontalen Abstand zwischen Knoten, sowie die Länge der linearen Segmente der Kantenzüge.

Lineare Segmente
Knoten werden so platziert, das Kantenzüge möglichst lange vertikale Segmente mit wenigen Knicken bilden können. Diese Verfahren bietet sich im Besonderen im Zusammenhang mit der Option orthogonale Kantenführung an. Als Nachteil dieses Verfahrens ist die relative geringe horizontale Kompaktheit zu nennen.
Liniensegmente
Knoten werden kompakte in den Schichten angeordnet, so dass dies möglichst schmal bleiben. Nachteilig ist bei diesem Stil, dass die Kantenzüge sehr viele Knicke bekommen können.
Pendel
Eine effektive Kombination aus den Verfahren Lineare Segmente und Liniensegmente
Simplex
Erzeugt Anordnungen hoher Qualität. Ähnlich wie bei dem Verfahren Lineare Segmente werden wenige Knicke für Kantenzüge erzeugt. Zusätzlich sind die Resultate horizontal kompakter und balancierter. Nachteil dieses Verfahrens ist seine relativ hohe Berechnungsdauer.
Median Simplex
Basierend auf Simplex erzeugt auch diese Einstellung Anordnungen hoher Qualität. Im Unterschied zu diesem versucht dieser Stil, wenn der Platz vorhanden ist, symmetrischere Bilder zu erzeugen. Dafür werden auch wenige zusätzliche Knicke in Kauf genommen.
Baumartig
Erzeugt perfekte Darstellungen für Baumstrukturen. Für Nicht-Baumstrukturen wird das Verfahren Lineare Segmente angewendet.

Kantenführung

Linienzug
Kantenzüge sind geradlinig oder werden aus mehreren Segmenten zusammengesetzt.
Orthogonal
Kantenzüge bestehen lediglich aus vertikalen und horizontalen Segmenten. Alle Kanten knicken in rechten Winkeln ab. Durch diese Variante der Kantenführung erhöht sich möglicherweise der Abstand zwischen benachbarten Knotenschichten.

Rückwärtskanten

Bei Aktivierung werden Kanten, die nicht in die Hauptrichtung des Layouts weisen, als Rückwärtsschleifen gezeichnet. Rückwärtsschleifen beginnen auf der Unterseite ihres Quellknotens, drehen dann um 180 Grad, führen dann nach oben und enden schließlich an der oberen Kante ihres Zielknotens.

Nur selektierte Elemente

Schränkt die Berechung auf markierte Knoten und auf Kanten die mit markierten Knoten verbunden sind, ein.

Reiter 'Schichtzuweisung'

Das hierarchisches Layoutverfahren ordnet jeden Knoten einer horizontal verlaufenden Schicht von Knoten zu. Schichten werden untereinander angeordnet. Der Rank eines Knotens bezeichnet dabei die Nummer der Schicht, in der sich Knoten befindet. Knoten der obersten Schicht haben beispielsweise den höchsten Rang.

Die Standardschichtzuweisung folgt der Strategie Topologisch. Dabei werden die Knoten so in Schichten eingeteilt, dass ein Knoten einen höheren Rang erhält als alle seine Nachfolger. Eine solche Schichteneinteilung ist bei azyklischen Graphen immer möglich.

Strategie

Topologisch (maximaler Rang)
Topologische Variante. Alle Knoten, die keine Vorgänger besitzen, erhalten denselben, höchstmöglichen Rank.
Topologisch (optimal)
Topologische Variante. Der Betrag der Differenz zwischen Quell- und Zielknoten einer Kante wird als Kantenlänge bezeichnet. Diese Strategie wählt die topologische Schichtzuweisung so, dass die Summe aller Kantenlängen minimiert wird.
Topologisch (heuristisch)
Eine schnelle und gute Heuristik, die versucht ebenfalls die Summe der Kantenlängen zu minimieren.
Topologisch (Knotenabsenkung)
Sehr schnelle, aber weniger effektive Heuristik als Topologisch (heuristisch)
Koordinatenabhängig
Diese Strategie benutzt die initialen y-Koordinaten der Knoten um die Schichteneinteilung vorzunehmen. Die resultierende Schichteneinteilung wird dabei ähnlich sein, wie in der Eingabe vorgegeben wird. Es ist auch möglich, dass durch dieses Verfahren miteinander verbundene Knoten in dieselbe Schicht gelegt werden. Die Kanten zwischen Knoten derselben Schicht werden dabei immer orthogonal gezeichnet.
Breitensuche
Basiert auf einer Breitensuche, deren Startmenge vom Benutzer festgelegt werden kann. Miteinander verbunden Knoten werden dabei maximal eine Schicht auseinander liegen. Wie bei dem Verfahren Koordinatenabhängig ist es erlaubt, dass miteinander verbundene Knoten derselben Schicht angehöhren können. Der Benutzer kann bei diesem Verfahren die Menge der Knoten, die der obersten Schicht angehöhren sollen, markieren. Sind keine Knoten markiert, so werden die Knoten ohne Vorgänger in die oberste Schicht gelegt.

Reiter 'Knotenreihenfolge'

Die Optionen in diesem Reiter beeinflussen die Reihenfolge der Knoten in den einzelnen Schichten. Es wird dabei versucht, die Reihenfolge der Knoten so zu wählen, dass wenige Kantenkreuzungen entstehen.

Gewichtungsheuristik

Strategie zur Verminderung der Kreuzungszahl von Kanten. Welche der verfügbaren Verfahren besser ist, hängt dabei von der Struktur des Eingabegraphen ab.

Baryzentrum
Setzt die Baryzentrum Methode ein.
Median
Setzt die Median Methode ein.

Vertauschung benutzen

Nachbearbeitungsschritt der die Kreuzungszahl von Kanten durch Vertauschung benachbarter Knoten weiter reduziert. Dieser Schritt kann sehr zeitintensiv sein.

Pseudokreuzungen entfernen

Nachbearbeitungsschritt der die Knoten so umordnet, dass keine Pseudokreuzungen mehr auftreten. Als Pseudokreuzung wird eine Kreuzung zweier Kanten bezeichnet, die einen gemeinsamen Endknoten haben.

Randomisierungsrunden

Diese Einstellungen gibt die maximale Zahl der Berechnungsversuche an, die durch zufällige Umordnung gestartet werden sollen. Eine hohe Zahl kann zu weniger Kreuzungen und längerer Laufzeit führen. Für große kreuzungsreiche Diagramme empfiehlt sich eine niederigere Einstellung.

Reiter 'Beschriftung'

Dieser Reiter bietet Optionen zur Steuerung der automatischen Anordnung von Kantenbeschriftungen.

Kantenbeschriftung

Aus
Beschriftungen werden nicht automatisch angeordnet.
Hierarchisch
Kantenbeschriftungen werden während des gesamten Layoutprozesses berücksichtigt. Es wird bei der Platzierung der Knoten und Kanten darauf geachtet, dass die Kantenbeschriftungen ebenfalls überlappungsfrei angeordnet werden können.
Generisch
Kantenbeschriftungen werden automatisch angeordnet, nachdem der Layouter die Knoten und Kanten bereits platziert hat. Bei dieser Vorgehensweise wird kein zusätzlicher Platz benötigt. Allerdings kann es zu Überlappungen zwischen Beschriftungen und anderen Objekten kommen.

Kantenbeschriftungsmodell

Ein Modell bestimmt die möglichen Positionen der Kantenbeschriftungen. Folgende Modelle stehen zur Auswahl:

Beste
Der Standardwert. Es wird ein Modell gewählt, das am Besten zum Beschriftungsalgorithmus passt.
Wie bisher
Nutzt die bereits gesetzten Beschriftungsmodelle. Modelle für Kantenbeschriftungen können dabei mittels der Einstellungsdialoge für Kanten und Kantenbeschriftungen individuell zugewiesen werden.
Mittig
Erlaubt Positionen, die sich auf dem Pfad der jeweiligen Kante befinden. Dieses Modell ist eine gute Wahl für die Beschriftungsmethoden Generisch und Hierarchisch.
Seitlich
Erlaubt Positionen, die sich auf beiden Seiten des Pfades der jeweiligen Kante befinden. Dieses Modell ist eine gute Wahl für die Beschriftungsmethode Generisch.
Unbeschränkt
Erlaubt alle Positionen. Diese Option ist eine gute Wahl für die Beschriftungsmethode Hierarchisch. Für die Beschriftungsmethode Generisch kann dieses Modell nicht benutzt werden.

Reiter Gruppierung

Auf diesem Reiter kann das Verhalten des Algorithmus bei der Anwendung auf verschachtelten/gruppierten Graphen eingestellt werden.

Layoutverfahren für Gruppen

Bestimmt den grundsätzlichen Ansatz des Algorithmus.
Gruppen neu anordnen
Der Algorithmus ordnet die Gruppen und Knoten rekursiv neu an. Alle Positionen von direkt sichtbaren Knoten werden neu berechnet.
Knoteninhalt festhalten
Der Algorithmus behält die relative Lage der Knoten zueinander innerhalb von Gruppenknoten bei. Die Neuanordnung findet nur auf der obersten Knotenebene statt. Kanten, die in Gruppenknoten hineinfüren werden im nachhinein neu verlegt.
Gruppen ignorieren
Diese Einstellung bewirkt, dass der Algorithmus Gruppenknoten und adjazente Kanten an diesen vollständig ignoriert. Dies kann zu Überlappungen von Kanten und Überlappungen mit Gruppenknoten in der endültigen Zeichnung führen.

Globale Sequenzierung verwenden

Diese Einstellung kann verwendet werden, um einen alternativen Sequenzierungsalgorithmus zur Berechnung der Knotenreihenfolge zu aktivieren. Dieser Algorithmus erzeugt tendenziell bessere Ergebnisse bei komplex geschachtelten Gruppenknoten, kann aber in manchen Fällen lokal mehr Kreuzungen erzeugen als der Standardalgorithmus.