User login

Weekly Report - 13/12/13

17

Dec

2013

As per discussing with Richard and Brendon, I aimed this week to produce a more fully connected version of the traceroute graph, for the purpose of visualising the networks represented by interconnected routes more accurately. I knew that in order to do this I needed to abandon my existing tree structure and instead represent the data as a graph, so I spent some time reading about drawing algorithms for directed graphs, which led me to reading further into hierarchical graphs, which appeared to be exactly what I was looking for. Hierarchical graphs are typically drawn according to Sugiyama's framework, which breaks the process down into 5 stages, each requiring the selection of an algorithm meeting the requirements of application.

Fortunately I came across a Javascript library called Dagre, which is used together with Graphlib to lay out coordinates for hierarchical graphs and usually with a rendering library such as D3 or JointJS to draw the graph. I wrote some quick rendering code to draw the graph to the Flotr canvas instead and it worked excellently, so I continued and quickly produced a desirable graph and mouseovers.

Of course, multiple stages of the layout process are NP-hard or NP-complete, so drawing these graphs is slow. Dagre would hang the browser for potentially several seconds before anything could be drawn to the canvas.

As such I investigated Javascript web workers (essentially threads, which work in the most recent browsers) and separated the data processing + layout step into a worker, resulting in a much more responsive experience, however the graph is now blank for a few seconds before the data processing catches up and draws something, which I would like to improve next week.