This week I have begun my "experiments". My framework is as good as it will ever be, with most of the implementation static and unchanging in order to control the output.
On Friday I completed my implementation of the algorithm used by FR (without grid layout), so a natural step for me was to at least check it worked faster than the Eades implementation. Results wise, about 50% faster in larger graphs, however, there were cases when the Eades algorithm achieved results before the algorithm had completed (before FR). A closer examination of the results using non-random coordinates will be undertaken late.
Next up was to implement the grid described by Fruchterman and Reingold, and subsequently, the Barnes Hut Quadtree/Octree grid, in order to compare against each other (Yifan Hu and I believe another earlier paper by Junger implement this effectively, but empirical data using the same system would be nice).
Whilst planning how to approach this, I remembered such a system may not be necessary in dynamic graphs, which sparked my usual madness/ideas. Veldhuizen uses his dynamics in a way that finer graphs are still affected by the acceleration and velocity of higher coarser level (using them as global forces), whilst forces are still calculated for the finer graphs. Although I will still implement the grids for approximation, I am looking into exploiting the coarsening structure in the same way as Veldhuizen, so this does not have to be calculated again.
{There are also other ideas but until I have proof they can be of use, I will not share them out of fear of looking silly, and also so you cant steal them :) }
Hopefully I'll have a more fulfilling update next time as this only highlights previous work and my plans. In the mean time, back to work!
<edit> Forgot to mention, you will hear less of the literature review from now as it is being completed during non-implementation hours to avoid spending too much time on it </edit>
Tuesday, 29 March 2011
Friday, 25 March 2011
About time!
@Happy_Mode: On
I have finally managed to get the FR equations working (at long last), also, its Friday.
This success was due to my implementation of a cooling schedule (which didn't seem necessary in my calculations, then again, my calculations were for one or two iterations). Ideally I wanted to avoid this so I would have a less complex framework but beggars can't be choosers, I'm just happy its working.
With this complete, and my framework also nearing completion (only 1 week behind), experimentation will be soon.
Have a good weekend!
I have finally managed to get the FR equations working (at long last), also, its Friday.
This success was due to my implementation of a cooling schedule (which didn't seem necessary in my calculations, then again, my calculations were for one or two iterations). Ideally I wanted to avoid this so I would have a less complex framework but beggars can't be choosers, I'm just happy its working.
With this complete, and my framework also nearing completion (only 1 week behind), experimentation will be soon.
Have a good weekend!
Thursday, 24 March 2011
FR Success (I think?)
I've mentioned my struggle with the FR and CW force functions before, and chose to ignore them until I needed them (so I could concentrate on other things such as the multilevel). Recently, as speed is now an issue, I have spent a lot of time attempting to implement these faster forces.
Unfortunately, I had hit a road block; no matter what I tried, I could not get forces that worked well (often one force overpowered another resulting is vertices being thrown huge distances apart and eventually their position becomes infinite [in Java]).
After struggling for long enough, I spoke to my supervisor, who pointed out a flaw in my understanding. You see, I have been going through papers with an understanding that the |x| notation as the absolute value/size/magnitude. So when I came to Fruchterman and Reingolds pseudocode, the line: disp/|disp|, to me, meant get the sign of disp.
Unfortunately my understanding was partially incorrect, in the pseudo code, the notation |x|, or in CW, ||x||, is the normalise function. So for a vector V, ||V|| would be the length of the vector (or using my own previous notation, d).
What's almost cruel, is I have used this previously for applying my Eades forces, so should have realised this. Although not implemented in my code yet, I have tested my new understanding on paper, and it appears to work (although I ignore the min(||disp||, t) function as I want to avoid the cooling schedule for now [for testing purposes]).
In other news, I found a useful paper which looks at over 100 network visualisation tools which looks to be useful (published December 2007 so fairly recent). I have also found a peice of software that has implemented my "Big Bang" idea which, in a way, is a confidence boost (something I thought of works, even if not implemented by myself). Details will be added in a later post.
Unfortunately, I had hit a road block; no matter what I tried, I could not get forces that worked well (often one force overpowered another resulting is vertices being thrown huge distances apart and eventually their position becomes infinite [in Java]).
After struggling for long enough, I spoke to my supervisor, who pointed out a flaw in my understanding. You see, I have been going through papers with an understanding that the |x| notation as the absolute value/size/magnitude. So when I came to Fruchterman and Reingolds pseudocode, the line: disp/|disp|, to me, meant get the sign of disp.
if disp = -2.0; (-2.0)/(2.0) = -1;
Unfortunately my understanding was partially incorrect, in the pseudo code, the notation |x|, or in CW, ||x||, is the normalise function. So for a vector V, ||V|| would be the length of the vector (or using my own previous notation, d).
disp.x/disp = x-axis component of vector
What's almost cruel, is I have used this previously for applying my Eades forces, so should have realised this. Although not implemented in my code yet, I have tested my new understanding on paper, and it appears to work (although I ignore the min(||disp||, t) function as I want to avoid the cooling schedule for now [for testing purposes]).
In other news, I found a useful paper which looks at over 100 network visualisation tools which looks to be useful (published December 2007 so fairly recent). I have also found a peice of software that has implemented my "Big Bang" idea which, in a way, is a confidence boost (something I thought of works, even if not implemented by myself). Details will be added in a later post.
Tuesday, 22 March 2011
Beware the libraries...
Although I mentioned my next post would be mid-week, I have come across a nuisance within Java.
<EDIT> Just discovered the cause for vertices being "thrown" from the graph; the when two vertices are too close together, the forces repulse so much that the displacement is magnitudes higher than it should be. This is what happens when you use quadratics such as the inverse square law.
For reference; if d = 0.01, 1/d^2 = 1000, if nothing is limiting the forces this is allowed through. The repulsive forces are calculated first so this should never happen (unless the springs are too powerful), however, in larger graphs its possible the forces push two vertices too close or something? (still doesn't sound like it should happen but its the only piece of code (so far) that exhibits such force)</EDIT>
It is relatively obvious that more complex calculations take a little more time to calculate, although if only performed a few times, it is negligible. Fruchterman and Reingold mentioned that Eades logarithmic equation for calculating spring forces were inefficient and managed to get similar results using linear equations (although I may need to check if it was the algorithm or the calculation which was inefficient).
Although I should be focusing on other more important aspects and not the software/programming part, I wanted to check whether Java would display a difference between such calculations. I found some interesting results:
for 10million iterations (had to scale for measurable data);
As you can see, using java.lang.Math significantly increases the time taken. This is most likely due to having call the method from the Math class instead of throwing it at the processor. Note, importing the Math libraries makes little difference. Bare in mind that a graph of 5k vertices in an O(|V|^2) algorithm is 25million iterations.
Just food for thought for any mathematicians or statisticians out there working with Java libraries and collections of millions of entities, and are looking to reduce runtime. Now back to implementing my ideas...
<EDIT> Thanks for the advice Chris; for those who do not read comments, Chris proposed a fairer test to determine the delay with using libraries (if any), by using Math.abs(), as pow() and log() take time to calculate anyway. The results still show a delay but it is infinitesimal in comparison to that shown above (a few ms for 10million iterations). </EDIT>
<EDIT> Just discovered the cause for vertices being "thrown" from the graph; the when two vertices are too close together, the forces repulse so much that the displacement is magnitudes higher than it should be. This is what happens when you use quadratics such as the inverse square law.
For reference; if d = 0.01, 1/d^2 = 1000, if nothing is limiting the forces this is allowed through. The repulsive forces are calculated first so this should never happen (unless the springs are too powerful), however, in larger graphs its possible the forces push two vertices too close or something? (still doesn't sound like it should happen but its the only piece of code (so far) that exhibits such force)</EDIT>
It is relatively obvious that more complex calculations take a little more time to calculate, although if only performed a few times, it is negligible. Fruchterman and Reingold mentioned that Eades logarithmic equation for calculating spring forces were inefficient and managed to get similar results using linear equations (although I may need to check if it was the algorithm or the calculation which was inefficient).
Although I should be focusing on other more important aspects and not the software/programming part, I wanted to check whether Java would display a difference between such calculations. I found some interesting results:
for 10million iterations (had to scale for measurable data);
calculation [x - 1.5] - 185ms
calculation [x * x] - 206ms
calculation [math.log(x)] - 3822ms
calculation [math.pow(x)] - 3765ms
As you can see, using java.lang.Math significantly increases the time taken. This is most likely due to having call the method from the Math class instead of throwing it at the processor. Note, importing the Math libraries makes little difference. Bare in mind that a graph of 5k vertices in an O(|V|^2) algorithm is 25million iterations.
Just food for thought for any mathematicians or statisticians out there working with Java libraries and collections of millions of entities, and are looking to reduce runtime. Now back to implementing my ideas...
<EDIT> Thanks for the advice Chris; for those who do not read comments, Chris proposed a fairer test to determine the delay with using libraries (if any), by using Math.abs(), as pow() and log() take time to calculate anyway. The results still show a delay but it is infinitesimal in comparison to that shown above (a few ms for 10million iterations). </EDIT>
Monday, 21 March 2011
Frame-lock...FIRE! I mean Framework...
I'm not even sure what a Frame-lock is...
In any case, this week has seen my return to programming and the mess I call "experimentation". Amidst all of the joy and happiness, I am writing a rough log of my approach, my plans and my results which may one day find itself in a thesis - in one form or another (I will also use this to record the info, but to a lesser and more informal extent).
First on the check list, a testing framework. This may paint the picture of me working on a completely new and improved version of everything, but don't be fooled, I am adapting my previous work into a more flexible and controlled "experiment zone" where I can test my ideas and retrieve reliable and measurable output.
Why don't I just use the work as it is now? Well, the current implementations are rather complex and exhibit some behaviours I cant fully understand. It is behaviour like this which makes the output difficult to monitor and compare, so using a "neutral and non-reactive" framework will ensure any changes in output are solely due to the changes I make(that's the plan anyway). I expect the "framework"to be finished quickly (before the day is out).
Regular readers may be wondering what happened to my literature review. Unfortunately the weekend was less productive than I would have liked, however, I am at a stage where only little bits remain to be filled in. This will be continued when I am at home (and not sleeping, most likely the weekend).
That's all I have for now, next update is planned for mid-week, stay tuned!
NB: awesome realisation that I'm following the work of Dr. Hu! Any science fiction fans should besmiling envious.
In any case, this week has seen my return to programming and the mess I call "experimentation". Amidst all of the joy and happiness, I am writing a rough log of my approach, my plans and my results which may one day find itself in a thesis - in one form or another (I will also use this to record the info, but to a lesser and more informal extent).
First on the check list, a testing framework. This may paint the picture of me working on a completely new and improved version of everything, but don't be fooled, I am adapting my previous work into a more flexible and controlled "experiment zone" where I can test my ideas and retrieve reliable and measurable output.
Why don't I just use the work as it is now? Well, the current implementations are rather complex and exhibit some behaviours I cant fully understand. It is behaviour like this which makes the output difficult to monitor and compare, so using a "neutral and non-reactive" framework will ensure any changes in output are solely due to the changes I make(that's the plan anyway). I expect the "framework"to be finished quickly (before the day is out).
Regular readers may be wondering what happened to my literature review. Unfortunately the weekend was less productive than I would have liked, however, I am at a stage where only little bits remain to be filled in. This will be continued when I am at home (and not sleeping, most likely the weekend).
That's all I have for now, next update is planned for mid-week, stay tuned!
NB: awesome realisation that I'm following the work of Dr. Hu! Any science fiction fans should be
Thursday, 17 March 2011
nonesense title here
I'm once again behind in my master plan.
Fortunately I bring good tidings, I have written up the majority of notes and am currently in the process of refining what is written so it resembles some form of English. Only 4 days behind, however, mindless programming and hacking is my strong suit (doesn't say much for my other suits heh), and will be making a comeback next week (if the literature review is not complete by then, I will temporarily abandon it as this has gone on too long).
It will be nice to get this out of the way so I can get back to what I love most, so stay tuned!
Fortunately I bring good tidings, I have written up the majority of notes and am currently in the process of refining what is written so it resembles some form of English. Only 4 days behind, however, mindless programming and hacking is my strong suit (doesn't say much for my other suits heh), and will be making a comeback next week (if the literature review is not complete by then, I will temporarily abandon it as this has gone on too long).
It will be nice to get this out of the way so I can get back to what I love most, so stay tuned!
Monday, 14 March 2011
I should have prepared...
It's that wonderful time of year when the coursework deadline for undergraduate is only a few days away (today), causing widespread panic and chaos in computer labs everywhere. Unfortunately for me, in their time of need, I am next door, and have this bad problem of not being able to say "no".
As with all excuses, there is a reason: I have not yet completed my literature survey as I had intended. I had hoped to spend my weekend working upon it, but due to other areas of life that require attention, I was unable to follow through with that either.
So I am left today, with the task of completing my reading/write up. Hopefully, tomorrow will see my return to the word of experimentation. One can only hope.
As with all excuses, there is a reason: I have not yet completed my literature survey as I had intended. I had hoped to spend my weekend working upon it, but due to other areas of life that require attention, I was unable to follow through with that either.
So I am left today, with the task of completing my reading/write up. Hopefully, tomorrow will see my return to the word of experimentation. One can only hope.
Tuesday, 8 March 2011
Java's making fun of me again
Previously, during my monthly meeting with supervisors, I shared results for my different implementations of multilevel drawing algorithms (regular readers may recall an issue I had with one whereby the global position was ignored), and found what was assumed to be a mistake on my behalf in the timings it took to run the independent algorithms.
In what I will now call Algorithm A, 3elt took too long to run and so I ended it prematurely, giving the following:
In Algorithm B, I had a similar problem with finan512, which I also ended prematurely:
At first I did not notice this, probably because I was just happy to get results, but it was highlighted in the monthly meeting wherein I explained that they were the results Java gave. Eventually I just assumed I had accidentally copied the same result over, as it seemed unlikely Java would give the same result twice.
Today however, during a break from my reading/writing, I ran my application again to see if I would ever get an output from finan512 (by leaving it for however long). Eventually I stopped it whilst it was placing the 6th level of the graph (of 26 levels), and noticed something that looked familiar, the output : 2147483647.
It turns out I was mistaken, I had assumed this number to be the runtime in milliseconds as it was the last item to be printed out. In fact, this is the Java Result (a number separate from my application) and coincidently the biggest value of an integer in Java (32bit).
http://wiki.answers.com/Q/Why_is_2147483647_the_biggest_number_Java_can_handle
An embarrassing mistake but better to identify it now than for someone to question it at a later date. It should be noted; normally, when an application is stopped, NetBeans outputs; "BUILD STOPPED (total time: n seconds)" which may further explain my confusion. Funny old world.
In what I will now call Algorithm A, 3elt took too long to run and so I ended it prematurely, giving the following:
Graph Time (ms)
3elt.graph || 2147483647
In Algorithm B, I had a similar problem with finan512, which I also ended prematurely:
Graph Time (ms)
finan512.graph 2147483647
At first I did not notice this, probably because I was just happy to get results, but it was highlighted in the monthly meeting wherein I explained that they were the results Java gave. Eventually I just assumed I had accidentally copied the same result over, as it seemed unlikely Java would give the same result twice.
Today however, during a break from my reading/writing, I ran my application again to see if I would ever get an output from finan512 (by leaving it for however long). Eventually I stopped it whilst it was placing the 6th level of the graph (of 26 levels), and noticed something that looked familiar, the output : 2147483647.
It turns out I was mistaken, I had assumed this number to be the runtime in milliseconds as it was the last item to be printed out. In fact, this is the Java Result (a number separate from my application) and coincidently the biggest value of an integer in Java (32bit).
http://wiki.answers.com/Q/Why_is_2147483647_the_biggest_number_Java_can_handle
An embarrassing mistake but better to identify it now than for someone to question it at a later date. It should be noted; normally, when an application is stopped, NetBeans outputs; "BUILD STOPPED (total time: n seconds)" which may further explain my confusion. Funny old world.
Monday, 7 March 2011
Eternal Erudition
Reading once again. Instead of a description of my reading methodologies, or a descriptions of what seems to be the hundreds of papers I've read (I'm not joking, I'm expecting to hear from Green Peace regarding the number of tree's I've had killed), I will merely say: "I think I get it".
I have read a lot of material on the graph drawing paradigm, not just on drawing general undirected graphs, but other areas too - aesthetics (which is assumed to be a requirement in modern papers), projection and perception (also required in anything with more than 2 dimensions), data structures, how to draw different graphs (i.e. planar, trees, star, social network, WWW etc), partitioning, visualisation-specific papers and probably some others which I have temporarily forgotten.
I have also seen many techniques for drawing general graphs, ways which these methods can be scaled, the advantages and disadvantages of these and the standards expected from modern drawing algorithms.
Why do I bring these up you ask? Well chances are I'm going to forget something simple and if its here, I can find it again with ease. As a consequence, you get to see my unfinished, mental-made-virtual, list of reading categories, lucky you.
It is however, coming to the end of this "reading period". I will be looking to write up my findings into a draft literature survey/review, and continue with experimentation using the notes I have found, with the intention to come back in a month or mores time, to continue and reread everything to ensure I haven't missed anything.
I will leave you with a great evaluation of drawing techniques by Yifan Hu; Algorithms for Visualising Large Networks; July 2010; which has helped point out a few techniques previously missed (Stress majorization).
I have read a lot of material on the graph drawing paradigm, not just on drawing general undirected graphs, but other areas too - aesthetics (which is assumed to be a requirement in modern papers), projection and perception (also required in anything with more than 2 dimensions), data structures, how to draw different graphs (i.e. planar, trees, star, social network, WWW etc), partitioning, visualisation-specific papers and probably some others which I have temporarily forgotten.
I have also seen many techniques for drawing general graphs, ways which these methods can be scaled, the advantages and disadvantages of these and the standards expected from modern drawing algorithms.
Why do I bring these up you ask? Well chances are I'm going to forget something simple and if its here, I can find it again with ease. As a consequence, you get to see my unfinished, mental-made-virtual, list of reading categories, lucky you.
It is however, coming to the end of this "reading period". I will be looking to write up my findings into a draft literature survey/review, and continue with experimentation using the notes I have found, with the intention to come back in a month or mores time, to continue and reread everything to ensure I haven't missed anything.
I will leave you with a great evaluation of drawing techniques by Yifan Hu; Algorithms for Visualising Large Networks; July 2010; which has helped point out a few techniques previously missed (Stress majorization).
Thursday, 3 March 2011
Is this Enlightenment?
Probably not, but its close enough to make me happy.
This week, I have continued my reading/research/sleeping, and have now realised that the material in the papers is relatively "limited". I say limited, in that many of the papers I have read contain very similar information which is only slightly different (it includes a different method of coarsening or it uses a different form of vertex placement, which has been used previously but not in this very specific context).
Of course there are the rare papers which show something new and useful, however, many papers that demonstrate a "new feature" are more specific to types of graphs or to different methods of viewing, and not directly useful. Having reached this point, I still have a mountain of papers to read having recently discovered that Google Scholar shows you where papers have been cited. (Instead of reading the papers in a reverse chronological order, I can now look forward at more modern papers).
Having read through and compared a large number of papers, I am beginning to make several decisions about which mechanisms and techniques I wish to use in my future work, and which not to use. There is still a long way to go before I make any real world changing plans, and future work is very much fragmented.
If I don't give another update tomorrow [Friday], you can make the safe assumption that next week, I will be returning to the wonderful world of journals, papers and gibberish they call 'knowledge'. If all goes well, I am planning to have a significant part of my draft literature review complete, but this may be me being over-ambitious. We will see, for now, goodbye and have a good weekend.
This week, I have continued my reading/research/sleeping, and have now realised that the material in the papers is relatively "limited". I say limited, in that many of the papers I have read contain very similar information which is only slightly different (it includes a different method of coarsening or it uses a different form of vertex placement, which has been used previously but not in this very specific context).
Of course there are the rare papers which show something new and useful, however, many papers that demonstrate a "new feature" are more specific to types of graphs or to different methods of viewing, and not directly useful. Having reached this point, I still have a mountain of papers to read having recently discovered that Google Scholar shows you where papers have been cited. (Instead of reading the papers in a reverse chronological order, I can now look forward at more modern papers).
Having read through and compared a large number of papers, I am beginning to make several decisions about which mechanisms and techniques I wish to use in my future work, and which not to use. There is still a long way to go before I make any real world changing plans, and future work is very much fragmented.
If I don't give another update tomorrow [Friday], you can make the safe assumption that next week, I will be returning to the wonderful world of journals, papers and gibberish they call 'knowledge'. If all goes well, I am planning to have a significant part of my draft literature review complete, but this may be me being over-ambitious. We will see, for now, goodbye and have a good weekend.
Tuesday, 1 March 2011
Forever reading
Not much of an update this week, much of my time has been spent reading, which seems to be one of the most time consuming and repetative tasks I have come across so far.
I am constantly adding to a mountain of notes, and have a large number of mechanism/algorithms/code that I am looking to implement in order to draw graphs as accurately and quickly as possible (in respect to my ideal final implementation of a "dynamic multilevel placement and exploration algorithm").
However, everything I have discussed and described in my notes, is just adaptations of already existing work, and nothing particularly original. Regardless, I am sure I will come across an idea that has not yet been used/implemented and am hoping to have a significant part of my (first draft) literature review completed towards the end of the week/weekend.
Thats all for now folks, i'll update when I have something more substantial to say.
I am constantly adding to a mountain of notes, and have a large number of mechanism/algorithms/code that I am looking to implement in order to draw graphs as accurately and quickly as possible (in respect to my ideal final implementation of a "dynamic multilevel placement and exploration algorithm").
However, everything I have discussed and described in my notes, is just adaptations of already existing work, and nothing particularly original. Regardless, I am sure I will come across an idea that has not yet been used/implemented and am hoping to have a significant part of my (first draft) literature review completed towards the end of the week/weekend.
Thats all for now folks, i'll update when I have something more substantial to say.
Subscribe to:
Posts (Atom)