Interesting start to a Friday, no caffiene due to a power failure and vacating my office for an exam. Nonetheless, not a bad start to the end of the week.
This week I have been adding the "finishing touches" to my implementations (making some corrections and adding functionalities I had previously ignored). Currently I am implementing the clumped coarsening for both my own and Yifan Hu's work, requiring a little more thought than previously expected (the theory is ok, changing my code is less ok).
Also this week, I have been preparing and building my testing suite which will have plug in properties for easy addition of algorithms, and a small GUI for adding parameters to all algorithms (keyboard controls for all three can become tricky). Silly to mention really but better than saying "I wrote code for parameter testing".
Other work has involved fixing the Grid and Quadtree approximations to use the new Component system as opposed to the older Vertex system. This was stopped when I realised how much work it would be, so my intention is to fix the clumping and try again after when the data structure should be better suited.
For now, this fragmented update gives some indication of my workings. I will post again next week with more fruitful results. Note; Monday is a bank holiday so I bid you all a "Woo! 3 day weekend".
Friday, 26 August 2011
Tuesday, 23 August 2011
Oh No Problemosaur!
My previous entry, posted the whole of 24hours ago, gave a lovely list of what I want/need to do before I can compare my results. The first on that list, elegantly labelled '0.5' was to figure out why smaller graphs did not follow the suit of the larger graphs; a problem which vexed me as it should be a simple answer, yet none could be found.
Well it's time to rejoice, and somewhat cry. The bad layout in smaller graphs is an unexpected behaviour of the algorithm which generates a value of 'k' too high for a graph with too few vertices and edges. This high value is far too high for the graph to be drawn and so the only movement the graph can do is expand, with no tugging forces of the springs to pull it back into shape.
It should be noted, the calculation for k is currently based on the Frutcherman and Reingold formula which uses the size of the viewing area. Changing this so it becomes a value proportional to the size of the graph, as Walshaw has done, should resolve this petty issue.
Further to this, I have been constructing the testing framework which will run the finished algorithms, measuring their quality and putting the data into neat little tables to show which runs best. I am still researching how to achieve the best viewpoint and which method would be best for my work.
Once again, whilst joining all algorithms into one big framework, I am also looking to keep them as identical as possible to give a fairer test.
For now, I will continue and hopefully put another update out before the end of the week.
Well it's time to rejoice, and somewhat cry. The bad layout in smaller graphs is an unexpected behaviour of the algorithm which generates a value of 'k' too high for a graph with too few vertices and edges. This high value is far too high for the graph to be drawn and so the only movement the graph can do is expand, with no tugging forces of the springs to pull it back into shape.
It should be noted, the calculation for k is currently based on the Frutcherman and Reingold formula which uses the size of the viewing area. Changing this so it becomes a value proportional to the size of the graph, as Walshaw has done, should resolve this petty issue.
Further to this, I have been constructing the testing framework which will run the finished algorithms, measuring their quality and putting the data into neat little tables to show which runs best. I am still researching how to achieve the best viewpoint and which method would be best for my work.
Once again, whilst joining all algorithms into one big framework, I am also looking to keep them as identical as possible to give a fairer test.
For now, I will continue and hopefully put another update out before the end of the week.
Monday, 22 August 2011
(Not so) Finishing Touches
This week I am looking to complete my implementations of all approximations and prepare them for comparison, which I know; is easier said than done.
0.5 Fix the algorithm so lower level graphs can find a better layout as opposed to being slanted or having edges crossed.
1. My first target, the clumping implemented by Yifan Hu, only activated when a graph can no longer be coarsened efficiently. Using the different in vertices between each coarse level will trigger such a mechanism, which will then switch to a different matcher (or the same matcher with different parameters, dependant on how confident I feel).
2. Comparison of the theories of each algorithm against their describing papers, to ensure I have not missed anything and that they remain as close to the original implementation as possible.
3. Comparison of the implementations, for best and fairest results, I want the implementations of each to be as similar as possible (so using the same coarsening scheme, data structures, readers, drawers, even techniques where applicable).
4. Testing structure; as discussed in my previous meeting with supervisors, ideally I want a testing framework I can plug the algorithms into and expect results in a comparable and reliable form. For comparisons, I intend to follow suit and primarily compare run times, but also edge crossings (where possible and using a method to find the best viewing angle) and edge length ratio. Other smaller attributes may be monitored out of curiosity, such as the angle between edges, but this is heavy to compute and not necessarily a requirement.
5.Kill the Batman...
Though I know how my plans have panned out previously, it's hard to differentiate away from these but no doubt I will find a way. Assuming all goes well, these are my tasks, any others will be added to this list or will make a great reason to write another blog post. I will update with any news if I stumble across anything, for now, I hope to update later this week.
In the mean time, here is a image of some daunting finan512 output for you to enjoy:
0.5 Fix the algorithm so lower level graphs can find a better layout as opposed to being slanted or having edges crossed.
1. My first target, the clumping implemented by Yifan Hu, only activated when a graph can no longer be coarsened efficiently. Using the different in vertices between each coarse level will trigger such a mechanism, which will then switch to a different matcher (or the same matcher with different parameters, dependant on how confident I feel).
2. Comparison of the theories of each algorithm against their describing papers, to ensure I have not missed anything and that they remain as close to the original implementation as possible.
3. Comparison of the implementations, for best and fairest results, I want the implementations of each to be as similar as possible (so using the same coarsening scheme, data structures, readers, drawers, even techniques where applicable).
4. Testing structure; as discussed in my previous meeting with supervisors, ideally I want a testing framework I can plug the algorithms into and expect results in a comparable and reliable form. For comparisons, I intend to follow suit and primarily compare run times, but also edge crossings (where possible and using a method to find the best viewing angle) and edge length ratio. Other smaller attributes may be monitored out of curiosity, such as the angle between edges, but this is heavy to compute and not necessarily a requirement.
5.Kill the Batman...
Though I know how my plans have panned out previously, it's hard to differentiate away from these but no doubt I will find a way. Assuming all goes well, these are my tasks, any others will be added to this list or will make a great reason to write another blog post. I will update with any news if I stumble across anything, for now, I hope to update later this week.
In the mean time, here is a image of some daunting finan512 output for you to enjoy:
Wednesday, 17 August 2011
Do as I command!
Not much to declare today; I have successfully retrieved some not-unattractive drawings from my contraction approximation, and it all runs in relatively fast time. Unfortunately, I am currently limited (runtime-wise) by the coarsening process which takes much longer in larger graphs (4elt, coarsener: 41sec fdp: 7sec).
I am therefore aiming to improve upon the coarsening technique so it is faster and uses less memory (as memory heap exceptions are also issues in huge graphs). I have still yet to determine whether the extended coarsening time is due to the calculation of the approximation structure (though it shouldn't be, I have to make sure).
Regarding Dynamics, I have thought it may be possible to introduce the multilevel paradigm into the contraction structure (as opposed to my current technique of running the FDP on each level) so to save some time (as the information is readily available to be calculated in the structure but needs to be applied correctly).
Back to my current implementation, the issues in lower levels of the graphs are still prevalent and I fear this is causing the algorithm to run longer than it needs to. I have managed to stop the vertices sticking to a tilted "plane" (I use the term loosely), achieved by using a random distance to push vertices apart as opposed to a set distance. I am currently working as to why the smaller graphs have such an issue, with the mostly likely suspect being inadequate forces.
Experimentation shows that changing the way the forces dampen the peripheral effect can lead to better or worse drawings based on the type of graph (grids benefit from a more power dampener).
It appears at the moment I have lots of little bits to play with; so I will look to mix these together or remove them as issues. For now, here are some more pretty pictures.
I am therefore aiming to improve upon the coarsening technique so it is faster and uses less memory (as memory heap exceptions are also issues in huge graphs). I have still yet to determine whether the extended coarsening time is due to the calculation of the approximation structure (though it shouldn't be, I have to make sure).
Regarding Dynamics, I have thought it may be possible to introduce the multilevel paradigm into the contraction structure (as opposed to my current technique of running the FDP on each level) so to save some time (as the information is readily available to be calculated in the structure but needs to be applied correctly).
Back to my current implementation, the issues in lower levels of the graphs are still prevalent and I fear this is causing the algorithm to run longer than it needs to. I have managed to stop the vertices sticking to a tilted "plane" (I use the term loosely), achieved by using a random distance to push vertices apart as opposed to a set distance. I am currently working as to why the smaller graphs have such an issue, with the mostly likely suspect being inadequate forces.
Experimentation shows that changing the way the forces dampen the peripheral effect can lead to better or worse drawings based on the type of graph (grids benefit from a more power dampener).
It appears at the moment I have lots of little bits to play with; so I will look to mix these together or remove them as issues. For now, here are some more pretty pictures.
 |  | |
4elt.graph, although the peripheral effect is quite large, the structure of the graph can be easily identified. | fe_4elt2.graph, drawn with similar forces, the image shows the detail of the graph. Note; some areas of compression in the bottom where a section has folded on itself. | |
 |  | |
Hooray! Testing and achieved this odd looking drawing, seemingly of someone with hands in the air wearing a cape.I might just be going crazy though... | 3elt.graph; unfortunately the layout here is quite flat, but till shows the layout of the graph with the compressed edges in the centre surrounding a gap. | |
 | ||
| 55grid, drawn using the same forces used to draw the graph 4elt above, showing the forces do not necessarily work for all graphs. The difference is down to increasing the magnitude of the spring force, showing its relatively easy to alter the graph. |
Friday, 12 August 2011
Going on and on
A rather late and lonely update this week.
For the past few days I have been working on upgrading and refining my own contraction approximation, and also the barnes hut quadtree; fiddling around with the forces and tweaking the output to give the best drawings. Unfortunately this has not worked for every graph, but I am able to retrieve relatively good layouts for many graphs.
Tangling appears to be my biggest issue thus far, with many graphs struggling to stretch out and instead, collapsing in on itself. This is normally an issue caused by the repulsive forces being too weak, however, it is not so easy with the use of a hierarchical tree to model the structure of the graph (forces are dependant on weights, and so increasing a force will have greater effect on "heavy" nodes). This is mostly global untangling, some local tangling has been found but only occurs in one area of the graph and panning out (like a messy gradient).
Investigation and experimentation continues as always, in an attempt to find a cure. Below is an image showing that forces for one graph may not have the same desired effect on another. The graph data, on the left, is drawn relatively accurately my contraction method, however, the forces used to not work with the graph 3elt which is shown compressed on the right below.
Another peculiar issue with the contraction is its drawings of smaller graphs, particularly those formed in the coarser levels of the multilevel paradigm. For instance, take the pictures below showing multiple levels of a graph.
The above image shows the 3 coarsest levels of a standard grid, which do not follow the pattern they should, seen below.
below is another image showing several levels of the same graph, suddenly expanding in the z direction. The confusing issue here is that it only starts expanding after a certain point, much like the z-axis problem exhibited in the Barnes Hut implementation previously.
This behaviour suggests that there is a bug in the code, much like the z-axis issue, which is stopping the z-directional forces until a build up causes it to finally expand. However, this still provides some good layouts for other compact graphs like data. Unfortunately large expansive graphs such as 4elt and 55grid suffer from this behaviour.
Investigation and experimentation is under way to find this bug and fix immediately.
Other issues with the Barnes Hut arose, whereby a graph would partition itself into two, and throw each other in opposite directions (much like two vertices) connected by a tube of edges. Unfortunately I did not get a screen shot of this and can no longer generate the same behaviour. It was resolved (for now) by altering the strength of forces.
This is all for now, I am supposedly moving back to Greenwich this weekend so that should be fun...
I will update again next week, hopefully with some measurable results. Have a good weekend!
For the past few days I have been working on upgrading and refining my own contraction approximation, and also the barnes hut quadtree; fiddling around with the forces and tweaking the output to give the best drawings. Unfortunately this has not worked for every graph, but I am able to retrieve relatively good layouts for many graphs.
Tangling appears to be my biggest issue thus far, with many graphs struggling to stretch out and instead, collapsing in on itself. This is normally an issue caused by the repulsive forces being too weak, however, it is not so easy with the use of a hierarchical tree to model the structure of the graph (forces are dependant on weights, and so increasing a force will have greater effect on "heavy" nodes). This is mostly global untangling, some local tangling has been found but only occurs in one area of the graph and panning out (like a messy gradient).
Investigation and experimentation continues as always, in an attempt to find a cure. Below is an image showing that forces for one graph may not have the same desired effect on another. The graph data, on the left, is drawn relatively accurately my contraction method, however, the forces used to not work with the graph 3elt which is shown compressed on the right below.
 |  |
Another peculiar issue with the contraction is its drawings of smaller graphs, particularly those formed in the coarser levels of the multilevel paradigm. For instance, take the pictures below showing multiple levels of a graph.
The above image shows the 3 coarsest levels of a standard grid, which do not follow the pattern they should, seen below.
The image below shows the same tangling in another coarse level of a grid (from the same set as above), and when turned, shows the grid is drawn only in 2D (but slanted in 3D for known unimportant reasons).
below is another image showing several levels of the same graph, suddenly expanding in the z direction. The confusing issue here is that it only starts expanding after a certain point, much like the z-axis problem exhibited in the Barnes Hut implementation previously.
This behaviour suggests that there is a bug in the code, much like the z-axis issue, which is stopping the z-directional forces until a build up causes it to finally expand. However, this still provides some good layouts for other compact graphs like data. Unfortunately large expansive graphs such as 4elt and 55grid suffer from this behaviour.
Investigation and experimentation is under way to find this bug and fix immediately.
Other issues with the Barnes Hut arose, whereby a graph would partition itself into two, and throw each other in opposite directions (much like two vertices) connected by a tube of edges. Unfortunately I did not get a screen shot of this and can no longer generate the same behaviour. It was resolved (for now) by altering the strength of forces.
This is all for now, I am supposedly moving back to Greenwich this weekend so that should be fun...
I will update again next week, hopefully with some measurable results. Have a good weekend!
Thursday, 4 August 2011
Shoot... it was close too
This week I have been implementing and making the necessary ammendments to my own contraction approximation algorithm, and this brings us the latest output from my implementions:
The graphs are drawn remarkably well for a first attempt (no refinement) and show that the contraction approximation works well enough to give a layout showing some of the features of the graph. Still, there is some work to be done to give more attractive results as these results are somewhat squashed on the z-axis (again...).
Removing the z-axis from the FDP algorithm, squashes the graphs again so they become thin stick-like graphs at a slant. This is perculiar as this behaviour suggests that every dimension has moved over (so 3rd is now 2nd, and that if I were to include a 4th, it would draw the 3rd, which is of course madness).
Some investigation and experimentation should resolve this. In an attempt to allow for clumping as opposed to edge contraction, I will be looking at changing the algorithm so a user can select how many vertices can be clumped, and in turn, allow the algorithm to decide whether edge contraction is sufficient or if grouping vertices would be more efficient.
I will continue with everything and update next Monday or Tuesday (only one update this week I'm afraid... I can hear your sign of relief by the way...). Have a good Friday/weekend!
 |  |
| 55grid.graph | 3elt.graph |
Subscribe to:
Posts (Atom)