The End!

Sad to say I am coming to the end of my research!

This sad news means I will soon be discontinuing the blog, and as such, a goodbye will be soon.

Having reached my writing up period about two months ago, I have spent the past weeks writing and running my experiments in order to provide enough evidence to defend my theoretical works. It also means I am now on the search for a job! Apparently this is a lot harder than it seems as postgraduate studies isn't really experience, nor is it graduate level work due to its specialism...

Anyhow, I am currently writing up! and my goodness is it boring... Writing about everything you known ten times over is not exactly enthralling, on the other hand, pretty pictures/layouts make it all worth while. So instead of boring you any longer, I've chosen to upload a few of the best over the past three years!

Is it a swan, is it a thing, what is it? I choose swan because I like birds. (It's actually a graph called data representing an aeronautical body but the drawing method drew it peculiarly).

A drawing of the graph 3elt, representing the airflow around an aerofoil, the layout itself doesn't follow drawings by other algorithms but shows the ability of MGF to draw "arms" of data. If only that "tongue" was better placed.

 The layout of add32, except different! The layout here was a result of my "primitive" research which tried to generate layout of star type graphs (one central vertex connected to all others). The layout didn't fare so well aesthetically but left an unusual look for the graph showing the connectivity of vertices. It seems one half is very connected, the other, very loosely connected.

Investigating unusual shapes of layouts, a 55x55 grid should be very square. This layout wasn't, and apparently the cause is the approximation of forces as part of the multilevel scheme (lay mans terms: the graph was split in two, and the different between the two caused the bulge you see as one side is bigger).

 Not exactly a different layout, in fact its very much what you would expect from a drawing algorithm. I just like how the components of the graph are clustered, showing the parts that made up "add32".

 The graph "finan521", normally visualised as a circle, the weakened repulsive forces generated a layout where the circle folded on itself. The smaller structures are also more flared than compared to other generated layouts.

 What I would consider a perfect layout of "4elt", with compression around the white spaces, avoiding overlap (note the "hole" on the left, which would otherwise have "excess" layout overlapping the surrounding layout, more extensively than the top of the hole). 

Pretty colours! A 55x55 grid with coloured partitioning. The layout itself is somehwhat warped as a result of the approximation of MGF, and the partitions are unequal (different sizes, see the red and pink partitions for difference). However, the ability to colour partitions is simple but important as a visualisation tool.

For now that is all! I will comment again with a final summary of all of my work once I am done with the writing up stage (or once I have completed my Viva). I hope you've enjoyed following my development from innocent undergraduate to specialised and scary postgraduate weirdo! 

For old times sake, a kitty;

Some interesting stuff with VisualMGF (and other tales of bad research)

Another two weeks gone by and what to I have to show for it? Well for starters I'm rather embarrassed, for you see my implementation of "Visual MGF" does not quite work as planned, to such an extent I am genuinely surprised it does what it does at all.

So what disastrous discovery comes this week? For several months it has been explained to my supervisors that the value of k (ideal edge length) for different levels of the multilevel scheme is appropriate following the research in static graph drawing. Technically, this is true and it was expected that the movement between levels (when using the dynamic drawing algorithm) was fine due to the speed at which layout is generated in comparison to a pure multilevel approach.

Well... I am partially wrong. The value itself is fine, my interpolation of layout, not so much. During one iteration of the VisualMGF cycle, each level of the multilevel scheme has force directed placement applied to it once, passing the displacement of vertices to their children in finer graphs (with some small difference to avoid singularities), for the sake of names we call this Cycle A (for Awesome). When the finest graph has layout applied, the algorithm runs in reverse, updating the parent vertices in coarser levels with the averaged layout of their finer children (in order to overcome inaccurate approximations which cause compression in the layout), named Cycle B (for B*****ks). These two update cycles do not work well together, in fact, Cycle A is relatively useless and only aids in expansion of the graph. As Cycle B updates vertices, the layout of the finer graphs is completely re-written to form a coarser layout of the original graph (which at this point can be considered bad layout). 

So how do I get "good" layouts? The MGF Approximation structure maintains approximation of vertex positions and continues to use these to overcome minima. Although this leads to problems with minima (both global and local), the layouts inevitably end up rather appreciable after some time. Removing the extra calculations of applying VisualMGF to the coarser levels (only applying to the original graph) proves that layout in coarser graphs is irrelevant - and provides a noticeable improvement in time required to find layout.

Initially I thought this would only be a problem with the VisualMGF algorithm but it appears to have a worse effect in the standard VisualML (visual multilevel only). Although displacement in the finer graphs is applied, and a good layout can be applied in coarser levels, the layout in the finer levels contradicts the coarser layout and so does not find a good layout so easily (if at all).

So... it seems Veldhuizen does have some tricks up his sleeve which requires yet another revisit to his publication in dynamic graph drawing. So the trick now is to once again identify a method of achieving global layout appropriately, but having used the multilevel scheme already for approximation, what comes next? a multi multilevel scheme? How deep does this rabbit hole go?

My assumptions were wrong? So much surprise...

So following on from the development of the Visual MGF framework, I have spent the past 3 days playing with investigating the abilities of the application and how much I can change, and inevitably, how does whatever I change affect the layouts of the graphs.

The biggest changes so far come from adding variables to give priority to one of the cooling schedules (to either repulsive or attractive forces). Changing this has allowed me to find some preliminary values which provide good global layout more often for most graphs (a problem described in previous posts). The bad global layout had to be for a reason though (treating the symptoms is only one thing), so investigation led me to think "lets spice the pretty pictures up with some colour".

So, a few hours later, here I am with the ability to colour the graphs, highlighting each of the matchings of vertices. So highlighting the two collections of vertices which make the coarsest graph, gives the following picture (for the graph 55grid/3025).

Notice that one of the "partitions" is much larger than the other, this sometimes happens due to the random nature of the matching process. You may also notice the crease in the layout between the two collections - interestingly this has been observed previously when I first implemented Walshaws multilevel with standard grid approximation, and shows that the global repulsive force is not pushing the two collections apart (and as such, the two collections overrun and crease). This suggests either changing the value of the spring length (k) to something more appropriate or copying the fix on the previous work and changing the strength of repulsive forces.

Either way, that is only slightly interesting. The more interesting, and sadly more disturbing news comes from observing some of the matchings that occur. The following image shows matchings on the same graph but in at a different (coarser) level in the multilevel scheme.

The image shows that some matchings include a large number of vertices stretching out across the graph. Previously I have made the assumption that matching connected vertices means the graph should be matched into reasonably uniform partitions. Apparently, this is not the case, and as such, the global layout is often skewed so that the larger partitions occupy more space than others.

This is due to abandoning the priority given to lesser connected vertices. Changing this should provide more appropriate partitions and generate a more uniform global layout. Shows the use of this blog, I only just thought of that as being a problem - might have ignored it otherwise, so thank you blogger!

Videos, just because.

Last post I discussed my progress with the visualisation of the MGF FDP algorithm. Now that some of the kinks have been ironed out - here's some videos of it in action.

3elt drawn using visual MGF FDP. Much of the layout is found relatively quickly in the first few seconds, however, global layout takes much longer, and due to the dual cooling schedules used to smooth vertex movement, the algorithm takes much longer than static drawing algorithms.

3025, the 55x55 grid given layout using MGF FDP. The video shows difficulty finding global layout due to the changes to the cooling schedule. This occurs in many of the drawings encountered suggesting a problem with the current algorithm as discussed further below.

3025 again, however, global layout is somewhat achieved. Unfortunately a group of vertices appears to get "stuck" in the layout. Normally, the forces would pull this grouping outwards and converge to a good layout, however, the vertices remain in this position, ignoring much of the forces. As mentioned above, global layout is not always achieved, and when coupled with this behaviour (which occurs in other graphs too), suggests a problem with the FDP (or interpolation of layout). The root of the cause is yet to be identified, but it wouldn't be fun if it were easy right?

Same algorithm, different graph. This time 4elt is the guinea pig, and with the problems of global layout given above, the entire drawing process is not visualised. Instead, the algorithm was left running for 10minutes in order to determine if larger graphs can be given layout that matches their static counterparts. The answer? very much a yes. As the video shows, the layout is very much comparable to 3D static drawings.

As the size of a graph becomes bigger however, the time taken to perform one iteration of FDP increases and so the visualisation is no longer smooth, with a noticeable delay between placement of vertices. However, in comparison to the videos presented in Veldhuizens work, the speed is equivalent, if not better. Further decrease in FDP runtime would therefore come from further optimisation techniques.

Visualisation of layout generation is good but not even half of the story. The other half is operations, which have previously been shown in other videos (which showed how terrible it is to apply the Fruchterman and Reingold algorithm to a layout after changes have been made - the oscillation from the cooling schedule is not a particularly pleasing attribute). So without further ado, the video below shows changes to a 20x20 grid having been given a layout (sorry, forgot to record the layout generation). The changes turn the grid into a tube like structure through the addition of edges (similar to an example given in Veldhuizens work), and then returning to its original structure by their removal.

The layout generated for the graph is initially quite good (some uniformity issues but nothing too drastic), however, as the edges are introduced, the middle of the graph/tube tends to be more affected by expansion, causing it to bow. Although not the best or smoothest layout, possibly due to no changes to the MGF structure, the operations perform their task in connecting distant parts of a graph and bringing them closer to one another in the layout.

Lots of stuff to refine and check but some progress appears to be made. Anyway, pretty videos, enjoy!

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!

"I feel a little better..."

Good news and bad news!

Good news, I'm in a happy mood. Also, I have managed to get the "smooth" Fuchterman and Reingold spring embedder to work with the multilevel scheme (mentioned previously and used to visualise the placement of vertices in a smooth fashion similar to Eades). Even luckier, I have managed to get it working with the MGF approximation - so much so that we can semi-visualise the layout being given to graphs as big as 4elt.

Now the bad news, there is only a 5% chance of it working due to some unknown issues generating positions which are NaN. Previously a problem with the distance between them being zero but it doesn't appear to be the cause here, so that's for me to investigate further. As always, there's some bug in there that is waiting for my attention.

Now the tricky part, the visualisations observed this far show the generation of good local layout but lacking in the global layout side of things (see the image below - when visualised this was moving but had slowed so much that it was unlikely to find a good global layout). The reason? the cooling schedule is great for smooth visualisation but makes generation of layout much longer as we wait for it to overcome all the local minima. This just gave me an idea to try with the original Frucherman and Reingold algorithm and see how that works out.

So the aim now? fix this damn NaN problem. After? play around with the visualisation, see if it can be improved and then get on with testing the dynamic matching stuff. For now, that's all I want to say until it works appropriately, so I'll keep you up to date, enjoy your Wednesday!

Another paper, luck requested!

Another rather late post to add to the collection of sparser and sparser updates.

So what have I been up to? Another conference paper! This time for the prestigious Graph Drawing conference, which is a rather big and intimidating deal. Unfortunately, the work submitted is only an addition and not the dynamic stuff we've been working on - but I guess that's what happens when you leave the big bits to the last minute.

So the work - leaf processing! We have successfully proven that processing edges in a graph reduces runtime due to the smaller graph size, and when using MGF approximation, reduced depth of the coarsening scheme (resulting in less approximations). We also suggest a simple Leaf Placement Algorithm for the layout of these vertices without the use of iteration (no FDP for you!). Unfortunately the LPA does increase the number of edge crossings somewhat, as the placement only accounts for the centre of mass and not for other nearby vertices, but this can be changed by implementing different algorithms. The concept is that we can control the layout of leafy vertices with ease - and by doing some simple preprocessing, can reduce the runtime required to generate layout for leafy graphs.

For more information you'll have to wait and see if the paper is accepted (mostly because I dont want to jinx it).

Anyway, moving on, what's next? The Dynamic stuff!! hurrah! We have the changes and operations currently implements (may not be optimised but they do their duty) and the framework for altering the coarsening scheme after these changes exists (but has not been tested so who knows what bugs are waiting for me there). More importantly, the cooling schedule mentioned in the previous post is implemented, so now its time to port that to the multilevel algorithms, so we can speed up the drawing.

A plan has been developed on scraps of paper scattered across the 5 corners of the world, and the code has been prepared in a special ceremony - so I guess now its down to me. Let us begin. I will update again in the future with a progress report. So luck be with me!