Multiply the what by the who and where?

Possibly my final update for 2010, and what a good year it's been, given the chance to undertake an MPhil/PhD, what could be better? (dont answer that, it will make me sad).

SO back to work, back to reality, back to trigonometry? Having cleaned up my code a little, identifying some new issues, along with some old, I've been looking at drawing edges (may help understand some old problems if I can visualise it).

In theory in appears relatively simple, which concerns me as nothing is ever THAT easy, but my understanding is:

• calculate the size of the edge (pythagoras)
• calculate the midpoint along the edge, so where the edge will be placed/drawn
• calculate how much the cylinder should be rotated to get to the correct position with trigonometry

 I have yet to implement this as I am still working on the fine details (mostly of which axis' to rotate around).

Another development, I have now implemented a mechanism to focus on the center of the graph automatically (no manual translating for me!), using the coordinates of all points to find the center point of everything, which appears to work well.

Nothing more to really update upon, continuing my re-reading/note taking for the literature review is probably the next best highlight of the week. Other than the whole "it being Christmas" thing. Time to end I guess.

Merry Christmas!

Reconcile the madness

ITS CHRISTMAS!

Now, moving on, last week we had my monthly meeting which for me, focused upon demonstrating my work. This would have been easier if my work output anything useful to demonstrate, but regardless, over the past three months I have successfully implemented Eades heuristic and Walshaws multilevel algorithm, with an attempt (good attempt) being made with Veldhuizens work (although showing this to anyone who isnt me, is quite difficult it turns out).

As I mentioned through the meeting, I have been writing a small report about my progress over this time, with an initial version here. The un-reconciled code can also be found here (self explanatory with comments here and there). NB: you will need NetBeans with OpenGL and GLUT libraries to use these files.

Now onto the other parts of the meeting. There have been several changes requested, the two most major of those are:

• Reconcile the code into a more appropriate and useful package, involving a modular based approach so different parts can be used by other applications.
• Animate everything, or more specifically, animate any changes that happen through out the graph from reading the file to infinity (and beyond).

Other, lesser emphasized, changes include:

• Draw the edges using GLUT cylinders
• Check all Eades implementations for old/new coordinates rewrite*
• Make the drawer class a tad more user friendly
• Write some testing, to check when something is changed to see where errors are
• Literature Review - begin to summarize and write up the several thousand notes sprawled across the papers I have read

All fairly reasonable, although some obviously more difficult than others, and a few may/will take longer than than one month (my normal personal deadline). Notes/minutes for meeting here.

*My Eades implementation currently uses the new coordinates of vertices to calculate the position of other vertices, instead of the older vertices. A handy work-around described during the meeting uses an array to hold the new vertices, whilst the algorithm uses the old, and updates them when finished.

It is my plan to have the code reconciliation/modularisation finished before the new year. I will also investigate the edge drawing as this is an interesting problem I want to test myself with.

For now, I wish you all a Merry Christmas and a Happy New Year!

DAMMIT! Oh wait... nope dammit!

Work this week has been exceptionally slow.

Tuesday was spent looking through previous implementations to find if there is anything I can use (and also to reinforce my understanding of what my code actually does). Turns out my understanding was correct in the first place and I was just having a mental breakdown...

Wednesday and today (Thursday) has been spent attempting to get output from my Veldhuizen implementation. Although there is an output, it is not correct due to a small bug which has yet to be debugged.

Attempt: The plan is to have the FDP algorithm run over the graphs for a small number of times to get the premature coordinates of the uncoarsened graph, a "key frame" similar to that in Veldhuizen's description. Each iteration of this step would keep changing and outputting the latest coordinates until a pre-set finishing point.

Problem: The way in which the algorithm works, the coordinates are based through the different graphs, but are not saved (so the coordinates are always starting at zero).

Fix: save the coordinates, simple as. The issue with this fix is that its not so simple as that. The method of storing graphs makes retrieving the levels difficult.

As an alternate route, to try and speed up my work, I may just choose to hold graphs in their own Graph type Component, which will hold the vertices and edges for that graph. That would make this step easier but less efficient, which for some reason I am obsessed with - even though I don't need to be yet!

In other new, I am mistaken when I refer to Java as comparing memory locations in my latest implementation (as referenced in my previous post). Java still compares Object or Component (whatever I am using at the time), but I only see the memory location because I am printing the Object/Component.

Also this week, I marked my first batch of coursework.

Anyway, back to work... one week left before my monthly meeting with Chris Walshaw and Alan Soper. I am intending to have something physical to show other than thousands of lines of useless code (such as graphs and pretty lights to distract them while I run away). The aim is still to have my Veldhuizen work completed (to my understanding of what it does, as recently I've been avoiding the scary maths equations he uses).

That's for all for now, my next may very well be from a padded cell, so see you soon? Heh, cya!

Time flies...

I have only just realised how long it has been since I gave an update, it's true what they say, time flies when your stuck trying to fix problem after problem, getting nowhere slowly.

On a more optimistic note, I have spent the majority of the past 6 days concentrating on fixing/improving my implementation of Walshaw's multilevel algorithm for drawing graphs, with the focus on making it dynamic (so implementing Veldhuizen's work) at the same time.

I have once again, implemented an iterative coarsening algorithm which coarsens an original graph (G0) into coarser graphs until |V| is equal or less than 2. I am looking to investigate whether this should be capped, and may attempt to limit coarsening where it may not be necessary (coarsening a graph of 1,000 vertices to a graph of 50 or 25 vertices is good, but to a graph of less than 10 vertices doesn't seem worth the computation, however small that might be, but this is what investigation is for).

Although using Component objects, my implementation compares and uses memory pointers to identify edges and vertices. EDIT: after some research, Java still compares the objects as normal, the output is just a memory pointer to the object - blasted naivety.

I have attempted to further understand Velhuizen's work, albeit still confusing with the amount of equations being thrown around and the ambiguity of some of the wording. I intend to follow on from his "key frame" analagy, and use a FDP algorithm (such as Eades, or the more efficient, Frutcherman and Reingold) to draw the graph bit by bit, allowing for a slower but incremental drawing of a graph.

NB: at this point, I am only attempting to animate the drawing of a static graph, and not implement an on-line version such as Veldhuizen's (just yet).

My main aim for the rest of this semester/term/year is to implement a dynamic multilevel drawing algorithm
which can coarsen graphs to more than 3 levels, and still provide aesthetically pleasing results. With less than 2 weeks left, my supervisors are right in this being an ambitious aim, but it wouldn't be as fun if it wasn't a challenge.

Noble 6, out. (Yes I'm that sad!)

NB2: I have yet to finish my presentation of results from my implementation of Walshaw's work, mostly due to the coarsening failing last minute, but be assured, this is planned to be uploaded before the end of the week (in fact, I am going to say a deadline of Wednesday so I don't forget - again).