Programmatic Rendering of Directed, Weighted Graphs

An algorithm for producing SVG drawings of directed, weighted graphs will be presented. In particular, the focus is on weight functions that satisfy flow conservation: the sum of the incoming weights equals the sum of the outgoing weights at all nodes except sources and sinks. Such a graph is particularly appropriate for representing flow through a system. Examples include traffic flow in a city, energy flow in a production plant, water flow through a network of pipes, Internet packet flow, the flow of money through a national economy, and so on.

Simple graph-rendering algorithms will often produce a confusing jumble of overlapping nodes or tangled edges on any but the smallest data sets. The challenge lies in producing an algorithm that renders the graphs in a legible and complete manner for a wide range of typical input. All information including weights must be visually represented, accessible and clearly conveyed. We were able to meet this challenge head-on after imposing the following two practical constraints:

  1. We restrict our attention to the practical problem of directed, weighted graphs satisfying flow conservation.
  2. The layout is constrained by an additional input: an ordered partition on the set of nodes. This additional information permits classification of nodes into conceptual stages in the flow.

In fact, we will demonstrate a graphical stylesheet that can generate interactive and attractive SVG representations automatically.

We begin by discussing an intuitive representation of a directed, weighted graph known as a Sankey diagram by its originator Sebastian Moffatt of Propolis Information Technologies, Inc. This diagram uses line thickness to represent the weight of an edge. Edges are rounded, rather than straight, for two reasons: first, rounded edges are more suggestive of real systems that transmit flow, and second, rounded edges are more aesthetically pleasing than hard angles. The diagrams are arranged linearly. Source nodes are placed near the top, and sinks appear near the bottom. Finally, since these graphs are intended to model real systems, each node has a space for a caption.

There are many problems to overcome in rendering such a graph. If an edge has thickness, it will obscure what is behind it. Therefore, the possibility of thicker edges completely obscuring thinner edges must be avoided somehow. Also, if a node has a caption, the caption must be visible at all times assuming reasonable constraints on its string length. Finally, although perfectly rounded edges are aesthetically pleasing, they can be quite challenging to render. However, all these challenges can be overcome, and this presentation will demonstrate a graphical stylesheet that produces nice SVG diagrams automatically from raw XML data.

SVG provides a number of unique advantages as a target format for rendering Sankey diagrams. To begin with, the scalability is particularly useful when dealing with large diagrams.

Secondly, the generated SVG contains interactive ECMAScript bindings which highlight edges in response to mouseover events, enhancing the impact of the diagrams. For further emphasis, the selected edge is moved to the front via re-ordering of DOM nodes. With this interactivity, the diagrams are much more accessible and effective than their paper- only counterparts. Nevertheless, the bindings do not prevent the diagrams from being committed to paper when necessary.

A third advantage is the fact that SVG is XML. This makes it an appropriate target for XSLT, and our implementation of the algorithm is done entirely with functional programming in XSLT 1.0, without any external bindings. Although there are many resulting benefits such as cross-platform code and the flexibility to run the XSLT on server or client, there were also some serious challenges in doing graph layout with XSLT. Calculating parameters such as the bounds of the graph and scaling factors requires logic that can consider the entire domain of source data in sequence, and this had to be done without the help of global variables to store the information.

The diagrams themselves are quite rich, consisting of graphical constructions that make full use of the powerful features of SVG but are not intrinsic SVG primitives themselves. As a result, nontrivial geometric manipulations must be performed at the transformation stage, and these manipulations will also be discussed. A key element of our algorithm is the calculation of smooth, rounded tube boundaries with the correct radii of curvature to optimally route the represented edge. This computation required some theoretically simple, but clever, geometry.

Finally, the practical use of the graphs will be discussed, including their application to resource management problems and opportunities for re-use in new and unrelated applications.

Dr. Philip A. Mansfield and Mr. Mark A. Ambachtsheer
SchemaSoft
#350 - 1190 Homer Street
Vancouver, BC  V6B 2X6
Canada
email: info@schemasoft.com
tel:   604-682-3404
fax:   604-682-3432
web:   http://www.schemasoft.com