Die Link-Layout-Algorithmen werden über die folgenden Klassen implementiert:
- ibm_ilog.graphlayout.shortlink.ShortLinkLayout für kurze Links
- ibm_ilog.graphlayout.longlink.LongLinkLayout für lange Links
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();