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:
- The speed of the JavaScript engine of your browser.
- 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.