Multi-what? Is that some type of game?

So ends another week of what can generously be called hard work, with the focus very much on implementing Chris Walshaw's Multi-level algorithm. Several implementations have been created, none of which worked ... well, heh (most died from exposure to increased amounts of Exceptions), however, it has become painfully clear that my current method of storing the data is inadequate and slow.

Fortunately, I have succeeded in creating an Array-orientated structure for holding information, whereby all vertices and edges are stored in arrays. It has been designed so that edges can be used as vertices (during coarsening), so the new vertex will hold the information of both child vertices in the form of an edge (so, in theory, the model can be used iteratively). The design took into account my supervisors advise/guidance that vertices should only know its children, and not its parents or neighbours, if any. See below for a more graphic description.

This is a very new change and I am still working through some issues, most noticeably, how to translate edges from G(n) to G(n+1). The intention of this change is to make the coarsening used in the multilevel algorithm easier for me (as using my current technique makes it very difficult).

Research wise, I have concentrated on the papers referenced in Chris Walshaw's paper, specifically those focused on matching and the problems associated with it (turns out I don't have the paper with me at the moment, nor can I remember who wrote it - so I will update this when I am home so I don't get it wrong).

For now, I will leave you with this attempt of an update, hopefully my next post will be a little more fruitful. As mentioned, a quick intro to how I'm using arrays, is below, once again, please remember it is not finished. Good Day!

-----------------------------------------------------------------

The plan is to have a 2d array of objects for vertices, and another for edges:

Object[|V|][4] vertices, where |V| is the number of vertices, and the 4 variables are (Object o, double x, double y, double z) where o can be anything (that is an Object or type of Object).

Object[|E|][2] edges, where |E| is the total number of edges (not included doubled edges), and the 2 variables are (Object v1, Object v2) where v1 and v2 are vertices from vertices[][].

An object v from vertices[][], can look like this for G(n) where n > 0,
v[0][0] = e[0];
v[0][1] = x coordinate;
v[0][2] = y coordinate;
v[0][3] = z coordinate;

Here the new vertex v is a matching of u1 and u2 that formed e[0]. If no matching is found, it can also be another vertex from the previous graph, i.e. u[0] from u[][].

For G(0) the vertex v will not include an edge or vertex, and instead, can be left to null or can hold some other value (such as an identifier if necessary).

Hopefully this gives you a little insight into the world of carl, good day!

[no pretty pictures this week folks!]

Organised Carl... now that doesnt sound right

The Roles and Responsibilities day yesterday [Thur 21.10.2010] highlighted the importance of organisation so that I do not run out of time (especially important for yours truly, as I am funded for 3 years and the average completion of an MPhil/PhD is 4). It also highlighted some other self-development exercises the Postgraduate Research Office require me to complete (including the 100page book they call a "Log-Book"), so I have been busy reading and writing through my motivations, my future career, my lack of skills and everything else sticky and self-improvement related.

Back to the real world, I have begun organising my read articles, including a small review for a select few in preparation for a literature review (organisation maintained by BibTex via JabRef).

Continuation of my implementations of existing models has been slow, mostly in response to the increased organisation and administrative tasks this week, however, having re-read "A Multilevel Algorithm for Force Directed Graph-Drawing" by Chris Walshaw, I expect the work rate to increase again by next week with an implementation of at least the coarsening and un-coarsening of graphs next week.

Have a good weekend!

Proof, I demand proof!

Proof!

Its easy saying something without proof, so it's reasonable to be sceptical if and when I say I have something working and show no screen shots to prove it, strangely like my previous post... On that point here are a few pretty pictures (with Descriptions!).

My first test (for every algorithm) is to draw a simple 2D square - completely inaccurate for testing as there are not enough vertices to gauge accuracy or see any adverse effects the attractive and repulsive forces may have.


As can be seen, the coordinates appear to be well placed with no horribly displacements anyway. One thing you may, and probably should, have picked up on is the lack of edges being drawn. This is due to myself not having included a method for drawing such edges, a simple algorithm with complexity |E| can be added to the current drawer however I am looking into other methods of drawing and viewing graphs. Therefore, it is assumed the edges are placed correctly, so we only look at the placement of vertices (for now).


Above is the 9square example used by many graph drawing theorists, it is essentially 9 2d squares in a 3x3 array and is relatively useful for seeing how the different forces act on the vertices. As can be seen a single vertex is thrown out, surprising and concerning at the time, but logic proved that it was an incorrect chaco file. I bring this up as it greatly affects the projection of the entire layout by (almost exactly) 45 degrees on the Z-axis, which I found interesting (a single particle affecting the entire graph layout. The correct layout is below.


The layout here is very different to that shown by Peter Eades in his journal entry, and has been attributed to a mixture of different coding practices, and some inconsistencies in the algorithm (such as starting positions).

My next test was a disconnected graph designed by myself. Consisting of 11 vertices and 13 edges, it is a hexagon with a triangle (with one loose vertex attached) within. This was designed to see how the algorithm would work with a disconnected graph, you know, out of curiosity...





On the left, is a simple sketch of how I wanted the graph to look, on the Left is the output. The output was quite predictable, I had made a calculated guess that the inner triangle would be thrown out in a random direction due to the repulsive forces. I did not expect the different parts to retain a an accurate layout, however, this makes sense within the code.


A few more tricks were tried to test the algorithm. Above is a standard octagon (or what was meant to be), with an acceptable although still flawed layout. Imagining a very sparse graph, with only edges around the perimeter. The next layout is when each vertex has an edge to every other vertex, a very dense graph - note this is still intended to have an octagonal layout.



The layout for this is still yet to be explained and understood, it could be that the different forces are acting against each other in such a way that no position can be finalised. Increasing the number of times the algorithm is run (100 to 200) has no noticeable effect on the layout.

Speed and Efficiency

The speed of my implementation is utterly shameful. The good news is, I can see and understand where and why. Eades original implementation was said to be of |V|^2 complexity, and be fast (I/O bound) for graphs under 30vertices.

My implementation is at worst |V|^3, and at best |V|^2 - very very bad. This is due to my method of storing vertices as objects (with adjacent vertices in an array list within), making it necessary to read through all adjacent vertices for each vertex (Which could be as big as all the vertices in the graph, such as in the dense octagon example).

The Future

It has been planned, that future work will continue to use my extremely inefficient method of storing vertices, until I have reached a further point with the algorithm side of things (after I have implemented a version of Walshaw's multilevel method.

A way of moving GLUT cylinders to act as edges is also planned, instead of using drawLine for a more pleasing aesthetic appeal.

My secondary supervisor, Dr Alan Soper, has also suggested I create an animated version of P.Eades (and other) algorithms so that it is easier for the user to see the changes made to the graph. This will be exceptionally helpful in debugging but will also be better for viewers.

Also a "fourth" dimension was advised, to hold some force if it increases above some level - in a similar way that 2d graphs are sometimes "folded" into 3 dimensions when the forces become too much to handle.

Bye

That's about it for now, It may be that I read over this tomorrow and have to edit half of it, but it the mean time - enjoy. If you have any questions or wish to context something I have written, or just want a copy of my code, please feel free to email me at cc96@gre.ac.uk.

It lives!

P Eades Heuristic for graph drawing is go! Now fully working, my implementation takes in coordinates as a chaco file, and outputs the cartesian coordinates to a drawing algorithm, which lays out and displays the graph as expected.

Thanks to my supervisors for helping me understand where I had gone wrong, it turns out I misread the paper. Where it asks to calculate a force, I calculated the force of all vertices on one vertex at one point, then applied the force as one big vector. My new implementation now uses the force between two vertices to move said vertex in one go (simple when you think about it now, something I probably should have realised, but were not all perfect).

There are a few issues that need to be fixed, for example, due to the initial position given to my vertices, some graphs are drawn at an angle (but still retain the aesthetically pleasing layout). Also, it has been made known to me, that my method for avoiding doubled edges will not work if I change the way I store vertices and edges, so this will need to be changed.

I will update after some more tinkering and have some screenshots to show you, in the mean time, cya!

Hell hath no fury like a graph drawing algorithm scorned

Continuing from my previous post, I am due to receive guidance regarding my implementation of Peter Eades "A heuristic for graph drawing" this coming Thursday (14/10/10), thus, pushing my implementation of Walshaws Multilevel approach until much later.

This, therefore, is a fairly deep progress report on my work with Eades Heuristic.

Attempt 1: I implemented the algorithm exactly as written (as I read it, others may read it differently). Where he has written, in his pseudo code, move vertex by (C4 * force), this was interpreted as adding the force to the x and y coordinates. Implementation quickly made me realise if the same number is added to both x and y, the final graph will be very linear and not at all representing the shape/layout it should (at some obscure coordinates).

Attempt 2: As the report by Peter Eades only mentions "force" and not "forces", I continued working with the single force, and tried to multiply the force by the x and y coordinates, which gave a different non-linear shape, however, the coordinates changed to such small positions (such as 0.04 and 0.01) without any shape, this was abandoned.

Attempt 3: Change the force to contain x and y vectors, so the force would only be calculated in one direction (with the distance, now only being the distance for a single direction). This came with a variety of issues, with coordinates returned with [infinity] or [NaN]. This was due to the use of negative numbers in Math.log() and in some cases, dividing by zero.

NB: with directional vectors, negative directions are allowed, meaning points could move anywhere instead of one direction.

Attempt 4: Keeping with the directional forces, I tried to create an implementation that would check for negative directions, and if found, switch the sign before and after the use of Math.log() (to avoid NaN), and some added functionality to avoid division by zero.

Conclusions: the force should/must have a direction to allow for larger changes for a single direction (x, than y, or y, than x). Math.log(-n) and division by zero are real issues that should be avoided.

All attempts failed to give a pleasing or accurate layout, with some failing to give any coordinates at all. It should be noted the Attempts above are not my only attempts, but are the largest distinctions between my changes.

Below is the pseudo code for my Attempt 3;

foreach vertex i {

foreach vertex j {

if i != j {

foreach adjacent vertices k {

if j == k

/* vertices adjacent */
i.x - j.x = dx
i.y - j.y = dy

forcex += C1 * log(dx/C2)
forcey += C1 * log(dx/C2)

else j != k
/* vertices no adjacent */
i.x - j.x = dx
i.y - j.y - dy

forcex += C3 / sqr(dx)
forcey += C3 / sqr(dy)
}}}}}

for each vertex i {

i.x += forcex
i.y += forcey
forcex, forcey = 0.0

}

Un-improving Hello World

These past few days have been quite a test of patience for myself, the algorithm given to us by the legendary Peter Eades in his "heuristic for graph drawing", as mentioned in a previous post works however does not give the correct coordinates. A lot of time has been spent on this, and currently, no solution to get my implementation to work. I am currently awaiting guidance which will hopefully kick start my progress.

In other news, I have been forced (by myself) to create yet another drawing application to draw the output from my implementations, using Cartesian coordinates. During development I remember the points made by Veldhuizen in his Dynamic Graph research, that the graph should be displayed as seamlessly as possible. As a short term method of encouraging this, I have decided to keep the bounds of the graph proportional to the number of vertices, and am intending to introduce a system where in these bounds and the view can be changed to suit the users needs (in real time).

My current aim is to have a working implementation of Walshaws Multi-level method before Thursday 14th October (which just so happens to be when I am scheduled for a meeting with my supervisors).

Have a good weekend.

Hello World! of Graphs

Good news! I have successfully collected the rare and mysterious article "A heuristic for graph drawing" by Peter Eades from the 1984 Congressus Numerantium Vol. 42 and have successfully created a working model of the algorithm described within.

Of course, "working" is very different to "accurately drawing a graph", given an input in the form of a chaco file, I am returned with coordinates for my drawing algorithm (currently drawn via sketches as said algorithm is not accessible in my current position - though it does exist as shown in previous blog entries). [pictures will be uploaded when the drawing algorithm is accessible or when I create a new drawing algorithm].

Next stop - completion of a fully working (I mean "drawing graph accurately" working) implementation of P.Eades Heuristic Algorithm, expanding upon this to include the multileveling and coarsening used in Walshaw's work and a deeper look into the storage of data (specifically Arrays and how to increase efficiency and speed).

Getting a move on

It has got to the point where I am now almost entirely sure that copying the model of someone else's paper, for example, creating the algorithm behind Walshaw's "A multilevel Algorithm for Force Directed Graph Drawing" is near impossible (Note the use of almost and near in that sentence) without the code behind it.

Having tried to follow it as closely as possible, I make too many assumptions and as far as can be told, am creating a completely different model. The good news, I guess, is that I have a very good understanding of what is expected and have found the worst possible way to do it (heh).

I am however, getting a move on and speeding up my work to meet my own personal-set deadlines and am due to have an algorithm capable of reading a joint graph in the form of a chaco file, and output the coordinates (though it may not look like the original or proposed graph) after the weekend, notes and screen shots will be posted.