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>
No comments:
Post a Comment