Many types of complex business data can best be visualized as a set of nodes and interconnecting links, more commonly called a graph or a diagram. Examples of graphs include business organization charts, workflow diagrams, telecom network displays, and genealogical trees. The mathematical concept of graphs is so general that it is used as a modeling tool in almost any domain. When we need to get a visual understanding of the graph data, there is a need for the automatic visualization of graphs. The purpose is to optimize the display by obeying common rules in a given field and by maximizing the readability.
Among the new visualization components included in the WebSphere Application Server Feature Pack for Web 2.0 & Mobile v1.1, Dojo Diagrammer allows applications to display and edit graphs (diagrams)and provides a comprehensive set of graph layout algorithms for the automaticplacement of the nodes and/or to ensure the links have optimal shapes.
Now, we may wonder: with automatic arrangement of diagrams, humans, that isdevelopers or end-users, have no role to play anymore? Well, there is stillplace for humans taking decisions... The following decisions are in the handsof the developer (if appropriate, the developer can offer these choices to theend-user thanks to configuration GUI):
- The choice of the graph layout algorithm among those available: Hierarchical, Tree, Force-Directed, Circular, Grid, Short and Long Link layouts (the framework also allows you to develop your own custom algorithm).
- The configuration of each graph layout algorithm, thanks to a wide range of options to fine-tune the display according to specific needs or taste.
The present post focuses on the first point: how to choose the graph layoutalgorithm that fits better. In some cases, this choice is quitestraight-forward, in other cases it is a bit trickier, and to guide your choiceyou can find below a short synthesis of information present at various placesin the Feature Pack documentation (Reference Manual and Infocenter), enrichedwith additional hints.
This algo organizes the nodes in horizontal or vertical levels, in such away that the majority of the links flow uniformly in the same direction. Typical examples:
This algo is the obvious choice for representing hierarchies, that is forhierarchically-structured data (graphs) such as process flows, workflowdiagrams, and so on. The key point about the data is whether the links(connections between nodes) are oriented, that is whether the directionof the link matters. If it matters, it is very likely that Hierarchical layoutfits (however, in some cases the Tree layout might fit better, see below). Tree layout
The obvious choice for representing trees (such as organization charts),where each node has one single ancestor. Typical examples:
The Tree layout can also be used if the graph is not a (pure) tree, howeverin this case it only takes care of the shape of part of the links, those thatcontribute to the pure tree part of the graph, the so-called "spanningtree" of the graph.
Your graph does not represent a hierarchy, is not a tree and the orientationof links does not matter? Then Force-Directed layout is likely to fit. An example: This algo is slower than Hierarchical or Tree layouts, therefore it is notrecommended for very large graphs.
The Circular Layout is mostly designed for Telecom applications where nodes arepartitioned into clusters. The clusters are displayed as rings or stars andpositioned in a radial tree-like fashion. An example:
In most Telecom applications, the nodes represent network devices that have predefinedcluster ids. Hence, the layout algorithm allows specifying the clusters as inputdata. For cases when no cluster ids are available, the layout algorithm is alsoable to automatically calculate appropriate clusters from the graph topology.
Obvious choice when your graph has no links, or you want nodes to be placedon a grid or matrix while ignoring the links. An example:
Short and Long link layout
Both are pure link layouts, that is they do not move the nodes, they onlyreshape the links in such a way that crossings and overlaps are reduced oravoided. But why two different algos, Short link layout and Long link layout?The answer is that they have different (mostly complementary) characteristics,and, depending on the case, one or the other provides results that fit betterthe aesthetic and performance requirements. How to choose one or the other? Thedumb rule is to try any of them; if it does not fit, try the other one (andexplore the multiple options of each).
That said, it is also useful to be aware of some characteristics of each,which help making the choice. In very brief, the names "Short Linklayout" and "Long Link layout" refer to the fact that the firstone fits better when most links are "short", that is they interconnectrelatively close nodes, without too many other nodes placed as obstacles thatwould need to be avoided by the path of the link. It is the converse for"Long Link layout": it usually fits better when links connect distantnodes with many obstacles in-between.
A more in-depth comparison follows:
Short link layout
- Links are placed freely in the space.
- Link-to-link and link-to-node crossings are reduced, if this is possible with link shapes that have a maximum of 4 bends.
- Crossing and overlapping of links with other links and nodes cannot always be avoided because the algorithm uses link shapes with a limited number of bends. This happens in particular when there are many obstacles between the end points of a link.
- Links of different width are supported.
- Link bundles between the same pair of nodes are supported. Optionally, the algorithm can ensure that multiple links are bundled together by giving them parallel shapes.
- Fast algorithm with low memory footprint.
Long link layout
- Links are placed on a grid.
- Link-to-node crossings of orthogonal links are avoided, even if this introduces many bends.
- Overlapping of nodes and links is always avoided, while link crossing cannot always be avoided.
- Slower and uses more memory depending on how small is the grid spacing.
The two screenshots above hold for the same graph data. At a quick look, theresults of the two link layouts are relatively equivalent, but at a closerlook, they differ in terms of link-link crossings, link-node overlaps, symmetryof connection points with respect to the node box, number of link bends (howmany turns). Each of these two link layout algorithms is useful in various use-casesand for various application requirements.
All layout algorithms can be applied to nested graphs, that is graphs with nodes that contain another graph. Most often, the best results for such graphs are obtained using the Hierarchical layout.
For the Business Process applications, Dojo Diagrammer also provides support for a special case of nested graphs, called swimlanes. An example:
Finally, all layout algorithms are provided with many configuration parametersto cover a wide range of needs. As a quick guidance, a future publication will providehints about the parameters that matter the most and their impact onperformance, in particular for the deployment on mobile devices. Stay tuned...
Dojo Diagrammer offers many other features, be sure to check the showcase sample that comes with the WebSphere Application Server Feature Pack for Web 2.0 & Mobile v1.1. You can install the showcase on your local server after downloading the Feature Pack (here are direct links to the installation instructions for WAS 8.0 and WAS 7.0). There is also an online version of the showcase here, which includes the live versions of the following graph layout samples: Graph Layout Browser, Organization Chart, Business Process Diagram, Graph Layout Explorer, Client-side Graph Layout for Mobile, and Server-side Graph Layout for Mobile.