Summary - a graph layout engine, a computationally complex problem, running entirely within a web browser without the use of plug-ins of any kind.
- Complex algorithm development based on published literature with novel additions.
- Cross compilation from Java to Javascript, complex CSS and cross-browser compatibility testing.
Graphs, in the sense of partially ordered sets, are common data structures in various computer science problems. In this particular case the graph was used to visualize the dependencies between different issues in an issue tracking system. The system in question was web based, and the potential load of multiple simultaneous connected clients performing server-side visualization of these graphs was a concern with respect to performance. The solution was to off-load the computationally intensive layout problem to the web browser; modern computers generally have an excess of capacity especially when used to access web based services.
Coding for a web browser means writing Javascript, but the process of testing and debugging Javascript code across the spectrum of modern browsers is an onerous one. At the time the Google Web Toolkit, a framework for cross-compilation of Java to Javascript, was becomming a more and more compelling option for such cases, especially as it has the ability to compile slightly different versions of the code optimized for each browser target.
The actual layout engine was coded based on a modified form of the 'dot' algorithm from the GraphViz software package. This meant reading up on the academic literature, and in some cases downloading and stepping through the rather terse C source code to clarify points where the papers were ambiguous. Graph layout is a complex process and outside the scope of this summmary, but the eventual algorithm I created was a hybrid of the crossing reduction from 'dot' and a custom heuristic based algorithm for node placement with a focus on preservation of vertical edges where possible.
The end result, running on one of the sample graphs from the 'dot' paper, can be seen by clicking on the demo tab above. A key element of the system is the ability to plug in arbitrary renderers for each node - in this case a simple composite div based rounded corner layout is used, but the intent for the original project was to embed live charts within each node to represent the progress of individual issues. As each node is a regular web page element there isn't really any limit to what could be used there - anything that could go anywhere else on a web page could work.
In total the code was around 10k lines of Java, and several hundred of CSS as well as a couple of sliced photoshop files to generate the images for the node components. Through GWT the compiled Javascript makes use of the HTML5 Canvas element where supported, and VML in Internet Explorer.