Optimizing the performance of Graph Layout
Describes how to optimize the performance of the graph layout algorithm used by your application.
Briefly describes how the application performance can be optimized.
Explains how to avoid unnecessary executions of the layout to improve performance.
Provides some hints on how to deal with huge graphs.
Describes the speed of the different layout algorithms.
Introduction
If your application displays and manipulates only small graphs, you don't need to worry about performance optimizations. Some layout algorithms are designed for medium sized graphs, and only few algorithms are available for huge graphs. Graph layout is in general a complex task that often uses heuristics to solve NP-hard problems (problems that cannot be easily solved from a computational point of view). Different heuristics have different speed characteristics.
Graph layout places the nodes and routes the links. If moving nodes and reshaping links is slow, graph layout cannot be fast. Therefore, it is important to know the performance hints described in
Optimizing the performance of JViews Framework in addition to those hints that are related to graph layout.
Use layout only when needed
The graph layout algorithm is most likely the most complex part of your application. Hence it might also be the slowest part of your application. Therefore it is useful to design the application so that graph layout is used only when needed. For instance, the application could offer a button that triggers layout, so that the graph layout does not need to run continuously during all interactions.
Graph layout places the nodes and routes the links. If moving nodes and reshaping links is slow, graph layout cannot be fast. Therefore, it is important to know the performance hints described in the
Optimizing the performance of JViews Framework in addition to those hints that are related to graph layout.
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. This has the effect that the layout is triggered whenever a node moves. However, if you have too many links, a full automatic link layout will be too slow. An alternative way to ensure orthogonal links is to use the orthogonal mode of
IlvEnhancedPolylineLinkImage (and its subclasses). This mode will ensure 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 layout mode. To enable the orthogonal mode on a link, call:
enhancedLinkImage.setOrthogonal(true);
Automatic layout
If you must use automatic layout (
setAutoLayout), be aware that the layout is triggered whenever any event is fired that indicates a change of the graph. In this case, it is important to optimize the events by using adjusting sessions as explained in
Events and listeners. This avoids that a sequence of changes triggers many layouts and ensures that the layout is only called once at the end of the sequence of changes.
JViews Diagrammer renderingDoneMode invocation
In JViews Diagrammer, the automatic layout is false by default, but the graph layout may be invoked automatically by JViews Diagrammer listeners when the diagram becomes outdated. This happens when the graph structure has changed because model objects have been added or removed. Or when a diagram event, like a model property change or selection, has impacted the bounding box of at least one graphic object. In this case, JViews Diagrammer automatically runs the current graph layout to keep the diagram accurate. However, the graph layout call can be expensive for large graphs or for complex algorithms. Sometimes, the event that triggered the layout does not justify a new computation of the layout.
To help you control when the graph layout is invoked automatically,
IlvSDMEngine provides the property
renderingDoneMode. This property is read when JViews Diagrammer receives an event, such as a new selection, a property change, the addition, or the removal of an object in the model.
The possible values of the property renderingDoneMode are:
IlvSDMEngine.ALWAYS: The graph layout is always called automatically on events.
IlvSDMEngine.NEVER: The graph layout is never called automatically on events.
IlvSDMEngine.IF_BBOX_CHANGED: The graph layout is called on selection or property change only if the bounding box of the selected graphic object has changed. This mode is the default mode and is suitable for most cases, because the graph or link layout generally depends only on the position and size of the objects.
You can configure the renderingDoneMode property in the style sheet or through the API.
In the style sheet, use one of the following string values:
IF_BBOX_CHANGED NEVER ALWAYS NOTE Whatever the value of this property, you can always manually perform a layout using for example IlvSDMEngine.performLayout().
Layout of huge graphs
Different graph layout algorithms can handle different graph sizes. As a rule of thumb:
More details are given in
Speed of layout algorithms.
Don't show all links
The tree layout can handle very huge graphs. If you have a very huge graph with links, the recommended way is 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 the hidden links. For example, selecting one node may highlight all nodes that are reachable from this node via hidden or visible links. This is even more ergonomic than displaying all the links at the same time, since 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 instance, a graph of people can be clustered according to nationality, or according to families. Each cluster can be represented as a nested subgraph (
IlvGrapher) that can be collapsed and expanded.
The advantage of subgraphs is having a faster layout when they are collapsed, since a faster layout does not need to lay out the inner of the clusters. The diagram also becomes more comprehensible if only those details of interest are shown and the less interesting subgraphs are collapsed. On the other hand, if all subgraphs are expanded, the layout may become slow if the nesting depth of subgraphs is too high. When dealing with very large graphs, a carefully designed clustering into nested subgraphs can help to improve the user experience of the application.
Speed of layout algorithms
The speed of the graph layout algorithms depends on the type of graph and on the layout parameters. Some layouts are very slow for specific types of graphs. Some layouts are fast in general but become slow for specific layout parameter settings. The speed of all layouts depends also on the performance of the nodes and links that are used. If you use nodes classes with a very inefficient implementation for moving the nodes, or link classes with a very inefficient implementation for reshaping the links, then the layout algorithm will also be slow, since it moves nodes and reshapes links.
Layout customization interfaces
Several layout algorithms support customization interfaces such as
IlvNodeBoxInterface,
IlvNodeSideFilter,
IlvLinkConnectionBoxInterface or
IlvLinkClipInterface. When you use these interfaces, the layout algorithm jumps into your code. Be careful when implementing these interfaces, so that they do not decrease the performance of the layout algorithm.
Tree layout
Tree Layout is in general very fast and can handle huge graphs, as long as none of the automatic tip over modes are used.
The layout mode FREE and LEVEL are the fastest modes.
The radial layout modes are a bit slower, but usually still fast enough for very large graphs.
The tip over layout modes are slow and should only be used for small graphs.
For details, see
Tree Layout (TL).
Hierarchical layout
The speed of hierarchical layout depends on the density of the graph. Hierarchical layout can handle very large graphs that have only few links, but it might be too slow for smaller graphs that have a huge amount of 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, you should avoid unsatisfiable constraint conflicts, because detecting these conflicts is very slow.
Grid layout
Grid layout is in general very fast and can handle huge graphs. However, in layout mode TILE_TO_MATRIX, the speed depends on the grid mesh size (the distance between grid lines). The smaller the grid mesh size, the slower the layout. In the other layout modes, the grid mesh size has no influence on the performance.
For details, see
Grid layout (GL).
Link layout
The speed of link layout depends on the number of links. It is suitable for small and medium size graphs. If the graph has too many links, see section Orthogonal links without link layout.
In layout mode
LONG_LINKS (or when using the
IlvLongLinkLayout) the layout speed depends on the grid mesh size (the distance between grid lines). The smaller the grid mesh size, the slower the layout. Additionally, the exhaustive search mode (
setExhaustiveSearching) of
IlvLongLinkLayout should be avoided, because it is very slow.
For details, see
Link layout (LL).
Uniform length edges layout
To fit a variety of needs, the algorithm provides three optional modes: incremental, non-incremental and fast multilevel. The later is the fastest for medium and large graphs. For more details on these modes, see
Layout mode.
Copyright © 2018, Rogue Wave Software, Inc. All Rights Reserved.
