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!