No news to report so far, other than the "oh my god, what have i done? what is this? what is that?" that comes with normal programming.
This week is delegated as the "paper week", whereby I will concentrate on getting the draft of a technical report out to my supervisors for checking. Only 2 weeks until students break for Christmas, and so I am running very close to my deadline (and I will need time for the supervisors to check it over, as nothing ever happens instantly).
I will be continuing with the multi-matching code after the draft is submitted (I will be writing up the theory but results will not be available and will be added when collected). For now, enjoy the week!
Monday, 28 November 2011
Wednesday, 23 November 2011
No Update == Progress? maybe?
I havnt given an update here recently, and this could be for many reasons: I've been so overwhelmed with work that I've had no chance? I've been so excited about work that I couldnt leave it for long enough to write here? Im lazy? Writing up my work has left be mentally decapitated?
While there is a thread of truth to each of these, it's mostly me having forgot about it. I have been concentrating on paper writing and preparing my results for publication. With this I have been re-reading a lot of the papers (which, admittedly, i havnt touched in a while) and finding ever more things to change with my implementations.
Even though there are changes, my previous results are still applicable due to the controlled environment - it just means they do not the full functionality of the original algorithms theyve been implemented to copy (which might eb frowned upon but as it is a comparison, the controlled environment should be beneficial).
In addition, I have been working to improve my own algorithm to retrieve the best results I can (including an implementation of multi-matching [grouped coarsening] to help combat star-type graphs).
I have also discovered/realised that Yifan Hu previously implemented a feature similar to the "scaling parameter" for repulsive forces to combat the peripheral effect - a parameter, p, he uses as the power in his force calculation. Why I didn't pick up on this before I do not know and worries me... but its not the end of the world.
With this recounted knowledge, I will look to publish my results as a refinement of this based on purely measurable output with the focus being to find a "good default value" for the CA algorithm (not an entire waste).
I have also failed to mention I differ from the original method for calculating the "k" value. Walshaw and Hu use a method where each graph uses the value of k' = sqrt(4/7)*k where k is the value of k from the previous graph and k' is the new value. I have been using the approach by Frutcherman and Reingold where the value is proportional to the number of vertices, and the size of the output.
This has been chosen as I dislike the method of calculating the initial graphs k value (using the average edge which is generated randomly) - so instead, each abstract graph has a value of k' = sqrt( Area/ |V| ). Comparing the sizes between graphs I get a value of ~0.72, in comparison to the value of 0.75 given from sqrt(4/7). There is a difference between output which I will look in to (and hopefully measure) but the difference is very small, bordering insignificant.
Some issues remain with algorithm (for both of these approaches) in that coarser graphs don't appear to be drawn well (for example, a line of edges will be bent instead of straight). This has been investigated and is down to the value of k (the size of the output), which requires further experimentation.
Moving on from the "everything is wrong" outlook, I have set the last day of this working year as my deadline to finish the work on static graphs. This should give me plenty of time to finish my investigations and implement improved functionality for better results in the end. I have already collected enough evidence of the contraction algorithms usability in contrast to the Barnes Hut octree approximation, so any further work is purely to find better and better results.
I will update again next week, most likely with "I implemented this.." or "I fixed this..." but I better not jinx it.
While there is a thread of truth to each of these, it's mostly me having forgot about it. I have been concentrating on paper writing and preparing my results for publication. With this I have been re-reading a lot of the papers (which, admittedly, i havnt touched in a while) and finding ever more things to change with my implementations.
Even though there are changes, my previous results are still applicable due to the controlled environment - it just means they do not the full functionality of the original algorithms theyve been implemented to copy (which might eb frowned upon but as it is a comparison, the controlled environment should be beneficial).
In addition, I have been working to improve my own algorithm to retrieve the best results I can (including an implementation of multi-matching [grouped coarsening] to help combat star-type graphs).
I have also discovered/realised that Yifan Hu previously implemented a feature similar to the "scaling parameter" for repulsive forces to combat the peripheral effect - a parameter, p, he uses as the power in his force calculation. Why I didn't pick up on this before I do not know and worries me... but its not the end of the world.
With this recounted knowledge, I will look to publish my results as a refinement of this based on purely measurable output with the focus being to find a "good default value" for the CA algorithm (not an entire waste).
I have also failed to mention I differ from the original method for calculating the "k" value. Walshaw and Hu use a method where each graph uses the value of k' = sqrt(4/7)*k where k is the value of k from the previous graph and k' is the new value. I have been using the approach by Frutcherman and Reingold where the value is proportional to the number of vertices, and the size of the output.
This has been chosen as I dislike the method of calculating the initial graphs k value (using the average edge which is generated randomly) - so instead, each abstract graph has a value of k' = sqrt( Area/ |V| ). Comparing the sizes between graphs I get a value of ~0.72, in comparison to the value of 0.75 given from sqrt(4/7). There is a difference between output which I will look in to (and hopefully measure) but the difference is very small, bordering insignificant.
Some issues remain with algorithm (for both of these approaches) in that coarser graphs don't appear to be drawn well (for example, a line of edges will be bent instead of straight). This has been investigated and is down to the value of k (the size of the output), which requires further experimentation.
Moving on from the "everything is wrong" outlook, I have set the last day of this working year as my deadline to finish the work on static graphs. This should give me plenty of time to finish my investigations and implement improved functionality for better results in the end. I have already collected enough evidence of the contraction algorithms usability in contrast to the Barnes Hut octree approximation, so any further work is purely to find better and better results.
I will update again next week, most likely with "I implemented this.." or "I fixed this..." but I better not jinx it.
Tuesday, 15 November 2011
Updates becoming a rarity? :o
I've noticed that my blog posts are now becoming weekly, which isn't necessarily bad, but I feel I should leave an update more often to ensure that I'm doing the work and to show the world my pretty pictures.
This week I've been writing up my work into some sort of essay-thing, which is now taking shape. On top of this I have begun collecting subjective evidence for the paper; running the application with the values given by the quantitative results and selecting "good" drawings to include. This is for both algorithms to show fairness.
Funny enough, although the results suggest no large change in quality when the force-strength-parameter (yet to be given a name) is below 1; the drawings appeal to my subjective taste when the value is low (0.0005) as opposed to higher values (0.5 - 1.0). This is no real surprise and was to be expected.
3D results had been on hold (what with problem solving and such) but will be next on my list.
But with progress comes reality to kick me back down, I have been comparing my runtime's against those given in other people's papers. ACE really does ruin it for me, with its millions of vertices in seconds (though I can live with this as it is spectral drawing as opposed to FDP - or so wikipedia tells me). Worse still, Yifan Hu's results are slightly better than those given by my implementation of his work and my own work, and in order to compete, I must spend more time improving (and finishing) my algorithm.
Now for some images:
This is a comparison of the graph fe_body, on the left is the output from my own algorithm, and on the left, that given on Yifan Hu's gallery. Although globally different, the structures are very similar (if not identical). A very badly draw picture below shows the similarities.
Admittedly, his looks more car-like... but his is a finished algorithm and not in comparison_mode.
This week I've been writing up my work into some sort of essay-thing, which is now taking shape. On top of this I have begun collecting subjective evidence for the paper; running the application with the values given by the quantitative results and selecting "good" drawings to include. This is for both algorithms to show fairness.
Funny enough, although the results suggest no large change in quality when the force-strength-parameter (yet to be given a name) is below 1; the drawings appeal to my subjective taste when the value is low (0.0005) as opposed to higher values (0.5 - 1.0). This is no real surprise and was to be expected.
3D results had been on hold (what with problem solving and such) but will be next on my list.
But with progress comes reality to kick me back down, I have been comparing my runtime's against those given in other people's papers. ACE really does ruin it for me, with its millions of vertices in seconds (though I can live with this as it is spectral drawing as opposed to FDP - or so wikipedia tells me). Worse still, Yifan Hu's results are slightly better than those given by my implementation of his work and my own work, and in order to compete, I must spend more time improving (and finishing) my algorithm.
Now for some images:
This is a comparison of the graph fe_body, on the left is the output from my own algorithm, and on the left, that given on Yifan Hu's gallery. Although globally different, the structures are very similar (if not identical). A very badly draw picture below shows the similarities.
Admittedly, his looks more car-like... but his is a finished algorithm and not in comparison_mode.
Wednesday, 9 November 2011
Funny thing: all my results are worthless (or are they?)
I should never become a novelist...
But back to reality now, I spent yesterday evening making notes and (finally) planning for the arduous paper writing task ahead. As I was working through how to describe my algorithm and its differences to others, I noticed a large and quite significant difference between mine and the quad tree approach used by Yifan Hu; the quad tree is created for each graph in the multilevel scheme, whereas the contraction tree is made once during the coarsening stage (Captain Obvious FTW).
This leaves a large gap of updating the tree. The quad tree does not concern itself with coarse vertex positions after they have been expanded in a finer graph, and so only needs to create a new structure around the finer graph. In the contraction tree, the structure uses the positions of the coarser graphs (parents of vertices and parents of parents), meaning we have to concern ourselves with updated the tree.
Previous to this, the position of coarser vertices are those that were calculated last (when the algorithm gives placement to each graph at a time). This has the consequence that if positions of vertices in a finer graph G(i) change by a large amount, the position of the parents in G(i+n) will no longer accurately model those vertices, and so the approximation loses accuracy.
It is surprising that this did not affect the drawings of the CA approach in a more significant way, but now explains why there is such a difference in both runtime and drawing quality. I have since implemented a method for the update of the contraction tree which will update the parents positions to better model the children.
The beauty of this is that (sacrificing the decreased runtime) I should be able to get better quality drawings, whilst still having the option to ignore quality and concentrate on runtime (a feature not seen in my implementation of the quad tree). The better news, is that this problem will have implications in my future work of dynamic graph drawing, when I will need to update the parents of vertices (in coarser graphs).
Results from previous tests are still valid and will act as one half of the testing data, or what shall be known as "Fast Mode". I am preparing a second lot of tests for the new "Quality Mode", and will continue my paper planning/writing with minimal interference.
Tuesday, 8 November 2011
Such thing as a too much of a Tutor?
Last post I mentioned I would have some pictures for you this week, and I just know all my readers cant sleep without those graphs, I will fulfil my promise. But first, (wouldnt be as fun if I didnt make you wait), this week, its been mentioned that I spend too much time on my tutorials.
This might not sound bad but I now notice that several times a week I find myself writing additional material or small programs to help my students with the tutorials. I have also been developing a demo of a coursework for one course, which has taken more time than it should have. Therefore, I hereby declare that I will refrain from this in future, and will keep to the expected 1hour 30mins extra time I am expected to give per tutorial.
Now that time is an issue and I am drifting away from my studies, its time to get back into shape. I present to you, my latest results, comparing the different approximation techniques on the graph 3elt.
CA : Contraction Approximation
QT : Quad Tree Approximation (Barnes Hut / Yifan Hu)
ML : Standard Multilevel - No Approximation
The results show that the contraction approximation is the fastest again (further testing show this is mostly due to not having to build the QuadTree structure). Unfortunately, the Quad Tree still provides better results for edge crossings. Below shows some results for the 3elt graph - excluding the ML algorithm (due to the time it would take to run the tests).
Similarly, these results show that the contraction approximation is faster and that the quad tree offers better quality. Note that in the size 50, the runtime appears to get smaller for quad tree, as the force multiplier is increased; if the results where to continue, it would most likely become faster than the contraction approximation (unfortunately for quad tree, the number of edge crossings increases hugely before this happens).
Using a measure of quality which applies to all graphs ( (E)(E-1)/ec ) I can see that quad tree continues to offer better results in smaller graphs, but when using 4elt, the difference becomes smaller and in some cases, the contraction approximation offers better quality.
If possible, I may run some additional tests on larger graphs (finan512 testing failed due to the problems exhibited with QT before), which will identify whether edge contraction becomes more useful in larger graphs or whether this is just a coincidental case (in theory it would make sense due to the approximation using the graph structure but previously this assumption has been wrong).
Results from this will also help choose a useful default force multiplier for some graphs. Currently it appears the best parameters are using size 50 with a force multiplier between 1.0 and 50.0, however, from experience I know that with larger graphs, it is better to draw them using a larger output area with forces outside of this range.
Currently I am planning out/writing out my paper for this, based on these results. I do however feel more results are required, but for now, I can concentrate my writing on the theory.
This might not sound bad but I now notice that several times a week I find myself writing additional material or small programs to help my students with the tutorials. I have also been developing a demo of a coursework for one course, which has taken more time than it should have. Therefore, I hereby declare that I will refrain from this in future, and will keep to the expected 1hour 30mins extra time I am expected to give per tutorial.
Now that time is an issue and I am drifting away from my studies, its time to get back into shape. I present to you, my latest results, comparing the different approximation techniques on the graph 3elt.
CA : Contraction Approximation
QT : Quad Tree Approximation (Barnes Hut / Yifan Hu)
ML : Standard Multilevel - No Approximation
 |  |
| 3elt edge crossings at size 50 | 3elt runtime at size 50 |
 | |
| 3elt runtime at size 50 (excluding ML) | |
 |  |
| 3elt edge crossings at size 250 | 3elt runtime at size 250 |
The results show that the contraction approximation is the fastest again (further testing show this is mostly due to not having to build the QuadTree structure). Unfortunately, the Quad Tree still provides better results for edge crossings. Below shows some results for the 3elt graph - excluding the ML algorithm (due to the time it would take to run the tests).
 |  |
| 4elt edge crossings at size 50 | 4elt runtime at size 50 |
 |  |
| 4elt edge crossings at size 200 | 4elt runtime at size 200 |
Similarly, these results show that the contraction approximation is faster and that the quad tree offers better quality. Note that in the size 50, the runtime appears to get smaller for quad tree, as the force multiplier is increased; if the results where to continue, it would most likely become faster than the contraction approximation (unfortunately for quad tree, the number of edge crossings increases hugely before this happens).
Using a measure of quality which applies to all graphs ( (E)(E-1)/ec ) I can see that quad tree continues to offer better results in smaller graphs, but when using 4elt, the difference becomes smaller and in some cases, the contraction approximation offers better quality.
 |  |
| 3elt Quality | 4elt Quality |
If possible, I may run some additional tests on larger graphs (finan512 testing failed due to the problems exhibited with QT before), which will identify whether edge contraction becomes more useful in larger graphs or whether this is just a coincidental case (in theory it would make sense due to the approximation using the graph structure but previously this assumption has been wrong).
Results from this will also help choose a useful default force multiplier for some graphs. Currently it appears the best parameters are using size 50 with a force multiplier between 1.0 and 50.0, however, from experience I know that with larger graphs, it is better to draw them using a larger output area with forces outside of this range.
Currently I am planning out/writing out my paper for this, based on these results. I do however feel more results are required, but for now, I can concentrate my writing on the theory.
Friday, 4 November 2011
Quick
Just a quick post given its the end of the week and I haven't updated in a while.
This week I have rewritten the Quad Tree approximation algorithm again, and finally I have some accurate results. Due to some discrepencies (the likes of which are still being questioned) being fixed, both approximations (and the results of using normal multilevel with no approximation) follow the curve shown previously by the contraction approximation.
Unfortunately, the edge crossings still look quite unhappy, with quad tree providing less crossings in most cases. However, the difference in runtime can still be observed (note, it appears quad tree gets faster than contraction as the force multiplier gets higher, but at these sizes, crossings are very high and so the speed is useless).
The results show that there is a range 1where the values of the force multiplier allow for good layouts to be given (in terms of edge crossings), so I will now concentrate my efforts on these values. My aim is to decrease the number of edge crossings at the expense of runtime - hopefully so runtime can match that of the quad tree but with better results (if not the same...).
I am also hoping to test coarsening of multiple vertices to see how the quad tree can compare to the structured approach (my prediction is that contraction will perform better due to the approximation using the relationships).
However, these are small in comparison to the next big jump, the paper writing and hopefully, moving to the dynamic layouts. I will update with some charts to show the new results next week (its 7:15pm on Friday now and have lost the patience of uploading images with Blogger).
Have a good weekend!
This week I have rewritten the Quad Tree approximation algorithm again, and finally I have some accurate results. Due to some discrepencies (the likes of which are still being questioned) being fixed, both approximations (and the results of using normal multilevel with no approximation) follow the curve shown previously by the contraction approximation.
Unfortunately, the edge crossings still look quite unhappy, with quad tree providing less crossings in most cases. However, the difference in runtime can still be observed (note, it appears quad tree gets faster than contraction as the force multiplier gets higher, but at these sizes, crossings are very high and so the speed is useless).
The results show that there is a range 1where the values of the force multiplier allow for good layouts to be given (in terms of edge crossings), so I will now concentrate my efforts on these values. My aim is to decrease the number of edge crossings at the expense of runtime - hopefully so runtime can match that of the quad tree but with better results (if not the same...).
I am also hoping to test coarsening of multiple vertices to see how the quad tree can compare to the structured approach (my prediction is that contraction will perform better due to the approximation using the relationships).
However, these are small in comparison to the next big jump, the paper writing and hopefully, moving to the dynamic layouts. I will update with some charts to show the new results next week (its 7:15pm on Friday now and have lost the patience of uploading images with Blogger).
Have a good weekend!
Subscribe to:
Posts (Atom)