The link layout algorithms are implemented by the following
classes:
- ibm_ilog.graphlayout.shortlink.ShortLinkLayout for short links
- ibm_ilog.graphlayout.longlink.LongLinkLayout for long links
Short Link Layout algorithm
The Short Link Layout algorithm is based on a combinatorial
optimization that chooses the “optimal” shape of the
links to minimize a cost function. This cost function is proportional
to the number of link-to-link and link-to-node crossings.
For efficiency reasons, the basic shape of each link
is chosen from a set of predefined shapes. These shapes are different
for each link style option. For the orthogonal link style, the links
are reshaped to a polygonal line of up to five alternating horizontal
and vertical segments (see Short link layout with orthogonal links). For the
direct link style, the links are reshaped to a polygonal line composed
of three segments: a straight-line segment that starts and ends with small horizontal
or vertical segments (see The same graph in short link layout with direct links).
The shape of a link also depends on the relative position
of the origin and destination nodes. For instance, when two nodes
are very close or they overlap, the shape of the link is chosen to
provide the best visibility of the link.
The exact shape of a link is computed taking into account
additional constraints. The layout algorithm tries to:
- Minimize the number of crossings between the links incident to a specific side of a node.
- Space the final segments of the links incident to a specific side of a node equally on the node border.
Long Link Layout algorithm
The Long Link Layout algorithm first treats each link
individually. For each link, it first calculates the connection points
at the end nodes that are on the grid and orders them according to
a penalty value. Connection points on used grid points have a high
penalty and, therefore, are unlikely to be used.
For the orthogonal links (see Long link layout with orthogonal links), the Long
Link Layout algorithm then uses a grid traversal to search a route
over free grid points from the start connection point to the end connection
point. Therefore, in contrast to the short link mode, orthogonal links
can have any shape with many bends if it is necessary to bypass obstacle
nodes to avoid overlapping. For the direct links, see The same graph in short link layout with direct links, it shortens
the search by using a direct segment between the connection points.
After all links are placed, a crossing reduction phase
examines pairs of links and eliminates link crossings by exchanging
parts of the routes between both links.
The Long Link Layout algorithm relies on the fact that
links fit to the grid spacing and parts of the routes between different
links can be exchanged. Therefore, the Long Link Layout algorithm
does not take the link width into account because it would be too
difficult to find the parts of two links that can be exchanged. It
is recommended to set the grid spacing larger than the largest link
width.
Example of Link Layout
The following code example shows the use of the ibm_ilog.graphlayout.shortlink.ShortLinkLayout class.
var layout = new ibm_ilog.graphlayout.shortlink.ShortLinkLayout(); graph.setLinkLayout(layout); graph.performGraphLayout();