Graph layout optimizations

Graph layout is, in general, a complex task that often uses heuristics to solve NP-complete problems (problems that cannot be easily solved from a computational point of view). Different heuristics have different speed characteristics. Small graphs do not usually require performance optimizations. Some layout algorithms are designed for medium-sized graphs, but only a few algorithms are available for large graphs.

Use layout only when needed

The graph layout algorithm is typically the most complex and slowest part of your application. Design your applications to use graph layout sparingly, and only when needed. For example, you could include a button that triggers layout, so the layout does not need to run continuously during all interactions.

Use orthogonal links without link layout

If your application requires orthogonal link shapes, you might be tempted to use a link layout in automatic layout mode (see setAutomaticLinkLayout). However, this mode causes the layout to be triggered whenever a node moves. If you have many links, a full automatic link layout can be slow. An alternative method is to use the orthogonal shape type of link (see setShapeType). This type ensures that the link shape remains orthogonal, without analyzing all links to reduce link crossings and overlaps. Therefore it can be more efficient than running link layout in automatic mode.
To enable the orthogonal shape type on a link, issue one of the following calls:
  • link.setShapeType(ibm_ilog.diagram.LinkShapeType.Orthogonal);
  • link.setShapeType(ibm_ilog.diagram.LinkShapeType.OrthogonalEditable);

Use layout appropriate for graph size

Different graph layout algorithms support graphs of different sizes.
  • Tree Layout and Grid Layout can handle large graphs.
  • Hierarchical Layout can handle medium-sized graphs that do not have too many links.
  • ForceDirected Layout is the slowest algorithm, and is not suitable for large graphs.
For more details, see Speed of graph layout algorithms.

Do not show all links

If you have a large graph with links, it is best to show only a spanning tree of the graph and hide the other links. The spanning tree can be laid out with the Tree Layout.
Design your application to use interactions to make the user aware of hidden links. For example, selecting one node might highlight all nodes that are reachable from this node through hidden or visible links. It is more ergonomic than displaying all the links at the same time. The user's eyes cannot trace links if too many are displayed at the same time.

Cluster into subgraphs and collapse

Sometimes graphs have meaningful cluster information. For example, a graph of people can be clustered according to nationality or according to families. Each cluster can be represented as a nested subgraph (Subgraph) that can be collapsed or expanded.
Subgraphs have a faster layout when they are collapsed, since there is no need to lay out the inner content of the clusters. The diagram also becomes more comprehensible if only details of interest are shown while less interesting subgraphs are collapsed. Conversely, if all subgraphs are expanded, when the nesting depth of the subgraphs is high, the layout can become slow. When an application uses large graphs, a carefully designed clustering into nested subgraphs can help to improve user experience.

Speed of graph layout algorithms

The speed of the graph layout algorithms depends on the type of graph and on the layout parameters. Some layouts are slow for specific types of graphs.

Tree Layout

Tree Layout is fast and can handle huge graphs, as long as you do not use automatic tip-over modes.
  • The FREE and LEVEL layout modes are the fastest.
  • The radial layout modes are slightly slower, but still fast enough for large graphs.
  • The tip-over layout modes are slow and work best for small graphs only.
For details, see Tree Layout (TL).

Hierarchical Layout

The speed of Hierarchical Layout depends on the density (the ratio between the number of links and the number of nodes) of the graph. Hierarchical Layout can handle large graphs that have few links, but can be slow for smaller graphs that have many links.
The speed and quality of the Hierarchical Layout also depends on the number of constraints. The fewer constraints, the more freedom the layout has to place nodes, and the faster the layout is. In particular, avoid constraint conflicts, because detecting these conflicts is slow.
For details, see Hierarchical Layout (HL).

Grid Layout

Grid Layout is fast and can handle large graphs. However, in TILE_TO_MATRIX layout mode, the speed depends on the grid mesh size (the distance between grid lines). The smaller the grid mesh size, the slower the layout. In other layout modes, the grid mesh size has no influence on performance.
For details, see Grid layout (GL).

Short and Long Link Layout

The speed of Link Layout depends on the number of links. Link Layouts are suitable for small and medium size graphs. If the graph has many links, see Use orthogonal links without link layout.
For Long Link Layout, the speed depends on the grid mesh size (the distance between grid lines). The smaller the grid mesh size, the slower the layout. If possible, avoid the exhaustive search mode (LongLinkLayout.setExhaustiveSearching), because it is slow.
For details, see Link layout (LL).

Force-Directed Layout

This algorithm provides three optional modes: incremental, non-incremental, and fast multilevel. The latter is fastest for medium and large graphs.
For more details on these modes, see Layout mode for the layout mode of the Force-Directed Layout.

Server-side Layout

For large or complex graphs, you can improve performance by using Server-side Layout. Server-side layout sends all the graph data to the server and performs the graph layout on the server. It can be faster depending on:
  1. The speed of the JavaScript engine of your browser.
  2. The speed of the network connection between the client and the server.

Layout customization interfaces

Several layout algorithms support customization interfaces, such as INodeBoxProvider, INodeSideFilter or ILinkConnectionBoxProvider. When you use these interfaces, the layout algorithm jumps directly into your code. Use care when implementing these interfaces, because they can lead to decreased performance of the layout algorithm.