For experts: special options of long link layout

> > > > >

The Link Layout algorithm uses the class IlvLongLinkLayout as subalgorithm. IlvLongLinkLayout is a subclass of IlvGraphLayout and can be used a stand-alone as well. To access the instance of IlvLongLinkLayout that is used by the Link Layout algorithm, use the method:

IlvLongLinkLayout getLongLinkLayout();

Using this accessor, you can control many special features of the Long Link Layout that are not made available by the IlvLinkLayout class because these features are for experts only.

Specifying additional obstacles

The Long Link Layout algorithm considers nodes to be obstacles that cannot be overlapped and links to be obstacles that can be crossed at an angle of 90 degree (approximately, if the link style is direct), but that cannot be overlapped.

A link
first overlapping a node, then crossing another link, then overlapping
another link

Crossing and overlapping

Example of specifying additional obstacles (Link Layout algorithm)

If an application requires additional obstacles that are not links or nodes, they can be specified as follows:

In CSS

It is not possible to specify additional obstacles in CSS.

In Java

Call:

layout.getLongLinkLayout(). addRectObstacle

layout.getLongLinkLayout(). addLineObstacle

Rectangular obstacles behave like nodes: links cannot overlap the rectangles. Line obstacles behave like link segments: other links can cross the line segments, but cannot overlap the segments. These obstacle settings can be removed as follows:

In Java

layout.getLongLinkLayout(). removeAllRectObstacles

layout.getLongLinkLayout().

removeAllLineObstacles

Penalties for variable end points

If the termination points of the links are not fixed, the algorithm uses a heuristic to calculate the termination points of each link. It examines all free grid points that are close to the border of the start and end node and assigns a penalty to each grid point. If a node-side filter is installed, the penalty depends on whether the node side is allowed or rejected.

A more precise way to affect how the termination points are chosen is the termination point filter. It allows the user to specify the penalty for each grid point.

Example of specifying the termination point filter (Link Layout algorithm)

In CSS

It is not possible to specify the termination point filter in CSS.

In Java

A termination point filter is a class that implements the interface IlvTerminationPointFilter that defines the following method:

public int getPenalty(IlvGraphModel graphModel, Object link,
boolean origin, Object node, IlvPoint point, 
int side, int proposedPenalty);

To select the origin or destination point of the input link , the input point (a grid point on the input side of the node ) is examined. The proposedPenalty is calculated by the default heuristic of the algorithm. You can return a changed penalty or you can return java.lang.Integer.MAX_VALUE to reject the grid point. If the grid point is rejected, it is not chosen as termination point of the link.

The termination point filter can be set as follows:

Call on the IlvLongLinkLayout instance: setTerminationPointFilter

Manipulating the routing phases

As mentioned in Long Link Layout algorithm, the algorithm first treats each link individually and then applies a crossing reduction phase to all links. To find a route for an individual link, the algorithm first checks whether a routing (such as a straight line or with only one bend) is possible. If this type of routing is not possible, it uses a sophisticated, but more time consuming, grid search algorithm with backtracking to find a route with many bends.

Example of manipulating the routing phases (Link Layout algorithm)

To disable the phase that finds a straight-line or one-bend routing:

In CSS

Add to the LinkLayout section:

layoutMode: "LONG_LINKS";
straightRouteEnabled: "false";

In Java

Call:

layout.getLongLinkLayout(). setStraightRouteEnabled

The backtrack search for a route with many bends can be done in several ways.

A convenient way is to specify the maximum time available to search for the route for each link.

Example of specifying backtrack steps (Link Layout algorithm)

You can specify the maximum number of backtrack steps.

In CSS

Add to the LinkLayout section:

layoutMode: "LONG_LINKS";
maxBackTrack: "1000";

In Java

Call:

layout.getLongLinkLayout(). setMaxBacktrack

The default maximum backtrack number is 30000.

Example of specifying maximum time for route search (Link Layout algorithm)

To specify the maximum time available to search for the route for each link.

In CSS

layoutMode: "LONG_LINKS";
allowedTimePerLink: "4000";

In Java

Call:

setAllowedTimePerLink

The default allowed time per link is 2000 milliseconds (2 seconds).

Finally, you can specify how many steps must be done during the crossing reduction phase.

Example of specifying the number of steps in crossing reduction phase (Link Layout algorithm)

To specify how many steps must be done during the crossing reduction phase:

In CSS

Add to the LinkLayout section

layoutMode: "LONG_LINKS";
numberCrossingReductionIterations: "5";

In Java

Call

setNumberCrossingReductionIterations

Example of disabling crossing reduction (Link Layout algorithm)

You can disable the crossing reduction completely.

In CSS

Add to the LinkLayout section:

layoutMode: "LONG_LINKS";
crossingReductionEnabled: "false";

In Java

Call

setCrossingReductionEnabled

Fallback mechanism

If one of the end nodes is inside an enclave, the Long Link Layout algorithm might not be able to find a routing for a link. In A node inside an enclave, the pink node is inside an enclave. In this case, the backtrack search algorithm fails to find a routing without overlapping nodes. The backtrack search algorithm can also fail if the situation is so complex that the search exceeds the allowed time per link.

A node inside an enclave

When the backtrack search algorithm fails to find a routing, a simple fallback mechanism is applied that creates a routing with a node overlap.

Example of disabling the fallback mechanism (Link Layout algorithm)

To disable the fallback mechanism:

In CSS

Add to the LinkLayout section:

layoutMode: "LONG_LINKS";
fallbackRouteEnabled: "false";

In Java

layout.getLongLinkLayout().setFallbackRouteEnabled(false);

If the fallback mechanism is disabled, these links are not routed at all and remain in the same shape as before the layout. In Java code, you can retrieve the links that could not be routed in the usual way without the fallback mechanism.

Example of retrieving links without the fallback mechanism (Link Layout algorithm)

To retrieve the links that could not be routed in the usual way without the fallback mechanism:

In Java

Enumeration e = layout.getLongLinkLayout().getCalcFallbackLinks();

For example, you can iterate over these links and apply your own specific fallback mechanism instead of the default fallback mechanism of the Long Link Layout algorithm.

Current section

Link layout (LL)