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.
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.
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.