Multilevel Global Force Relative Motion Graph Drawing is a go

Last post I mentioned regarded my implementation of the Multilevel Global Force Relative Motion Graph Drawing algorithm (no idea why it's now called that but until a better name comes up, it'' have to do). This week I have improved upon the implementation and fixed the NaN bug which has plagued it.

The NaN errors, as expected, came from division by zero. Due to the way in which forces are calculated (repulsive forces are not calculated for vertices connected by springs), a graph with only one edge will inevitably have zero repulsive forces acting upon it. When calculating vertex displacement, this causes division by zero and so ruins the game.

Why hasn't this come up before? Well, previously we have only used one cooling schedule (that described by Davidson and Harel) and as such, spring and repulsive forces are combined (so even if one is zero, the other will inevitably have a value). Moving to the smooth FR algorithm splits them so if one of the forces is zero, NaN begins its takeover. It's stressed that this only occurs in graphs with only two vertices and one edge, meaning only one force is calculated.

Anyway, moving on, the algorithm now works and shows massive speed improvement from brute force and multilevel approaches. Some graphs exhibit the structures you would generally see in static graph drawing and global layout is often achieved after some period of time. Due to the dual cooling schedule and instant visualisation, this takes much longer than with static graph drawing.

Changing the algorithm to use single cooling schedule but still retain the real time visualisation, you would expect to see good layout in much shorter time (but with more erratic vertex movement). However, this is not the case, as each iteration finds layout for the entire graph, and inevitably, the cooling schedule finishes before a low energy layout is found.

In any case, there are some bugs still observed in the drawing (for example, the graph drifting out of the viewing area and some vertices unable to move from their position) which require fixing, and of course, combining the operations framework with the algorithm so that we can begin analysis of dynamic matching. But, we are now seeing a working algorithm similar to Veldhuizens using techniques already present in the graph drawing literature (no fancy dynamics as such), so yay for us.

That's all for now as its Friday and I need a drink... catch you next time!