Merkmale und Einschränkungen des Baumstrukturlayouts

Merkmale

  • Berücksichtigt die Größe der Knoten so, dass keine Überschneidungen vorkommen.
  • Formt die Links optional um, um ihnen eine orthogonale (rechtwinklige) Form zu geben (abwechselnd horizontale und vertikale Liniensegmente).
  • Unterstützt verschiedene Layoutmodi: frei, Ebenen, radial und radial abwechselnd, Ballon und automatisches Tip-over.
    • Im Modus für freies Layout werden die untergeordneten Knoten jedes Knotens rekursiv ausgehend vom Stammknoten angeordnet, so dass die Links einheitlich in dieselbe Richtung weisen.
    • Im Ebenenlayoutmodus werden die Knoten in Ebenen eingeteilt und die Ebenen horizontal oder vertikal angeordnet.
    • Im Radiallayoutmodus werden die Knoten in Ebenen eingeteilt und die Ebenen in Kreisen oder Ellipsen um den Stammknoten herum angeordnet.
    • Im Ballonlayoutmodus werden die untergeordneten Knoten in Kreisen um den übergeordneten Knoten herum angeordnet, so dass jede untergeordnete Baumstruktur einen Ballon bildet.
    • Im Tip-over-Modus werden die Knoten auf ähnliche Weise wie im Modus für freies Layout angeordnet, aber es wird versucht, untergeordnete Knoten automatisch zu kippen (Tip-over), damit das Layout dem Seitenverhältnis besser entspricht.
  • Stellt mehrere Ausrichtungs- und Offsetoptionen bereit.
  • Ermöglicht Ihnen die Angabe der Knoten, die direkte Nachbarn sein müssen.
  • Unterstützt inkrementelle und nicht inkrementelle Modi. Im inkrementellen Modus werden die vorherigen Positionen der Knoten berücksichtigt und die Knoten positioniert, ohne die relative Reihenfolge der Knoten in der Baumstruktur zu ändern, so dass das Layout bei inkrementellen Änderungen des Graphen stabil bleibt.
  • Effizienter skalierbarer Algorithmus. Erzeugt ein übersichtliches Layout, selbst bei einer sehr hohen Anzahl an Knoten.

Einschränkungen

  • Wenn die Orthogonaleinstellung nicht als Linkstil angegeben ist (siehe Linkstil (TL)), können sich in seltenen Fällen Links mit Knoten überschneiden. Dies ist abhängig von der Größe der Knoten, der Ausrichtungsparameter und der Offsetparameter.
  • Der Layoutalgorithmus bestimmt zuerst einen Spanning Tree des Graphen. Wenn der Graph keine reine Baumstruktur ist, werden einige Links nicht in den Spanning Tree aufgenommen. Diese Links werden ignoriert. Deswegen können sie im endgültigen Layout andere Links kreuzen oder sich mit Knoten überschneiden.
  • Im Hinblick auf die Stabilität versucht der Algorithmus im inkrementellen Modus, die relative Reihenfolge der untergeordneten Knoten jedes Knotens zu bewahren. Er verwendet ein heuristisches Verfahren, um die relative Reihenfolge anhand der vorherigen Positionen der Knoten zu berechnen. Das heuristische Verfahren kann scheitern, wenn untergeordnete Knoten ihre alten Positionen überlappen oder wenn sie nicht horizontal oder vertikal ausgerichtet sind.
  • Trotz der Einhaltung der relativen Reihenfolge der untergeordneten Knoten ist das Layout in inkrementellen Radiallayouts in seltenen Fällen nicht perfekt stabil. Nachfolgende Layouts können die Knoten um den Stammknoten herum drehen, obwohl die relative Kreisanordnung der Knoten innerhalb ihrer Kreisebenen weiterhin beibehalten wird.
  • Trotz der Einhaltung der relativen Reihenfolge der untergeordneten Knoten ist das Layout in inkrementellen Ballonlayout in seltenen Fällen nicht perfekt stabil. Nachfolgende Layouts können die Knoten um den übergeordneten Knoten herum drehen, obwohl die relative Kreisanordnung der Knoten weiterhin beibehalten wird.
  • Die Tip-over-Layoutmodi führen mehrere Testlayouts mit unterschiedlichen Tip-over-Ausrichtungsoptionen auf der Basis verschiedener heuristischer Verfahren aus. Aus diesen Testlayouts wählt der Algorithmus das am besten für das Seitenverhältnis geeignete Layout aus. Es ist möglicherweise nicht das optimale Layout für das Seitenverhältnis, aber das beste Layout aus der Gruppe der Testlayouts. Die Berechnung des absolut besten Layouts ist nicht machbar. Dies ist ein allgemeines "NP-vollständig"-Problem.