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!
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!
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!
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 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!
So another long delay to an update, so what's been going on?
Primitives
Sadly, no good news here. The primitives work, which intended to reduce the number of levels in a graph and as such, reduce the runtime required for approximating global repulsive forces has had little impact. This is primarily down to primitives only being identified too late on in the coarsening phase (when graphs only consist of 100 or fewer vertices). As a result, the time saved generating this layout is insignificant - and with limits on the extent of approximations, there is no real use for this approach unless a primitive with thousands of vertices is identified.
So, this is apparently a no-go.
Leaf Coarsening
A little better news but still not amazing. The leaf coarsening works as expected, with most graphs being unaffected by the approach, and those graphs which do have leaves in their structure, coming back with reduced runtime (for example, add32 is given a layout in 15% less time).
The layout however, although higher in the number of edge crossings, makes changes more available to users. Leaves are currently laid out using the centroid of the graph to push them outwards (separated by small differences if coincident), however, a technique using a "cone of freedom" allows for multiple coincident vertices to be displayed evenly around an anchoring vertex or between other edges, giving them more freedom to escape repulsive forces and to be displayed as the user requires (through changing the angle of separation between them). Though the technique is not perfected and is more specific to tree and star type graphs, the approach is relatively simple and can provide a more contextual layout.
But unfortunately again, this is no real benefit to general graph drawing and is just a mechanism than only optimises the MGF structure when applicable.
Multimatching
Another disappointment - grouping more than 2 vertices was expected to reduce the number of levels in the multilevel scheme (and MGF tree) making for a faster and more efficient approximation which closer resembles the structure of the quadtree. The results say... sometimes, but each graph has a "preferred" matching number which is cannot be identified without checking each matching number individually (a long process). This essentially rules out multi-matching as a standard mechanism to improve the algorithm.
Summary of MGF Optimisation through Coarsening
Only the leaf coarsening has any promise - and the promise is not particularly linked to general graphs. The primitives layout is only useful for smaller graphs that require perfect layout, and even then, FDP offers competitive speeds. Multimatching backs up the use of matching only singular edges (two vertices), higher matching numbers provide an increase in levels (in general) and an increase in runtime.
Spring Embedder without Cooling Schedule
Previously I have complained that the Fruchterman and Reingold cooling schedule does not meet my demands, and as such, does not bode well for dynamic graph drawing (thus everyone uses Eades spring embedder or similar). The problem comes from the large movement in the beginning of the cooling schedule, and the stopping when the tolerance is met (as the cooling schedule acts as a limit on the number of iterations). Removing such limitation and allowing the algorithm to run indefinitely does not provide good layout as the large movements are never restricted.
Well, finally some good-ish news. Thanks to implementations of the modified spring embedder on GPU's, there is a cooling schedule which allows for continious layout generation without stopping limits, without the erratic movement and with (relatively) good layout. The approach uses two cooling schedules and treats the movement of the two forces seperately (as opposed to one singular movement). After a quick implementation, the layout is achieved smoothly and nicely, albeit with much more noticeable peripheral effect. Hopefully, this discovery will aid my design of the relative dynamic algorithm.
The modified spring embedder without cooling schedule showing the erratic movement as repulsive and attractive forces continually fight each other. The graph drawing is a thee dimensional 7x7x7 vertex grid. No multilevel scheme is used.
The modified spring embedder with two cooling schemes. The erratic movement disappears and allows for continuous layout generation (a layout is achieved and does not change). Unfortunately, as the cooling schedule has not yet been fitted to my own algorithm, the graph expands to a much larger size than required. The same 7x7x7 grid is drawn. Unfortunately, this approach is much slower than the single cooling schedule as it takes longer for vertices to pass out of local minima.
Current Dynamic Framework
Some progress in the dynamic framework. Mechanisms and data structures have been prepared for changes to a graph and updating the layout periodically has been achieved. In the video below you can view the graph 55grid (3025, a 55x55 vertex grid) having vertices removed and the layout updating to show these changes. The structure/mental map of the graph remains until nearly 75% of all edges are removed.
The erratic movement after the layout is updated comes from the cooling schedule as mentioned above. I am currently implementing the new approach to smoothen this out and so the redrawn layout does not have to be requested but is visualised immediately. An alternate and possible faster approach has been suggested by my supervisor which would be to only show the stages of layout generation where vertex movement is below some tolerance - making the image and changes much smoother.
