Brief Description of the Algorithm

Graph Layout > Layout Algorithms > Orthogonal Link Layout > Brief Description of the Algorithm

The Orthogonal Link Layout algorithm is based on a combinatorial optimization that chooses the “optimal” shape of the links in order 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. See the orthogonal link style in Orthogonal Link Drawing Produced with the Orthogonal Link Option and the direct link style in Orthogonal Link Drawing Produced with the Direct Links Option.

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 given side of a node.

Space the final segments of the links incident to a given side of a node equally on the node, no matter what their width.

Code Sample

Below is a code sample using the IlvOrthogonalLinkLayout class:

// ...

IlvGrapher* grapher = new IlvGrapher(display);

// ... Fill in the grapher with nodes and links here

IlvOrthogonalLinkLayout* layout = new IlvOrthogonalLinkLayout();

layout->attach(grapher);

// Set the layout parameters, e.g., the offset between links:

layout->setLinkOffset(5);

// Perform the layout

IlvGraphLayoutReport* layoutReport = layout->performLayout();

if (layoutReport->getCode() != IlvLayoutReportLayoutDone)

IlvWarning("Layout not done. Error code = %d\n", layoutReport->getCode());

// ...

// If this grapher is not anymore subject of layout:

layout->detach();

// Once the layout algorithm is not anymore needed:

delete layout;

Version 6.1