Going on and on

A rather late and lonely update this week.

For the past few days I have been working on upgrading and refining my own contraction approximation, and also the barnes hut quadtree; fiddling around with the forces and tweaking the output to give the best drawings. Unfortunately this has not worked for every graph, but I am able to retrieve relatively good layouts for many graphs.

Tangling appears to be my biggest issue thus far, with many graphs struggling to stretch out and instead, collapsing in on itself. This is normally an issue caused by the repulsive forces being too weak, however, it is not so easy with the use of a hierarchical tree to model the structure of the graph (forces are dependant on weights, and so increasing a force will have greater effect on "heavy" nodes). This is mostly global untangling, some local tangling has been found but only occurs in one area of the graph and panning out (like a messy gradient).

Investigation and experimentation continues as always, in an attempt to find a cure. Below is an image showing that forces for one graph may not have the same desired effect on another. The graph data, on the left, is drawn relatively accurately my contraction method, however, the forces used to not work with the graph 3elt which is shown compressed on the right below.



Another peculiar issue with the contraction is its drawings of smaller graphs, particularly those formed in the coarser levels of the multilevel paradigm. For instance, take the pictures below showing multiple levels of a graph.

The above image shows the 3 coarsest levels of a standard grid, which do not follow the pattern they should, seen below.

 

 The image below shows the same tangling in another coarse level of a grid (from the same set as above), and when turned, shows the grid is drawn only in 2D (but slanted in 3D for known unimportant reasons).

below is another image showing several levels of the same graph, suddenly expanding in the z direction. The confusing issue here is that it only starts expanding after a certain point, much like the z-axis problem exhibited in the Barnes Hut implementation previously.

This behaviour suggests that there is a bug in the code, much like the z-axis issue, which is stopping the z-directional forces until a build up causes it to finally expand. However, this still provides some good layouts for other compact graphs like data. Unfortunately large expansive graphs such as 4elt and 55grid suffer from this behaviour.

Investigation and experimentation is under way to find this bug and fix immediately.

Other issues with the Barnes Hut arose, whereby a graph would partition itself into two, and throw each other in opposite directions (much like two vertices) connected by a tube of edges. Unfortunately I did not get a screen shot of this and can no longer generate the same behaviour. It was resolved (for now) by altering the strength of forces.

This is all for now, I am supposedly moving back to Greenwich this weekend so that should be fun...

I will update again next week, hopefully with some measurable results. Have a good weekend!