Visualization

Requirements

This Graph Visualization control was developed for a project at Pacific Northwest National Laboratory. The requirements were:

GDI+ was considered for this project, but it would not be the optimal choice for the last requirement. Instead, I chose to use JavaScript to draw the graph, using <div> tags as nodes. This enabled a great deal of flexibility, allowed some DHTML elements to be used, and would later allow the graphing package to be modified to enable interactivity.

How it works (frontend)

The graph visualization is built entirely in JavaScript. All that is required to create a graph is the canvas div tags (a node canvas and a graphics canvas), a div for an info popup, and some calls to the visualization object that look something like this: Vis.Nodes.push(New VisNode(id,name,style)); Vis.addRelationship(parent,child); Vis.draw(); So, just a few lines of code: Vis.Nodes.push(New VisNode(1,'1','COMPLETE')); Vis.Nodes.push(New VisNode(2,'2','GHOST')); Vis.Nodes.push(New VisNode(3,'3','')); Vis.addRelationship(1,2); Vis.addRelationship(2,3); Vis.draw() can create a graph like this:

Visualization

Almost all of the logic is within the draw() function and its helper functions. The draw() function works something like this: function draw() { calculateNodeDepths(); addPathways(); // See "Problems" below positionAndSizeNodes(); drawLines(); // Also draws arrowheads - see "Problems" below } These functions operate on VisNode objects, which themselves manage their node's data, page element and events that operate on their page element.

How it works (backend)

Everything is wrapped up in one user control. This user control contains the required page elements, generates the appropriate JavaScript, and includes the required JavaScript libraries and CSS files. Using the standard data-access method (obtain data from the project's web service), all that is required is a graph id and the control will do the rest. In other words, the following line of ASP.NET code is all that is required to draw a graph: <uc:VisControl ID="Graph" GraphId="1021" runat="server" /> This can even be accomplished by dragging-and-dropping the control into the Visual Studio .NET Design view for a web page - no coding required.

The control obtains its data from a set of classes within the Graph.Visualization namespace. The control creates an instance of the Graph class with the GraphId, which the Graph class uses to poll the web service for information about that graph. It uses this information to construct a collection of Nodes and Relationships. The control then uses this information to generate the JavaScript code required to create the graph.

Customization

Data source

Using a data source other than the web service is easy. All that is required is changing the constructors for the Graph and Node classes. In fact, since Properties are used to access all of the graph data, as long as the Properties are accessible, the classes can be changed in any way.

Style

The graph's stylesheet is organized to make it simple to change the basic styling of the graph. Customizable visual styles (such as canvas size, colors and borders) are all located at the top of the stylesheet while important styles (such as display mode, overflow handling, floating and z-indexing) are all placed below a comment line that says "Changes made below this line may break the graphing control." Additionally, visual styles are grouped intelligently, so changing something like the border color on the canvas will also change the border color of the nodes, key, and key items. In other words, by changing a couple lines of the stylesheet, a graph like this could be created:

Visualization

This makes it easy to integrate the Graph Visualization control into many different projects, each with different styles.

Problems

Overlapping lines and edges

The original graphing algorithm (the same as above, sans the addPathways() function) had problems with overlapping nodes and edges, since it is possible for a node to be both a parent and a grandparent of another node. For example, in the above graph, if node 1 was also a parent of node 3, where would the path to node 3 be drawn? In the original algorithm, all lines were drawn completely straight, and since lines exist on a layer below the nodes, it was impossible to tell if a line was following the path 1->2->3, or if it was following 1->2 and 1->3. This was even more of a problem because arrowheads weren't drawn at the time the issue was encountered.

To solve this problem, I read several research papers on the subject of visualizing graphs. Many of them covered crossing minimization (which didn't help), but a paper by Tom Germano entitled Graph Drawing had a picture that solved my problem. Essentially, the solution was to insert "waypoint" nodes at every level between a parent and a child. The line would follow these nodes between the parent and child node. These nodes would add an invisible block the size of a node through which a line could pass, avoiding other nodes at the same level.

This simple change turned a graph that looked like this:

Visualization

into this:

Visualization

It is much easier to interpret the relationships in the second graph since lines don't pass through nodes.

Arrowheads

Originally, the graph had no arrowheads. I was asked to add arrowheads to reinforce the left-to-right direction of the graph. After some work trying to figure out the math behind how to position points in a triangle to form an arrowhead, I decided instead to use a Rotation Transformation. I decided to draw an arrowhead pointing straight up, and then used the transformation to rotate it around the base of the arrowhead. I then translated (moved) the arrowhead to the correct point on the line. This graphics technique saved me a lot of time and energy, and produced great-looking results.