Graph Layout Algorithms

Graph Layout

We use the term graph broadly to denote a diagram consisting of a set of nodes (also called vertices), and a set of edges, where each edge connects two nodes. Such diagrams are useful in a wide range of applications such as network maps, organizational charts, flowcharts, UML diagrams or electrical circuits, to name just a few. The shapes and characteristics of the nodes and edges can vary according to the application.

The purpose of automatic graph layout is to use an algorithm or semi-automatic method to determine the positions of the nodes and edges so that the result will be visually appealing and give the most useful information to the viewer. What constitutes a good layout is highly dependent on the application domain and intended use of the diagram, and also on subjective factors such as personal taste.

Layouts in InfiView

InfiView provides a number of layout algorithms. The layouts are designed with flexibility and extensibility in mind, so that they can be used as building blocks for applications. There are basically two different classes of layouts: those that are meant for trees, and those that work with general graphs.

Regarding trees, the following are provided:

The following layout apply to general graphs:

TreeLayout

The TreeLayout produces a hierarchical drawing of a rooted tree.

TreeLayout

WedgeTreeLayout

This layout places subtrees in separate sectors (wedges) around the parent vertex in a circular fashion. The angular width of the sectors is assigned according to the sizes of the subtrees.

WedgeTreeLayout

BalloonTreeLayout

The BalloonTreeLayout places subtrees in circles around the parent node in a balloon-like fashion.

BalloonTreeLayout

Iterators

The layout algorithms use the concept of an iterator to represent the graphs. The general idea is that each vertex (node) of a graph is iterable, and provides an iterator that yields its neighboring vertices (the adjacency list). This architecture allows the application developer to leverage all the power and flexibility of the iterator pattern and other concepts from functional programming.

InfiView uses the MochiKit library for the iterator implementation. Please refer to its documentation at http://mochikit.com for more information.

The Vertex interface

The layout algorithms are not tied to the InfiView node and edge classes, but rather work with any node objects that support the Vertex interface. The InfiView nodes support this interface out of the box, and can thus be used directly in the layout algorithms. By implementing the Vertex interface yourself, you can apply layout algorithms to arbitrary application objects, such as Bindows components. You can also choose to implement this interface even for InfiView nodes if you need special behavior.

The code below shows a skeleton for a Vertex class:


Vertex = function()
{
    // The adjacency list
    this.neighbors = [];
};

_p = Vertex.prototype;

// Called by the layout algorithm to position the vertex.
_p.setLocation = function(x,y)
{
    // ...
};

// The dimensions of the node.
_p.getWidth = _p.getHeight = function()
{
    return 16;
}

// Returns the adjacency list (can be an array or an iterator).
_p.getAdjacencyList = function()
{
    return this.neighbors;
};

// Returns an iterator for the adjacency list.
_p.iter = function()
{
    return MochiKit.Iter.iter(this.neighbors);
};

Now you can apply a layout algorithm to the class defined above. The code below shows a skeleton for a Vertex class.


var root = new Vertex();
// create some more vertices
var layout = new infiview.WedgeTreeLayout();
layout.layout(root, 0, 0);

Note that the Vertex class has two methods that return the adjacency list: iter() must return an iterator, whereas getAdjacencyList() may return either an iterator or an array of vertices. Returning an array improves performance in some cases.

Try the Samples