1year 3months: Time goes too quickly

This week I have been preparing/collecting some more results for the paper, on top of writing the paper.

But! the main change this week is the discussion of the paper with my supervisors. It seems by adding the multi-matching to my algorithm and generating some more results for the paper, I have been slowly hijacking the real focus of the paper, therefore, I will be splitting the paper into two. One focusing on the coarsening tree approximation, and the other, multi-matching and its affect on the coarsening tree structure, and how it can be useful for much larger graphs.

This change makes it so much easier to write the paper, and will be better for other readers to understand the point of the research. Currently, the supervisors are checking the draft version of the paper and I will be giving them the results to accompany it, very soon (I want to ensure I have results for the graphs tested by Hu).

Not much else to update upon this week, much of the time has been spent writing or proctastinating to avoid writing, or outright ignoring the need to write. Next week I will be working from home and will be finishing the results/conclusions section of the paper, with a continuation on the multi-matching, before I get too detatched from it.

Have a good weekend!

1am - 4am: A PhD students supreme state

This week I have been working on the death machine paper, which is progressing nicely. The majority is now complete, with only the results and discussion of which, to complete. There is also the checking, however, I am going over it again as I type (for what seems like the 50th time) and making any necessary changes, so checking wont be too much of an issue.

I have also been writing some awesome lecture slides for Computer Algorithms and Modelling so I have been distracted/preoccupied by that.

Additionally, I have been working on the multi-matching again, and am just having some small issues implementing my choice of data structures (getting a lovely concurrency exception with hashmaps, which make my life that little bit more interesting ).

So it seems everything is head towards a nice little finishing point, or at least resting point until we get onto the really cool stuff (dynamic graphs here I come!). I am once again stating I want to have my paper done by tomorrow, but I may aswell give in and say the end of term. I will still be awaiting results for the multi-matching but it is my aim to have a draft completed soon, especially as I no longer have any distractions.

I will now leave you to continue with my dead machine paper, and hopefully you will an update next week.

Stumbling Block

To be honest, it's bit of a stressful time of year - presents need to be bought, paper in writing, applications need developing, tutorial material needs creating, research committee requesting forms that should have been submitted a year ago and on top of all that its getting cold on a morning. No matter, it is time for a quick update.

Unexpected Issues (Research Forms)

A recent problem has arisen whereby my research has not yet been approved. Research students are expected to submit a form detailing their research to a commitee for acceptance in the first few months, however, I did not (I thought an application had been submitted but it was a different form). I have therefore been asked to resubmit a form (only a year late) for them to check my topic and accept or decline my intended work.

A little bit of a morale crusher as the Commitee whom recieves the form should have reminded me when I need to submit but did not, and have accept an annual update since then ("we are happy with your progress") suggesting they dont follow my progress. Not to worry though, simple form to submit, so hopefully there wont be any complications (you just know there will be).

Paper

The paper has stalled (what with the unexpected issue above). The content is mostly there, but just needs to be ordered appropriately. Results regarding the matching have not yet been included as they were scheduled for collection this week.The aim is to complete some other tasks first (below), then complete the paper and the matching this week (paper first, matching can be added after).

Tutorials

As part of my tutoring, I am "helping" develop some last minute tutorial material. Though trivial, this takes time and I had forgotten that it was expected this week, so am rushing to complete that today. Marking will also be arriving soon, so I am not looking forward to that (and as its getting closer to the deadline for some courses, I am being treated as Google.

Coldness and Other Stuff

It's cold. I am also making stuff.

FIN

That's all for now, I will attempt to update later this week but I'm a little busy so may not find time. But do not threat, I will let you know if anything drastically important or life changing happens. TTFN.

Update 1.12

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!

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.

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.

Funny thing: all my results are worthless (or are they?)

 

It's one of those days... Let me set the scene using my amazing descriptive powers; picture me sat at a desk. A light above me. Carpet Below.

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.

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

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.

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!

To Hell with it All!

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!

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.

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.

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!

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... 

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.

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.

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.

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>

Soon.... Results

Another late post this week. I partially blame my lack of concentration on tutoring and other extra curricular activities, but they're still excuses...

Anyway, monthly meeting with supervisors yesterday came to a happy conclusion: I no longer have to worry about implementing the Eades best viewpoint finder. Instead, I will continue with my implementation of finding the 'polhodes': http://en.wikipedia.org/wiki/Polhode. [May be incorrect but the description matches].

Essentially, it is what I have implemented previously; finding the two or three most prominent axis in the graph (greatest direction of edges) and then move the viewer perpendicular to them. Bad that I didn't find the paper but reassuring that I was on the right lines without knowing it existed.

Before this, I am preparing my results for the 2D versions of the algorithms. The testing 'suite' is almost finished and last night was the first night of leaving my application working away (as a test run to ensure no errors are found). I have a few simple changes to make, but I should have full tests running over the weekend, with my first set of real results on Monday.

After I have got these running (later today), I will be continuing with the 'polhodes' work so I can finally test the 3D graphs. Again, this shouldnt take too long what with previous coding already existing.

This all finally leading to me returning to the domain of dynamic graph drawing! In retrospect, I feel slightly let down that I have not yet started on it, now being in my second year. Could be worse though, so back to work I go! Will update next week, hopefully to discuss my results, if not, the failure of the testing suite, and the rest of my work.

Freshers Week and Doom

This week I have been distant from my work, helping the CMS Mentors. This has involved me helping the new University of Greenwich students getting settled in and helping in the lab days, similar to last year.

My work has been slower because of this, but due to an issue with my viewpoints research, I have been avoiding the continuation of my work. I have a meeting with my supervisors next week so hopefully that will help decide my next plan of action.

Today I have been writing (refining) the tests for counting edge crossings and edge lengths for the 2D implementations, and preparing for the scaling forces (changing the power of repulsion and maybe spring forces in order to find the best forces and determine a default scalar value).

I will be continuing  with these tests and will continue to think of a method to calculate the final projection so 3D drawings can be tested as well.

Will update tomorrow or next week dependant on progress.

Not as easy as anticipated , how original

A week since my last post and I am still stuck on the viewpoints gibberish. Unfortunately I am stuck at a crossroads, with no idea where to go (self -confusion and the internetz to blame mostly).

Whilst reading throughout the papers, I have been neglecting the limitations of my understanding, and have stumbled on a problem. When a drawing is rotated, the space itself is being rotated as opposed to the individual line segments (I also use this rotation as a form of user input to find the best viewpoint manually). When calculating the 2D projection of the 3D drawing, the coordinates used are those held in each vertex, which are the same as before, however, the viewpoint has changed, so in the ideal world, I would calculate the angle of the viewpoint, and calculate the change in position of each vertex/line segment... no.

Behold, in theory, there is an easier method. I could use the projection matrix used by OpenGL project the drawing to the 2D viewing area, to determine the line segments and run the various tests upon those. Woefully, I cannot find a method of doing so.

Another method I have just though up, would be to reverse engineer what's happening within OpenGL and use this. Unfortunately, I am less keep on the mathematics of it all, but it doesnt look like I have much choice.

I cant help but feel there is something I am missing in this, some easy method of doing this that I am overlooking. I am aware there is a test for occlusions within OpenGL, which may help testing Eades et al. 'Finding Best Viewpoints for 3D Graph Drawings'. I am sure I will find out soon enough, but I am still disappointed as I did not want to spend so long on something which is not a (notable) concern in previous papers.

I will update again next week, for now, have a good weekend.

Forever Reading (again) + additional crazy

Research is slow. Apparently, finding good viewpoints is meant to be as slow. Most of the techniques I have looked at concentrate on viewpoints which do not cause occlusions, which is computationally expensive. Occlusions are undesirable as it can hide information within the graph, however, I am under the impression these approaches work well for smaller graphs, but are less effective in larger graphs.

NB: there are many methods which use these good/bad viewpoints and have different approaches to calculating them

Larger graphs are very likely to have occlusions, no matter which angle the drawing is observed. Although still offering the better viewpoints (by calculating the viewpoint with less occlusions), I am starting to see why it is not used (or at least referenced) in other placement/drawing algorithms where the viewpoint is left to the user.

There are other approaches which I have yet to research but a naive first glances suggests this area is lacking interest from researchers looking for a quicker and more ideal methods for finding viewpoints based on more than one criteria (see Purchase for multi-criteria and Eades for implementing more criteria in graph drawing.

Now for some monthly Carl Crazy; when looking at graphs, the more we can see, the more we can normally understand about the graph, even in cases where edge crossings can be seen. For example, rotating a cube so it is observed at a 45degree angle, we understand a lot more about the cube than if viewed head on (you could argue a planar drawing does this with no crossings, but the graph is warped and edge lengths suffer).

Using this same crazy, if you look at an edge within a graph, you ideally want to have the view perpendicular to it (or you will be looking at it from an angle which shortens the edge) in order to see it. If we look at this on the whole, we would be looking for the average direction of all edges within the graph. If the view was perpendicular to this, the observer would be looking at a view which offered the maximum view of all edges in the graph, albeit with occlusions/crossings.

<EDIT> This is a rather silly version of Kamada and Kawai 88, albeit ignoring the normals of the image and instead choosing to use the average edge direction to rotate the graph. In practise, this isn't as adequate as one would have hoped, with large numbers of occlusions and edge crossings. May be best to stick to Eades et al.Best Viewpoints for 3D Graph Drawings).

Of course I will continue reading, but I will test the crazy regardless due to the speed increase it offers.

That's pretty much all for this post, here's a picture of some output to liven this otherwise boring post up:

finan512.graph, drawn using 3D quadtree and 2D contraction approx. with different forces for each. The testing of parameters will hopefully find output for 'quadtree' which closer resembles that by Yifan Hu (although currently it is very close to his output of MSE(2). )

I've been following my plan? WTF?

As the title suggest, I have atypically been following the plan I laid out last week, so here is my progress:

1. Changing QuadTree and Grid to Components - Complete
• Some issues came from bad refactoring
• Vertices and Edges have now been abandoned for the Component but may return during memory optimisation (smaller footprint)
2. Finish Testing Suite - Ongoing
• Currently researching methods for finding the best viewpoint (not necessarily most efficient)
• "Plug and Play" attempted but requires additional code in most cases, albeit minimal
• Tests for 2D mostly complete; 3D await for viewpoint research
3. Convergence - Complete
• successfully implemented the convergence finishing rule
• preliminary testing shows using a tolerance of 0.001 gives longer running times that 50iterations
• 0.002 is on par, any higher gives faster results (but results may be reduced quality
4.  Matching - Ongoing
• no real progress since last update but still have the option to coarsen all incident vertices to a selected vertex
5. Comparison of Algorithms - Not Started
• Waiting on 2. and 4.
6. Yifan Hu implementation vs Contraction Approximation - Not Started
• waiting on 5.

Most of the work is now dependant on implementing a method for finding the best viewpoint, which will enable me to write accurate tests for the 3D output. There has been no thoughts on which initial starting positions should be used for the fairest results, a comparison of pre-set and random positions will be undertaken.

I will continue to work with this plan as it seems to be working for me so far. An update will be posted later this week. Almost one year since my start, quite scary...

Weapon C: because Weapon X was taken...

As mentioned yesterday, my objectives this week have been a bit of a mess, so I have finally decided to put them into a reasonable path;

1. Component data structure for BH and Grid
• Change my previous implementations to use the same data structure for fairer tests
• Can/Should be able to add to Weapon C with own structures but will not be as fair
2. Finish 'Weapon C'
• Plugin functionalities ( whether using Component or own Data Structure )
• Tests ( edge crossings, angles, edge lengths; to be used ubiquitously )
• Projections ( dependant on speed but finding the best viewpoint for said tests ) 
3. Walshaw Convergence
• Old news now, but change from iteration based to convergence based (before default forces found)
• This should be applied so either iteration or convergence can be used
4. Matching/Clumping
• Finish off the clumping/matching I had started
• User defined sizes; find matching with 'n' vertices
• NB: several ways for this, which gives best results? only one way to find out, EXPERIMENTS!
5. Comparison of algorithms
• testing in Weapon C (testing done entirely by application, increasing params without user input)
6. Comparison of optimised CApprox against Yifan Hu's own results

As a side note; I should remember that using random positions initially can alter results, as vertices can be given a better placement in some scenarios. Dependant on the inconsistency of results, using strict initial positions may be better (or worse), we will see.

Going nowhere quickly

This week has been very slow. Much of my time has been moving between bits of my work trying to fill in the gaps I missed when originally implementing the different algorithms, and attempting to implement an efficient method for matching/clumping multiple vertices during the coarsening process.

The multi-matching has proven to be quite a difficult to implement; it is easy enough to match two vertices by just looking at the list of edges, it is also easy enough to match all vertices connected to one vertex with this same list, the issue arises when coarsening with a user given number (i.e. 3). This is all due to the way I have coded my implementation, it is easy enough to create a list of adjacent vertices for each vertex, but this would require a significant amount of memory.

I really shouldn't be concerning myself with efficiency and memory just yet, however, I dislike the idea of making an application slower just to implement a different method of matching. I guess beggars cant be choosers.

Other work has been preparing to change to the convergence finishing criteria as opposed to the current method of running the placement algorithm 'n' times (where 'n = 50', give or take a few). I have also dug up the Huang and Eades paper's for the cos/sin forces for better graph untanglement.

In a random 'crazy of the month' type deal, I am now concentrating on this convergence idea proposed by Walshaw (when a vertex no longer moves further than some tolerance, the graph can be classified as converged, using the cooling schedule of Davidson & Harel). I hope to find a way of moving vertices into more accurate positions, requiring less iterations of the placement algorithm (instead of my current "how to make the algorithm" faster).

I will of course also be continuing with the test suite which currently awaits my finished algorithms. Reading back on this, my work load appears to be quite a mess, with intentions to do different bits in the same time as doing what I should be doing. Maybe I can clean this up a little... I guess we will find out soon (yay more plans which will never see the light of day again).

That is all (I can remember) for now, I will update tomorrow or next week dependant on progress. Have another good weekend.

Boom! Friday.

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".

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.

(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:

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.

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.

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.

 

 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!

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:

55grid.graph	3elt.graph

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!

Planning before the launch (or lunch)

Being happy with  my quad tree implementation (for now), I have begun on my contraction/binary tree approximation.

Most of the work has been paper-based, refining my plans for the easiest and less disaster-prone way of coding it out. Unfortunately the desired plan requires me to change significant amounts of the code, however, the changes are simple in theory and can be applied to older implementations with ease (of course, now that I have said 'ease', I'm doomed).

The coding has been started and I am roughly half way through the implementation, so I expect it completed by next week (including refinement). For now, that is all, but I intend to upload some scans of my theoretical scribbles, with a little discussion about what I'm attempting to do, in the near future.

For now, you don't get any pictures either, ha!

(fine.. here's one showing the normally dense hole in the centre of the graph, 3elt, being pushed out like a gravity well).

Forward, Upward, Progess, Stronger

Behold, I have fixed the z-expansion issue!

The cause? A small insignificant piece of code I had overlooked as I made the incorrect assumption it was in working condition based on its use in other force directed placement algorithms I have implemented (FR_limited, means nothing to you but its a personal variant of the Frutcherman and Reingold algorithm).

The detailed cause? A small piece of code used to normalise the forces when applying them, incorrectly added the same value twice. This was probably a change of mine made several weeks ago (used as a way to monitor behaviour in sections of the algorithm - not really important), and without changing it back, forgot about it.

Interestingly enough, with this fixed and my previous output resembling how the graph should look, the output this time does not look adequate, having undone whatever I did last time (dammit). Fortunately the changes where on refinement techniques so I just need to continue following my notes to get back to reasonable output.

A video, along with the previous posts video, will be available shortly. Below is the output for 55grid, drawn unoptimised and still buggy, in 2 seconds.

Next, my own contraction approximation. This will require some large scale changes to the coarsening scheme and Quad Tree currently employed, but has already been prepared for in the code (to some extent).

I predict this will take about two weeks assuming there are no stubborn problems, so the real time could be anywhere between tonight and 6 months from now (I think my expectations can be a little off sometimes...). Regardless, I will hope to have it done much quicker than this recently fixed problem took to resolve.

More Changes

Once again the output has changed, and although I cant tell if for better or worse, the results are making me a little happier.

Behold, 3elt;

As can be seen, the original graph is not exhibiting the structure as shown in my previous post (and is not easy to determine which graph is actually being drawn). Although the increased randomness and unorganised structure, the Z-axis expansion has changed to show a ball like structure (as opposed to +ve to -ve change shown previously). When rotating, the graph appears ball like as I would have liked (instead of the flat structure normally drawn), but the edges through the centre of the graph give it the unattractive view seen above.

The changes to cause this were insignificant changes to segments of code, so I will investigate how these segments affect the z coordinates of edges. Until I have further information, I would leave you with a video but Blogger is being rather difficult about playing it, so I will edit/upload when I can.

Why does it lie!

Interesting development last week, changing the order of some of the code and fixing some minor problems gave a slightly different output. Observe below;

The graph 3elt drawn in 3dimensions using the Barnes Hut approximation. As can be seen, the graph is drawn very well (much like outputs seen previously) when seen from the front (0,0,1 > 0,0,0), however, when rotated (1, 0, 0 > 0,0,0) the view shows the same z-expansion shown previously.

This makes this work, the most awkward and infuriating peice I have come across thus far. The code is now clean and most errors identified and fixed, but this output is awful. From one direction, the graph is fine, but any other, it isnt? What kind of sorcery is this? Why does my algorithm hate the z-axis? What is the significance of edges changing direction half way down? is that 0,0,0?

As always, I will continue to search for my mistake and will update accordingly. For now, here is my favourite graph, data, showing the same problem.

Ripping it to Shreds

As can probably be gauged, I'm very bad with estimating how longs things take. The weekend plan went to hell when unexpected circumstances left me without a laptop/computer (and there's only so much you can write on paper before thinking "can I even do that?").

I have been dropped to ripping my work to shreds to find this cause, and low and behold, I have a very good idea what's causing it. The problem lies in the repulsive force calculations, it seems as though the algorithm is taking nodes of a tree which would otherwise be null, or taking its own branch, and adding the additional force.

As my coding forbid this, it's my theory that I have hacked something up elsewhere, which caused the siblings of a child to be included in the force calculation, even if they're empty quadrants of the quad tree. My code-cleaning made this a little easier to read as the hacked code is hidden from plain sight.

Whether or not this is the issue is subject to some testing (once I finish re-engineering the code), but one thing is now for sure, the problems are with the forces, specifically repulsive force (thanks to some digging, ripping and shredding). 

I will update again soon, in the mean time, enjoy the wonderful cloud cover outside.