LL-Algorithmen

Die Link-Layout-Algorithmen werden über die folgenden Klassen implementiert:

Algorithmus für Layout mit kurzen Links

Der Algorithmus für Layout mit kurzen Links basiert auf einer kombinatorischen Optimierung, die die "optimale" Form der Links auswählt, um eine Kostenfunktion zu minimieren. Diese Kostenfunktion ist proportional zur Anzahl der Kreuzungen zwischen Links und zwischen Links und Knoten.
Aus Effizienzgründen wird die Basisform jedes Links aus einer Gruppe vordefinierter Formen ausgewählt. Diese Formen sind für jede Linkstiloption verschieden. Für den orthogonalen Linkstil werden die Links in eine Mehrfachlinie mit bis zu fünf alternierenden horizontalen und vertikalen Segmenten umgeformt (siehe Layout mit kurzen orthogonalen Links). Für den direkten Linkstil werden die Links in eine Mehrfachlinie umgeformt, die sich aus drei Segmenten zusammensetzt: einem Segment mit gerader Linie (siehe straight-line), das mit kleinen horizontalen oder vertikalen Segmenten beginnt und endet (siehe Derselbe Graph im Layout mit kurzen direkten Links).
Die Form eines Links richtet sich auch nach der relativen Position des Ursprungs- und des Zielknotens. Wenn zwei Knoten beispielsweise nah beieinander liegen oder sich überschneiden, wird die Form des Links so gewählt, dass eine bestmögliche Sichtbarkeit des Links gewährleistet ist.
Die exakte Form eines Links wird unter Berücksichtigung weiterer Vorgaben berechnet. Der Layoutalgorithmus versucht,
  • die Anzahl der Kreuzungen zwischen den Links an einer bestimmten Seite eines Knotens (siehe incident) zu minimieren,
  • die Endsegmente der Einfallslinks für eine bestimmte Seite eines Knotens in gleichmäßigem Abstand am Knotenrand zu verteilen.

Algorithmus für Layout mit langen Links

Der Algorithmus für Layout mit langen Links bearbeitet zunächst jeden Link einzeln. Für jeden Link berechnet er zunächst die Verbindungspunkte an den Endknoten, die sich im Raster befinden, und sortiert diese dann mithilfe eines Strafwerts. Verbindungspunkte an verwendeten Rasterpunkten haben einen hohen Strafwert und werden deshalb wahrscheinlich nicht verwendet.
Für die orthogonalen Links (siehe Layout mit langen orthogonalen Links) verwendet der Algorithmus für das Layout mit langen Links dann eine Rastertraversierung, um einen Pfad über die freien Rasterpunkte vom Anfangsverbindungspunkt bis zum Endverbindungspunkt zu ermitteln. Deshalb können orthogonale Links im Gegensatz zum Modus für kurze Links eine beliebige Form mit vielen Kurven haben, sofern dies erforderlich ist, um Knoten, die ein Hindernis darstellen, zum umgehen und somit Überschneidungen zu vermeiden. Informationen zu direkten Links finden Sie unter Derselbe Graph im Layout mit kurzen direkten Links. Die Suche wird verkürzt, indem ein direktes Segment zwischen den Verbindungspunkten gesucht wird.
Nach der Platzierung aller Links werden in einer Phase zur Reduktion der Kreuzungen Linkpaare überprüft und Linkkreuzungen entfernt, indem Teile der Pfade zwischen den Links ausgetauscht werden.
Der Algorithmus für das Layout mit langen Links stützt sich auf die Tatsache, dass Links in den Rasterlinienabstand passen und Teile der Pfade zwischen verschiedenen Links ausgetauscht werden können. Deshalb berücksichtigt der Algorithmus für das Layout mit langen Links die Linkbreite nicht, weil es zu schwierig wäre, die Teile der beiden Links zu finden, die ausgetauscht werden können. Es wird empfohlen, für den Rasterlinienabstand einen Wert zu wählen, der größer ist als die größte Linkbreite.

Beispiel für das Link-Layout

Das folgende Codebeispiel veranschaulicht die Verwendung der Klasse ibm_ilog.graphlayout.shortlink.ShortLinkLayout.
var layout = new ibm_ilog.graphlayout.shortlink.ShortLinkLayout();
graph.setLinkLayout(layout);
graph.performGraphLayout();