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
- Workflow Darstellung
- Software Engineering
- Customer Relationship Management
- Konfigurationsmanagement
- Prozessmodellierung
- Datenbankmodellierung
- Bioinformatik
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.