Now where was I?

Rejoice! I have managed to get (almost) back to where I was before the Monday incident. I say almost, I have not yet fully implemented Fruchterman and Reingolds force equations, as opposed to the Eades equations I've been using, however, everything else appears to be working smoothly.

Currently, I am trying to create a "nice" way for the multilevel algorithm to know when to stop coarsening a graph. I'm aware in most cases you could say "when |V| is equal to some designated size", however, what I have observed during some testing (specifically when coarsening add20.graph from Dr. Chris Walshaw's Graph Partitioning Archive here), is that coarsening a graph may result in a "star" type graph where all vertices are connected by a single edge to the centre vertex, making it difficult to coarsen further.

These graphs are typical in social network structures, and can be better coarsened by clumping a number of vertices at once. At the moment, however, I am only looking to identify when such a graph is created in coarsening, so I can stop the coarsening at a level which holds useful information (constantly coarsening a graph of 500vertices, where coarsening only collapses two vertices, isn't very useful). I will most likely include the feature mentioned before at a later date so I can compare results.

Alternatively, I have yet to implement a "working" weight based coarsening, which could solve the issue. This does not avoid the fact that star-like graphs will eventually turn up somewhere, and will need to be dealt with. Walshaw mentions in his paper how the multilevel  and FDP paradigms could be used to draw and explore social network structures.

In other news, for my own enjoyment, I have been testing the coarsening part of the algorithm on larger graphs (x10^5+) to get an idea of runtime. I am looking to have results for my Eades equations on Multilevel before the end of the week (with edge-crossings counted, because YAY! my edges now coarsen correctly!!!).

I will hopefully update on Friday. All the best!