Interesting... Gibberish, but interesting...

<EDIT>
re-reading this, I just remembered, Peter Eades commented on such findings in his "Heuristic for Graph Drawing" note.See section 3: Examples - Figure 1(a) and Figure 1(b). This however, is attempting to highlight that when starting positions remain static, the structure of the graph can cause outcomes like this, even for graphs of similar size. Another comparison has been added below. 31/01/2011
</EDIT>

Just a quick update.

Come across an unusual but almost predictable pattern during my play time. Whilst checking over graphs of reasonable size (~50 vertices) to ensure the coarsening works, I noticed some graphs drew well where others did not. In retaliation, I attacked the initial positions, making them a tenth smaller, only to find the graph that drew badly drew well, and vice versa.

Its hard to explain with text and no images, so here are some images:

This first image shows two graphs of similar size, a 5x5 square matrix, and a honeycomb of 19 hexagons. As can be seen, the matrix has a relatively good layout (ignoring the edges in the background), whereas the honeycomb does not. Note, these are drawn with initial positions of x = i +1, and y = i, where i is the vertex number.

Now for the change, x = i+1/10, and y = i/10

The square matrix has deformed, caused by twisting in the coarsened graphs. The honeycomb, on the other hand, has a reasonably good layout. This shows initial positions of vertices can have an effect on the layout. More tests, including randomised initial positions, will allow me to see whether this is as important as I would like to think.

<EDIT>

Given rand values (using Math.random() to return values of 0.0 >= x,y < 1.0 ), the graphs are very similar to using i+1/10. However, as the initial coordinates are different every time the project is run, the outputs can be different each time (and so there's no guarantee you will see the same aesthetically pleasing layout as before).

</EDIT>

Other changes, such as the number of times the force directed placement algorithm is run, also affect the layout but this is common sense (and is shown in Peter Eades heuristic for Graph Drawing). Why have I included this almost useless point? in case I forget, also, I haven't quoted a paper in a while and feel I may be neglecting them.

Anyway, just felt like updating this little bit, may hopefully of be use one day. All the best.

The Real World (of fail)

Apparently, I haven't updated my progress for a while (an entire week, the horror). This can be for two reasons; I'm slacking and being generally lazy, or, I'm working full capacity and have only just realised what day it is. Hopefully you will all believe me when I say its the latter, as I have been working on getting results. Big results.

Over the past few days I have been attempting to get a reasonably working implementation of Walshaw's multilevel drawing algorithm for static graphs, however, all attempts have been futile. After the program has finished (it should be noted, I am so needy that finishing successfully is regarded as an achievement), the coordinates for each vertex is Na, which experience suggests is due to singularities or problems with my multi-level implementation.

In the realm of checking for line segment intersection, I have done some research but not yet made anything. A pattern of finding the equation of the individual line segments and solving the last and first point of the lines for each and comparing the value between the lines, seems to pop up a lot. I will elaborate and discuss more when I'm comfortable with the process.

Next, LITERATURE! It's no surprise that whilst waiting for these lengthy applications to complete, my work is limited to guesswork and maintenance, so I have spent more time, this week, reading/note taking in preparation for the literature review.

For now, I hope this update shows my direction and (hopefully, by tomorrow) progress. [I have just been assaulted by a horde of students requesting help... interesting]. That's it for now I'm afraid, next update tomorrow (Friday) or Monday, possibly with some results worth mentioning.

PS. a picture I enjoy looking at, (what was a) dynamic single level force directed placement using Eades heuristic. Tried to export, or record to GIF but no luck so far. I enjoy watching the "snapping" effects as two vertices pass each other closely. Note the squashing of outside hexagons, you (I) should do something about that... don't forget.

Another month bites the dust

Another monthly meeting over, with the focus once again showing off what I have (or haven't) done, mostly showing the animated version of standard force directed placement, and Chris Walshaw's multilevel version. This may not seem like such an amount to show, given that most of the work was done before and all that was necessary was to output a few coordinates each time the algorithm runs, but this is Java, and Java doesn't play nice with developers.

Moving on... it looks like future work (at least for this month) will be focusing on benchmarks and comparing output, as opposed to mindless/mindful (delete accordingly) programming. This will be concentrating on static graphs as opposed to the current work, so that I can get a feel for how things like this can be checked and compared in this area. More concerning, this will be using graphs slightly larger than those I am used to, and due to the intended size, will mean I have no output telling me what's going on (something I am not used to, which is not a nice feeling, but is necessary).

Its going to be an interesting month.

Other areas of interest will be small, such as fixing a few problems with the viewer (where the average x and y is), figuring out once and for all why my graphs insist on moving away from the centre of the view, and reverting a few areas of the multilevel implementation back a few versions (so a vertex shared between two graphs becomes two different vertices).

Anything else is written in the minutes here, and an image showing the three graphs of a coarsened 9square.graph [9 squares in a 3x3 grid]. The coarsest graph given coordinates first, then the second, and then the third. Might be best to ignore the black lines / edges for now, as they have no real purpose here (generated by an incorrect piece of code).

More slow progess

As the title suggests, little has changed since the last update (par a few things below otherwise I wouldn't be writing this).

Most significantly, I have found the cause of a problem I've been having (this has to be the most ambiguous line ever). The problem was graph layouts, not quite matching the shape they should have, which without edges is quite difficult to gauge in large graphs. The edge drawing mechanism was to help with this, but due to time and other priorities, completion of this has been postponed. A temporary line drawing mechanism (similar to that used when i first started) has been implemented, allowing me to see what's actually going on... and good god its a mess.

It appears the layout gets very confused, and starts "flicking" out in the wrong direction causing crossed edges (which clearly shouldn't be happening). This has only occurred since my attempt at moduli sing the work, and has since been blamed on a few changes to my implementation of eades algorithm (which worked before). The edges now being drawn show that the problem may also be down to incorrect edges being drawn, and possibly a result of a change in my data structure. Nothing has been been shown to be the cause yet, but when it is found, I will mention it in another blog post.

There is not much else to report, other than tens of pages of notes and a busy looking NetBeans, most of the time has been spent analysing and attempting to resolve the issue with the graphs. I will update soon. I promise. Please don't leave me. 

Below is a picture showing some more output, specifically, the difference of new algorithm layout vs old algorithm output and what this problem is.

The left image is of the old implementation, updated to include edges and animation, whereas the new implementation on the right, which only differs in that the data structure is different. Both are of a cube, can you tell which has the better layout?

Progress: SLOW

As the title may suggest, progress this week has been slow. Nothing has been "finished" per se, and any progress has been that of small items that only make up a fraction of a larger task.

Much work has been mostly theoretical, concentrating on the edge drawing mechanism early in the week, and restructuring of the code / animation later. Small breakthroughs in the edge-drawing have been made, with edges being successfully drawn manually (calculations by hand/calculator as opposed to code) and a common algorithm outlined for other edges, however, this is far from a final implementation.

Animation and structure wise, I am attempting a "makeover" of the code to suit a more flow-like system (as the current implementation is too rigid to adapt with any ease, and will take a similar or longer period of time to change anyway). Again, the work has been mostly theoretical in preparation for the changes. This will be a time consuming task but will be worth it in the long run.

Some odd behaviour to report in some of the changes made previously, the output of the latest (latest in the last I've adapted) drawing algorithms changing the visual layout of the graphs. NB TO SELF: More information regarding this is intended to be uploaded, but failing that, some descriptions have been made in the code [see code repository]. Reverting back to previous versions reverses this.

A more detailed, hopefully entertaining and upbeat and possibly funny, update is expected at a later date when some "real" work has been implemented, but for now, progress is still progress, no matter how slow.

I'll leave you with this picture of one of my manually drawn edges,

Two vertices, with an edge placed using some trigonometry.

And if you're having a bad week, here is a picture of how I feel a completely unrelated lolcat,

*Sigh* paperwork...

Beginning of the year and back to paperwork, so much paperwork. Whether its the student loans company or marking, it appears to never end. Regardless, much of the past two days have been spent getting my affairs in order and so once again, I must use my time wisely and catch up to the imaginary point deep within my head.

A quick summary of what is meant to be done and what has been done:

Edge Mechanism - in progress, much having been done such as the rotation angles and drawing points, its putting it together than appears trickiest at the moment (amongst other problems such as - how are edges stored in the xy file?).

Code modulation/reconciliation/puzzle - also in progress, unfortunately I get distracted by tweaking some of the components to see what happens. A few errors popping up, soon to be resolved (hopefully) but still moving forward.

Literature Review - reading is still a prime time-taker, with notes being equally as laborious. Again, going forward.

Animation - some progress in this area, mostly rotation and better viewing capabilities.

Much of the time is spent on time-consuming little things at the moment, and so progress seems slow, however, I expect when the students return next week, everything will continue as it did before. I will update tomorrow[Friday] or Monday with an update on progress.

Back to life, Back to reality (Let the race begin!)

Holiday break is over and everyone is resentfully back to work (except me of course).

This week will focusing on gathering my work back together into a form that can be continued, with attention given to re-structuring / organising the code, and implementation of a edge drawing mechanism. Dependant on the progression of these, other aspects highlighted in the last monthly meeting will be visited (I'm looking at you, Mr Literature Review).

Now, back to work! Updates on my progress will follow every other day as per usual (hopefully with more pictures and better descriptions).

ciao