Bad day, I guess.... but moving on to more important issues;
I/we had my monthly meeting last Thursday, which went well. We spoke about the results I have collected and the general consensus is that there should be something wrong with my implementation of the Quad Tree algorithm (should...). It was therefore decided that I need to check the code and rerun the tests in order to find any discrepencies. Another plan is to implement the scaling forces into the normal multilevel implementations (no approximation).
To start the week off well, I had left the tests running over the weekend. One of the quad tree retests failed to output altogether (due to the way Java stores output until theres enough to save, the file was left empty, suggesting an infinite loop or a buggy machine - which has happened before). This has been restarted with some more stable code (which worked for other graphs).
Continuing on with the dissapointment, the finan512 tests for CA still have not surpassed the size 100 tests (starts at 50, incremenets by 50 until 500, so very very slow).
Furthermore, the results I did manage to collect now show, wait for it... no difference.... The number of edge crossings against scalar value is linear (instead of quadratic like my own CA). I am still awaiting the results for 4elt before I can say for all cases but 3elt and 55grid show no change to the results collected before.
This leaves me with waiting for the results of the multilevel implementation with scalable forces, which previously hit a Java Heap Space error shortly after runtime.Another chance for redemption is to continue with the matching tests (compare matching with 4 vertices in CA against QT with matchings of 4 - the only real true test).
I guess its true to say if something can fail, it will all fail at once, but I'm sure there are some silver lining to these grey clouds somewhere in here. It just might be harder to see through the lightning and rain... heh. I will update again when I have more news. Have a fun week!
Monday, 24 October 2011
Tuesday, 18 October 2011
Conflicting headaches
This week I have been looking to complete my implementation of 3D testing using a simpler form of inertia bisection. As I mentioned before, I look for the most prominent axes, and move the vertices round to a new position which would simulate movement of the viewer. This is still being incorporated as there are some issues with rotating the view (testing different views to see which offers the best).
Viewpoints Yet Again
Whilst testing the views, I can see some improvement in the viewpoints, however, every time I am becoming more and more concerned that projecting a 3D image onto a 2D plane is bad, the bad kind of bad. With 2D images the forces push each other only on that plane, and so the results are in effect, designed and developed for that view.
3D results however, are not, they are designed to make the most of all 3 dimensions, and when compressed, they lose information and readability. This is all common sense really, but practically, I am seeing that "bends" and "folds" in graphs are more important in 3 dimensions as in most cases, vertices will clump together to form these much larger structures.
As you can see, the graph has more noticeable folds/arms, which again, in a 3D context (with movement and navigation) can show the global structure of a graph. Yet, the results will suffer again, even more so in this graph, due to the overlap.
A more accurate form of testing would be to identify these arms and finding a method for the computer/application to comprehend the structure in all dimensions. I imagine that due to the difficulty generating this kind of test, is why many authors choose to use subjective view or 2D projection.
Matching
Moving on from the viewpoints, I am moving back to matching in order to test a hypothesis regarding the 2D results. In them, the contraction approximation algorithm has difficult with higher scalar values, whereas the Quad Tree does not. I expect this to be due to the tree having four nodes as opposed to two, therefore, by changing the coarsening to match 4 vertices, I expect to see results closer resembling the quad tree results.
Currently, I am using a hard coded method which checks each edge, but due to the constraints of this, may have to move to a different data structure for the coarsening. This may be difficult to implement but the algorithm shouldn't be too affected by the change. Of course, this is a hope and there is a high chance of changes, which will require new results and more waiting.
Teaching
Teaching again and good god, I forgot how much time it takes out of the day. Thought I would mention this as I have spent more time than usual preparing for tutorials, sorting through students emails and tests (whoever invented QuestionWriter, damn you!) and generating new teaching material (or at least, altering old material).
Paper Writing
With results now analysed, it is becoming more and more likely that I will be expected to publish my results. I am still waiting on some further tests and would like to run some more, but so far I have concluded that using a contraction approximation is faster than a mesh overlay approximation, and in theory, should provide better results (which may be a reason it is faster).
NB: check the speed difference when generating the quad tree structure, as it may be that the time difference is due to making the tree, but it may also be due to the vertices finding better positions each iteration due to the better abstraction of the original graph.
End
That's all for today, I am hoping for a meeting with supervisors this week so I will update again if and when that happens. For now, if any students are watching, don't miss out on https://www.ai-class.com/ (even though not relevant and most of it is covered in undergraduate, it's still a good refresher and has some good material and explanations).
For everyone else, there's Dilbert, http://www.dilbert.com/
Have a good week!
Viewpoints Yet Again
Whilst testing the views, I can see some improvement in the viewpoints, however, every time I am becoming more and more concerned that projecting a 3D image onto a 2D plane is bad, the bad kind of bad. With 2D images the forces push each other only on that plane, and so the results are in effect, designed and developed for that view.
3D results however, are not, they are designed to make the most of all 3 dimensions, and when compressed, they lose information and readability. This is all common sense really, but practically, I am seeing that "bends" and "folds" in graphs are more important in 3 dimensions as in most cases, vertices will clump together to form these much larger structures.
The graph above, 4elt is semi useful in that the flattest surface is perpendicular to the viewpoint, but there are two folds/arms overlapping the main body. As a 3D image, these arms are an important part of the structure, yet when testing for edge crossings, these areas would be bad due to the overlap. A better example can be seen below, a stretched version of 3elt.
A more accurate form of testing would be to identify these arms and finding a method for the computer/application to comprehend the structure in all dimensions. I imagine that due to the difficulty generating this kind of test, is why many authors choose to use subjective view or 2D projection.
Matching
Moving on from the viewpoints, I am moving back to matching in order to test a hypothesis regarding the 2D results. In them, the contraction approximation algorithm has difficult with higher scalar values, whereas the Quad Tree does not. I expect this to be due to the tree having four nodes as opposed to two, therefore, by changing the coarsening to match 4 vertices, I expect to see results closer resembling the quad tree results.
Currently, I am using a hard coded method which checks each edge, but due to the constraints of this, may have to move to a different data structure for the coarsening. This may be difficult to implement but the algorithm shouldn't be too affected by the change. Of course, this is a hope and there is a high chance of changes, which will require new results and more waiting.
Teaching
Teaching again and good god, I forgot how much time it takes out of the day. Thought I would mention this as I have spent more time than usual preparing for tutorials, sorting through students emails and tests (whoever invented QuestionWriter, damn you!) and generating new teaching material (or at least, altering old material).
Paper Writing
With results now analysed, it is becoming more and more likely that I will be expected to publish my results. I am still waiting on some further tests and would like to run some more, but so far I have concluded that using a contraction approximation is faster than a mesh overlay approximation, and in theory, should provide better results (which may be a reason it is faster).
NB: check the speed difference when generating the quad tree structure, as it may be that the time difference is due to making the tree, but it may also be due to the vertices finding better positions each iteration due to the better abstraction of the original graph.
End
That's all for today, I am hoping for a meeting with supervisors this week so I will update again if and when that happens. For now, if any students are watching, don't miss out on https://www.ai-class.com/ (even though not relevant and most of it is covered in undergraduate, it's still a good refresher and has some good material and explanations).
For everyone else, there's Dilbert, http://www.dilbert.com/
Have a good week!
Friday, 14 October 2011
3D testing
This week I have processed the results for my 2D implementations of different graph drawing techniques (specifically, different approximations for graph drawing), and the results have been good. I am now aware that size of the viewing plane (directly relating to the size of k) has an effect on both quality and speed, and am also aware that my own approximation algorithm has issues with large scaling of repulsive forces between vertices.
Unfortunately, results are based purely on quantitative data in the hope it is related to the quality of the actual drawing; meaning I have no graphic representations of the results I have been comparing, in order to gauge the accuracy and readability of output. Running the algorithms with the same parameters gives me similar results but due to the stochastic nature of the repulsive forces between levels, it is unlikely to get exactly the same output.
Now, I have finished implementing a "cheats" version of 'inertia bisection' for use with finding a good viewpoint. Instead of calculating eigenvectors, I have found the most prominent axes of a graph based on the vectors of edges. In practise, this appears to work well, though results vary between graphs (As to be expected).
With this technique, instead of using the normal line intersection used before, I have to calculate the projected positions of the vertices onto a 2D plane from this view.
As mentioned so many times before, the greatest issue is that the current technique for gauging readability is its portability (or lack of) to 3D. With many of the graphs I have sampled, the 3-dimensional rotation of the graph makes it significantly easier to read than a 2D image, as folds are better defined and the overall structure can begin to make sense. In the tests, these folds, amongst creases and overlapping layers, will give bad results.
I have therefore chosen to continue with the tests but I acknowledge the variance in physical results is not as important as it once was, instead, memory footprint and runtime are more important, along with any subjective results made.
ALSO: finan512... seriously... how does it take so long to run tests on you...
Unfortunately, results are based purely on quantitative data in the hope it is related to the quality of the actual drawing; meaning I have no graphic representations of the results I have been comparing, in order to gauge the accuracy and readability of output. Running the algorithms with the same parameters gives me similar results but due to the stochastic nature of the repulsive forces between levels, it is unlikely to get exactly the same output.
Now, I have finished implementing a "cheats" version of 'inertia bisection' for use with finding a good viewpoint. Instead of calculating eigenvectors, I have found the most prominent axes of a graph based on the vectors of edges. In practise, this appears to work well, though results vary between graphs (As to be expected).
With this technique, instead of using the normal line intersection used before, I have to calculate the projected positions of the vertices onto a 2D plane from this view.
As mentioned so many times before, the greatest issue is that the current technique for gauging readability is its portability (or lack of) to 3D. With many of the graphs I have sampled, the 3-dimensional rotation of the graph makes it significantly easier to read than a 2D image, as folds are better defined and the overall structure can begin to make sense. In the tests, these folds, amongst creases and overlapping layers, will give bad results.
I have therefore chosen to continue with the tests but I acknowledge the variance in physical results is not as important as it once was, instead, memory footprint and runtime are more important, along with any subjective results made.
ALSO: finan512... seriously... how does it take so long to run tests on you...
Tuesday, 11 October 2011
Results Time
Spent the past few days collecting and arranging my first lot of results for the 2D implementations, and so far, results are mixed. My own Contraction Approximation algorithm is the fastest in all tests (considerably faster, in most cases running in at least half the time), however, my algorithm sacrifices edge crossings.
In the charts above, results are compared against a variable I have named the scalar; a parameter introduced to change the power of repulsive forces between vertices to find better graphical results. Other variables such as the size of the viewing plane (affects the size of k) have been tested.
So what do these results show? The most obvious is that edge crossings sky rocket as the scalar increases, whereas the quad tree is unaffected, suggesting the contraction tree CA uses is more sensitive than the bulky quad tree (testing different matching algorithms will check this). Although these crossings sky rocket, during the lower scalar values, the CA algorithm matches the edge crossings of QT; so its arguable that the CA is the better option in these circumstances.
Results for the graphs data, whitaker3 and 3elt also show this same pattern across all parameters tested so far. There are no uncontrolled parameters which give either algorithm a bias; both CA and QT use code as close to each others as possible, including same data structure, same matching technique, same coarsening scheme (alterations for CA of course) and same cooling schedule.
I will update again after future analysis and when I have begun the 3D tests.
 |  |
| 4elt Edge Crossings y: crossings count x: scalar parameter | 4elt Runtime y: runtime (ms) x: scalar parameter |
 |  |
| 55grid Edge Crossings y: crossings count x: scalar parameter | 55grid Runtime y: runtime (ms) x: scalar parameter |
In the charts above, results are compared against a variable I have named the scalar; a parameter introduced to change the power of repulsive forces between vertices to find better graphical results. Other variables such as the size of the viewing plane (affects the size of k) have been tested.
So what do these results show? The most obvious is that edge crossings sky rocket as the scalar increases, whereas the quad tree is unaffected, suggesting the contraction tree CA uses is more sensitive than the bulky quad tree (testing different matching algorithms will check this). Although these crossings sky rocket, during the lower scalar values, the CA algorithm matches the edge crossings of QT; so its arguable that the CA is the better option in these circumstances.
Results for the graphs data, whitaker3 and 3elt also show this same pattern across all parameters tested so far. There are no uncontrolled parameters which give either algorithm a bias; both CA and QT use code as close to each others as possible, including same data structure, same matching technique, same coarsening scheme (alterations for CA of course) and same cooling schedule.
I will update again after future analysis and when I have begun the 3D tests.
Thursday, 6 October 2011
Hello motivation/enthusiasm!
Unsure why, but I am beginning to like playing with eigenvectors. It seems like forever since I last played with any 'scary' maths, but thanks to a fellow PhD student, I am finally getting my head around this whole eigenvector/eigenvalue subject.
I am aware I have played eigenvectors before, but previously it was to understand how other more spectral graph drawing algorithms worked (and had no intention of implementing them). I am now needing them to use inertia bisection to help find the principal axis of a graph (normally used for graph partitioning) and use that to calculate the best viewpoint (perpendicular to it).
Meanwhile, I remain in waiting for my results of the 2D implementations. They were started yesterday (after more issues developed), and are still calculating away (worryingly only on their second graph). Checking output to the files, it seems they are still generating results and the slowness due to the number of parameters and size of the graphs. I was concerned for a point when I noticed output had stopped half way through a result (suggesting a failure) but thankfully Java is clever with writing to files; sending chunks at a time as opposed to writing directly to it.
Previous results and partial results from single parameters show that my Contraction Approximation is still faster in most cases, and offers competitive results for edge crossings with the less powerful repulsive forces, than the Quad Tree approximation. Future results will provide more solid evidence with which to make conclusions.
For now, I will continue with my work on finding the best viewpoint (sticking to the inertia bisection and principal axes instead of Webber's work on viewpoints).
I will most likely update again next week, for now, it is almost time for tutoring, so ta ta for now.
I am aware I have played eigenvectors before, but previously it was to understand how other more spectral graph drawing algorithms worked (and had no intention of implementing them). I am now needing them to use inertia bisection to help find the principal axis of a graph (normally used for graph partitioning) and use that to calculate the best viewpoint (perpendicular to it).
Meanwhile, I remain in waiting for my results of the 2D implementations. They were started yesterday (after more issues developed), and are still calculating away (worryingly only on their second graph). Checking output to the files, it seems they are still generating results and the slowness due to the number of parameters and size of the graphs. I was concerned for a point when I noticed output had stopped half way through a result (suggesting a failure) but thankfully Java is clever with writing to files; sending chunks at a time as opposed to writing directly to it.
Previous results and partial results from single parameters show that my Contraction Approximation is still faster in most cases, and offers competitive results for edge crossings with the less powerful repulsive forces, than the Quad Tree approximation. Future results will provide more solid evidence with which to make conclusions.
For now, I will continue with my work on finding the best viewpoint (sticking to the inertia bisection and principal axes instead of Webber's work on viewpoints).
I will most likely update again next week, for now, it is almost time for tutoring, so ta ta for now.
Monday, 3 October 2011
Disaster Strikes!
A wise old man once told me I was a fool of a Took, though now that I think of it, that might have been someone else...
The programs I left running over the weekend, never finished. A small mistake in my code meant that instead of moving to the next graph after the scale parameter is over 1000.0, it continued with the same graph with the same parameters. All down to one while loop; while(scale != 1000.0), a silly rookie mistake but not all is lost.
The programs did give some results for the graph 3elt, so I can use these to refine the tests further and highlight any possible issues. It has also shown me the importance of setting up remote desktop so I can see whats happening when at home (the computers are for hot-desking so do not have it set up, nor given useful machine aliases).
Unfortunately I will have to run the simulations again for those results I did not receive (losing more valuable time). I will edit this post when I've made a quick analysis of the results I do have.
<Results>
Delayed once again, I was fixing some irregularities in the different algorithms to give fairer results (one was calculating edge lengths as though in 3D, and the other had hard coded testing values), but all fixed now. Those tests have been left running and am expecting results back later today.
The results show that CA is 31.1% faster on average, than QT, but QT has less edge crossings on average. This is due to the affect of increasing the power of the repulsive forces; QT is little affected by this scalar and the edge crossings remain similar though out, whereas CA has large increases in edge crossings as the scalar increases.
These results are from running each algorithm once, with some discrepancies between the algorithms (QT had a hard coded 'size' of 100 instead of the 150 it should have been. Future results will show whether this has an effect on the edge crossings or not.
Results above are based of one runtime per scalar on each algorithm, for the graph 3elt. Numerical data from the tests will not be presented just yet until further results are finished.
</Results>
The programs I left running over the weekend, never finished. A small mistake in my code meant that instead of moving to the next graph after the scale parameter is over 1000.0, it continued with the same graph with the same parameters. All down to one while loop; while(scale != 1000.0), a silly rookie mistake but not all is lost.
The programs did give some results for the graph 3elt, so I can use these to refine the tests further and highlight any possible issues. It has also shown me the importance of setting up remote desktop so I can see whats happening when at home (the computers are for hot-desking so do not have it set up, nor given useful machine aliases).
Unfortunately I will have to run the simulations again for those results I did not receive (losing more valuable time). I will edit this post when I've made a quick analysis of the results I do have.
<Results>
Delayed once again, I was fixing some irregularities in the different algorithms to give fairer results (one was calculating edge lengths as though in 3D, and the other had hard coded testing values), but all fixed now. Those tests have been left running and am expecting results back later today.
The results show that CA is 31.1% faster on average, than QT, but QT has less edge crossings on average. This is due to the affect of increasing the power of the repulsive forces; QT is little affected by this scalar and the edge crossings remain similar though out, whereas CA has large increases in edge crossings as the scalar increases.
These results are from running each algorithm once, with some discrepancies between the algorithms (QT had a hard coded 'size' of 100 instead of the 150 it should have been. Future results will show whether this has an effect on the edge crossings or not.
Results above are based of one runtime per scalar on each algorithm, for the graph 3elt. Numerical data from the tests will not be presented just yet until further results are finished.
</Results>
Subscribe to:
Posts (Atom)