Innovations within reach: The parameters that matter most for creating interactive diagrams on mobile devices

Algorithm tips and performance hints for using IBM ILOG Dojo Diagrammer

IBM® ILOG® Dojo Diagrammer includes a comprehensive set of graph layout algorithms that come with a vast number of customization parameters. This article provides a quick reference guide of the most important parameters for each algorithm, along with the parameters that can significantly influence performance. It also provides hints for optimizing the diagramming applications using graph layout on mobile devices. This content is part of the IBM WebSphere Developer Technical Journal.

Share:

Adrian Vasiliu (vasiliu@fr.ibm.com), Software Engineer, IBM China

Adrian Vasiliu has been an architect and developer of diagramming and graph layout technologies at ILOG since 1997 and IBM since 2009. Adrian has a PhD in Computer Science from Ecole Centrale Paris (1997).



21 September 2011

Also available in Chinese

Each installment of Innovations within reach features new information and discussions on topics related to emerging technologies, from both developer and practitioner standpoints, plus behind-the-scenes looks at leading edge IBM® WebSphere® products.

Introduction

IBM ILOG Dojo Diagrammer is a component of the newly released IBM WebSphere® Application Server Feature Pack for Web 2.0 and Mobile V1.1. Dojo Diagrammer enables applications to display and edit graphs (diagrams) and provides a comprehensive set of graph layout algorithms for the automatic placement of the nodes and to ensure the links have optimal shapes. Figure 1 is an example of a business process management (BPM) application using Dojo Diagrammer.

Figure 1. Example of graph layout in BPM applications
Figure 1. Example of graph layout in BPM applications

In a recent blog entry, I provided some quick guidance about how to make a choice among the graph layout algorithms provided by Dojo Diagrammer, while mentioning that each algorithm can be fine-tuned using a number of parameters. Expanding on this, the tables in the next section list the critical parameters that you need to know about, based on graph format, along with tips that describe how these parameters can affect your application performance:

  1. Hierarchical layout
  2. Tree layout
  3. Force-directed layout
  4. Circular layout
  5. Grid layout
  6. Short link layout
  7. Long link layout

The graph layout parameters that matter the most

1. Hierarchical layout
ParameterValuesComments
flowDirectionleft, right, top, bottomDefines the direction toward which most links of the diagram "flow."
globalLinkStyleorthogonal, polyline, straightDifferent styles can be intermixed in the same diagram..
recursiveModetrue, falseWhen enabled (which is the default), the algorithm optimizes the layout globally for an entire nested graph, instead of a local optimization for each subgraph (a subgraph is a graph contained in a node of another graph). Also, when enabled, it lays out the “intergraph” links (that is, links that interconnect nodes from different subgraphs).

The hierarchical layout algorithm provides many other customization options, including various spacing parameters, an incremental mode, and a fine-grain constraint system.

Impact of parameters on performance:

  • The speed of hierarchical layout depends mostly on the characteristics of the graph itself. In particular, it depends on the density of the graph; that is, the ratio between the number of links and the number of nodes. The algorithm can handle very large graphs that have only a few links, but it might be too slow for smaller graphs that have a huge number of links.
  • Among the parameters, the “hierarchical constraints” have the highest influence on the speed. The constraints are a mechanism for the user to customize the layout in a fine-grain manner. The fewer the constraints, the more freedom the layout has to place nodes, and the faster the layout. In particular, you should avoid unfeasible constraint conflicts, because the detection of these conflicts is very slow.
2. Tree layout
ParameterValuesComments
layoutModefree, level, balloon, radial, alternating radial, various variants of tip-over modesThe arrangement differs quite significantly depending on this parameter, and so it is therefore interesting to experiment with the modes for choosing the one that fits better.
flowDirectionleft, right, top, bottomDefines the direction towards which the diagram "flows."
globalLinkStyleorthogonal, straightBoth styles can be intermixed in the same diagram.

The tree layout algorithm provides many other customization options, including various spacing parameters.

Impact of parameters on performance:

  • The layout modes free and level are the fastest.
  • The radial layout modes are a bit slower, but usually fast enough even for large graphs.
  • The tip-over layout modes are slow and should only be used for small or medium graphs.
3. Force-directed layout
ParameterValuesComments
layoutModeincremental, non-incremental, fast multilevelThe most useful is the fast multilevel mode because it is often faster for large graphs. The incremental mode helps in case it is important that the layout preserves as much as possible in the initial positions of the nodes, thus preserving the so-called "mental map" of the user.
preferredLinksLengthnumberIncrease the value to spread the nodes over a larger area, or decrease the value to get a more dense arrangement.

Impact of parameters on performance:

  • To fit a variety of needs, the algorithm provides three optional modes: incremental, non-incremental and fast multilevel. The latter is generally the fastest for medium and large graphs.
4. Circular layout
ParameterValuesComments
clusteringModebySubgraphs, byClusterIds, AutomaticDetermines how the clusters are specified: either each subgraph forms a cluster, or the clusters are specified per node by an id, or the clusters are automatically determined from the graph topology without any additional specification.
addClusterIdnumberWhen the clustering mode is byClusterIds, then specifying clusters, star centers, ordering indexes change the layout most.
minimumClusterSize, maximumClusterSize, clusterByBiconnectivitynumber and true, falseWhen the clustering mode is Automatic, these parameters influence how the nodes of the graph are grouped into clusters.

The circular layout algorithm provides other customization options, including various spacing options.

Impact of parameters on performance:

  • The automatic clustering mode is usually the slowest mode, because it requires the computation of an optimal clustering, while in the other modes the clustering is provided as input to the algorithm.
5. Grid layout
ParameterValuesComments
layoutModerows, columns, matrix with fixed total width, matrix with fixed total heightThe nodes can be arranged either on rows, or on columns, or in a matrix (grid) for which either the total width or the total height is specified.
horizontalGridOffset, verticalGridOffsetnumberIf the layoutMode is matrix, define the spacing of the grid lines. If the layoutMode is rows or columns, these parameters are not used.
leftMargin, rightMargin, topMargin, bottomMarginIf the layoutMode is rows or columns, define the minimum distance between the border of the nodes and the border of the grid cell. If the layoutMode is matrix, defines the minimum distance between two adjacent nodes.

The grid layout algorithm provides other customization options, including an incremental mode and ordering options.

Impact of parameters on performance:

  • The grid layout in general is 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 gridlines). The smaller the grid mesh size, the slower the layout.
  • If the layout mode is rows or columns, the grid mesh size has no influence on the performance.
6. Short link layout
ParameterValuesComments
globalLinkStyleorthogonal, directDifferent styles can be mixed in the same diagram.
linkOffsetnumberDefines the minimum offset between links connected to the same node.

The short link layout algorithm provides other customization options, including various spacing options.

Impact of parameters on performance:

  • The speed mostly depends on the number of links. This layout is suitable for small and medium size graphs.
7. Long link layout
ParameterValuesComments
globalLinkStyleorthogonal, directDifferent styles can be mixed in the same diagram.
horizontaGridOffset, verticalGridOffsetnumberKey dimensional parameters that define how dense is the grid where link points are placed. A finer grid (lower grid size) usually improves the quality of the layout, but at the price of slower computation and an increased memory footprint.

The long link layout algorithm provides other customization options, including various spacing options.

Impact of parameters on performance:

  • The speed depends on the number of links. This layout is suitable for small and medium size graphs.
  • The grid mesh size parameter (the distance between the grid lines) has a high influence of the performance. The smaller the grid mesh size, the slower the layout.
  • The algorithm provides an exhaustiveSearchMode which should be avoided when performance is a concern.

Optimizing graph layout applications for mobile devices

Mobile devices have specific constraints compared to a typical desktop or laptop computer:

  • Screen size is much smaller (holds for tablets and especially for smartphones).
  • Specific interaction paradigms (using touch gestures).
  • Less available memory.
  • Lower CPU power.
  • Slower network access, in particular for a GSM connection.

The small screen size and the interaction paradigms require you to design the graphical user interface in a way that suits the mobile devices. Dojo Diagrammer benefits from the mobile dojo package, dojox.mobile, which makes this adaptation easy.

Mobile applications also need to take CPU, memory, and network speed constraints into account. In the case of diagramming applications using graph layout, all three of these factors are critical. Indeed, most graph layout algorithms are computational intensive by their mathematical nature, and the mobile device needs to receive the data describing the graph via the network, which can be slow for large graphs.

Here are some key hints for optimizing your graph layout application on mobile devices:

  • Design the application such that it presents to the user small or medium graphs. If the business data involves large graphs, extract small relevant portions of the data (Figure 2 illustrates this idea). Besides saving computational power, this also provides a view on the data which fits the size of the screen.
  • Among the graph layout algorithms, lean toward using the fastest ones, in particular for large graphs. The fastest algorithms are the tree and grid layouts. Hierarchical and link layouts are slower and should be used for small or medium graphs. The slowest algorithm is the force-directed layout.
  • Pay attention to customization parameters of graph layouts that can strongly impact performance.
  • Try the server-side execution of graph layout. Dojo Diagrammer enables you to execute the layout algorithm either as Dojo code inside the browser, or as Java™ code running on a server (thanks to a ready-to-use RESTfull/JAX-RS service, included in the product). When running the layout algorithm on the server, the CPU and memory of the actual devices matter much less. Additionally, the mobile device needs to download less JavaScript™ code, because it won’t need the algorithm code, and this reduces the initial loading time of the application. On the other hand, the execution on the server requires passing the graph description, serialized in JavaScript Object Notation (JSON), between the mobile client and the server, and this can be slow with a GSM connection. Either the client-side or the server-side will fit better, depending on the size or speed characteristics of the graph, layout algorithm, mobile device and network. Dojo Diagrammer provides both solutions to give you the freedom to use the one that is the most appropriate for each case.
Figure 2. Example of graph layout application tailored for a mobile device using a local view of an orgchart
Figure 2. Example of graph layout application tailored for a mobile device using a local view of an orgchart

Resources

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into WebSphere on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=WebSphere, Cloud computing, DevOps
ArticleID=758499
ArticleTitle=Innovations within reach: The parameters that matter most for creating interactive diagrams on mobile devices
publish-date=09212011