Quantum Particle Layout Generation with Plasma Dynamics

If that has ever been a title, the writer probably cried. Unfortunately, this post is about nothing as interesting (though comes from some interesting research into forces between atoms). The main point of this post - put some of my ideas down so I don't have to keep thinking over them.

• The problem: dynamic graph drawing is the changing and visualisation of a graph in interactive time (or as close to as possible)
• Most techniques for smaller graphs are derived from Eades and Sugiyamas work (essentially a Spring Embedder which outputs vertex positions to a plotter after each iteration)
• For small graphs, this works well because the vertex movement can be calculated between animation slides. Large graphs - not so lucky, the higher number of force calculations requires more time and cant be fit between animation slides
• In practice, instant changes to a graph are bad as the reader does not have enough time to follow what is happening - for smaller graphs (9cube) a time dilation of about 200ms per iteration is required, for larger graphs (55grid) FDP takes too long (and without Multilevel, the layout is awful anyway)
• Typical "easy" response from me would be to run MGF on a graph, and after a change (or collection of changes), reapply MGF, outputting the new layout to an additional time frame
• This doesn't quite work for two reasons - 1. takes too long (essentially generating an entirely new layout per time slice - so not really a time slice, more of an iterative layout thingy) 2. the vertices do not gradually move into new positions, and so between frames, there could be a very different graph
• You could alter the FDP technique to cut down the number of calculations required (as a good layout is already applied, it just needs to be altered), or even cut out all calculations in the multilevel scheme so only the final (original) graph is altered
• This brings us to the dynamic matching - how many levels before layout suffers during the coarsening process, similarly, how many levels required change as a result of FDP before the layout suffers 
• This suggests that inevitably, a layout will have to be generated for a large graph through typical static graph drawing techniques. Only the original graph is then a concern - until you wish to start updating the approximation structure (again dynamic matching)
• Can the levels still be used to approximate forces if the higher levels are not having their positions updated? How slow will this be to visualise?
• The dreaded cooling schedule - everything above is all well and good, however, visualisation of the cooling schedule in action shows large amounts of movement (oscillation of vertex positions) - Veldhuizen uses "damping" to reduce this effect, so its assumed we could do the same (assumed...)
• Considering the cooling schedule is so limiting, another approach would be to change this (that way we can really see whether MGF is better or worse than the Octree in terms of which converges first)

Cant really think of much more as I now have to change the printer ink (talk about interrupting a train of thought...) but I will no doubt update this list when I can think of more things. Good news though, this already answers a few of the questions I had for myself. 

Progress Something Something

It's been a while since my last post but hopefully that means I've been working hard. I say hopefully, I know whether I've been working hard or not, but its fun to keep the mystery alive.

So to cover my tracks, what have I been doing?

• Multilevel Global Force Approximation - this again? you betcha. Ever since the fiasco with the randomised matching I had problems with, I spent some time going back and checking everything was correct. I have now updated the model/algorithm and have begun testing various bits and pieces to ensure it works, and that the behaviour/results match my expectations from the theory. I also wanted to follow up on some old ideas while I had the chance.
  
• Random matching/coarsening - completed. I've run the linear matching for a selection of graphs and ten randomised counterparts and found that there are significant differences in the number of levels generated in the multilevel scheme, due to the algorithm being dependant on the order vertices are stored in. Using the same algorithm but randomly shuffling the vertices presents a more universal number of levels, proving to be the more reliable option. Analysis of the layouts is forthcoming, however there are limited resources available to run the tests.
  
• MGF Level Limit - during the generation of the Octree, the number of splits is capped at 13 following the implementation by Yifan Hu, making approximations faster by reducing the number of approximated force calculations (a shallower tree to traverse). Using similar logic, there is now a limit on the MGF depth (though this is controlled in FDP). Implemented, with testing of the value under-way.
  
• Coarsener Tolerance - similar to using primitives and multimatching, coarsener tolerance aims to reduce the number of levels with little difference between them. As a new level is generated, the number of vertices is expected to be smaller, if not, the coarsening phase stops. If the difference is small, i.e.  1 vertex, there will be a larger number of levels and will require more time to generate layout. The tolerance is used to limit this. Implemented, with testing of the value is under-way.
  
• Graph Theoretic Distance vs Weight - in MGF and Octree implementations, the weight of the approximated vertices are used to determine the strength of the repulsive force and provide a more accurate estimate. As an alternative, I wanted to provide a more realistic approximation using the graph theoretic distance between them, playing on a similar idea to the Kamada and Kawai method which states an imaginary spring exists between two distant vertices with a length equal to the graph theoretic distance between them. Testing has shown than a more uniform layout is generated which ignores much of the peripheral effect, suggesting the approximation is more realistic than using the weights (however, as discussed by Hu, this increases the "fluffiness" of a graph and so, increases the number of edge crossings). It is expected this matches a layout generated from an algorithm with no approximation but is yet to be proven.
  
• Scale testing - once again, but only to ensure no changes to the originally calculated values as a result of recent changes. Results this far have shown the default values remain the better in terms of runtime and quality. Some issues have arisen with the octree implementation and require the grid structure to be made larger to encompass the graph (higher scale values generate larger layouts which have been shown to push vertices outside of the bounds of the octree - would like to point out, not a problem with MGF! *smug grin*)
  
• Multimatching!
  
• Levels analysis - to ensure no more panicking, much of the coarsening and multilevel has been tested with some short analysis. No FDP is applied, but the number of levels and the degree at each level has been analysed to show the behaviour of the algorithm. The plan was to identify why finan512 coarsened to hundreds if not thousands of level, which has now been shown to be caused by single matchings (it coarsens into a very large sparse graph with star like structure(s))
  
• Testing under-way  for M = 2,3,4,5,6,7,8 - with randomised matching. Following pre-analysis of the number of levels, those graphs which generate unreasonable number of levels (100+) are not fully tested due to the time taken to perform the tests, instead, only a limited number of tests will be used to prove my theories.
  
• Primitives - Implemented for Stars, Rings and Chains in both 2 and 3 dimensions. Testing will begin when resources are available.
  
• Dynamic!
  
• Operations have been taken from previous implementations and are undergoing some early phase testing to ensure no bugs (and make my life easier by adding some other functions so I don't have to do it later)
  
• Dynamic Chaco files are in the later stages of implementation (reading dynamic data) - though generating graphs with hundreds of thousands of vertices is a bit bias at the moment (sticking with very large grids, cube like structures, sierpinski triangles and primitives)
  
• Measuring quality - implementation stage of mental/movement map and I've been playing with some edge crossing stuff (though so far this hasn't gone well...)
  
• Dynamic coarsening - also under-way  but more at the theoretical stage than anything, just to make sure I know what I'm doing and what I expect to implement (not something I just want to hack together given previous problems).
  
• Other Bits!
  
• Post Order efficiency - something brought up a long time ago, during the MGF approximation, positions of vertices are averaged to produce more accurate positions of vertices in the coarser graph when calculating approximated repulsive forces. But this undermines the layout previously generated - not a problem for static graphs as the layout is used only once, but for dynamic graphs it becomes a problem. Some theoretical work has been carried out similar to the "ideal spring length" work by Walshaw, but nothing concrete.
  
• Warping of the graphs - using MGF has been shown to warp the layout of a graph (although using the graph theoretic distance instead of weights [mentioned above] has been shown to lower the effect greatly). The quadtree/octree has been shown to also have similar effect, especially on star type graphs, however, it is less noticeable to to the increased directions used (2 vs 4/8). Without using some radius to determine a cut off point, I wanted to see how much effect this has - but for now, this is not a concern.
  
• Thesis! - I have been working on adding text to my Thesis; the MGF theory has now been added with some description of functions and parameters with only Results, Analysis of Drawings and Conclusions to go in, the Multi-matching and Primitive Theory has also been started but requires some more work/research, and brief explanations of the Dynamic coarsening/operations have been included.

That's about all I have to share for now (that's all that's on the piece of paper in front of me). I will attempt  to update again soon but the current pattern is once every two to three weeks, so we will see how it goes. Have a good week!