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

Damn you and your games universe!

It figures that the second I mention my implementation as working, and have a meeting with my supervisor organised, that something goes horribly, horribly, wrong. Coarsening now only works at one level. This is due to the way in which I compare edges against other edges as memory as opposed to an ID number.

For example, a section of memory looks like: name.Class@XXXXX, where an edge will point to the memory of its vertices as opposed to holding information about its ID (my attempt at avoiding memory usage). So two edges sharing a vertex would look like:

v(0) | v(1)      name.Class@00001 | name.Class@00002 
v(1) | v(2)      name.Class@00002 | name.Class@00003

Somewhere within my algorithm (during matching and creation of edges), the vertices use different segments of memory closer to:

v(0) | v(1)      name.Class@0000A | name.Class@0000B 
v(1) | v(2)      name.Class@0000C | name.Class@0000D

To fix this, I just need to change how the matches are created (so point to existing memory blocks for vertices). What is more worrying is that this working previously, and therefore something has changed (without me realising), fortunately I have a fairly secure versioning process so I can always roll back to a previous point and modify that.

On a different but unrelated note, here is the perfect explanation for this, courtesy of Piled Higher & Deeper:

 http://www.phdcomics.com/comics/archive.php?comicid=821

Sweet Jesus it works (kinda...)

My implementation of Chris Walshaw's Multilevel Algorithm for Graph Drawing works! Actually it worked last Friday (19/11/10) but I wanted to test and write a mini-report to ensure it wasn't some fluke.

I have successfully received useful output that can be drawn, with output looking similar (but not the same as) that of my Peter Eades Heuristic for Graph Drawing Algorithm. There are a few problems with my implementation such as no soft-coded cooling function and the level of coarsening depends on how many times the user calls the method, but all can be fixed given time.

In completion of this, I have written a small report detailing the algorithm and my implementation, so 1. I have something more detailed that "it works" when I come back to it, and 2. in case anyone needed it. Output has still yet to be recorded, albeit I have been doing this for today (so still yet to be finished), but eventually this will comprise of various images of different graphs, and the layout of each level.

Next on the list, I am intending to meet my primary supervisor this Thursday to demo what I have done (and prove its not all an elaborate and well planned lie). After, assuming all goes well and minimal corrections/changes, I will be focusing on a dynamic version of the algorithm similar to Todd Veldhuizen's work on Ubigraph (very inspirational work, also a good indicator of what Im trying to achieve).

Below are some useful links, I hope to update soon with my testing documentation and example outputs. Adiós!

Here is a link to the document mentioned above, a brief description of my implementation. It should be noted this is likely to change over the next few days as I update it to suit my own specification.

Also, I failed to upload this previously, a presentation regarding my Eades implementation and output. Some of this may also be outdated as I have progressed my implementations.

\\OLD\\ "Are we there yet?" - "Almost..."

NOTE: this post was written on the 25/10/2010 and was failed to be published. Instead of loosing this update, I am going to publish now.

Since my last post, I have corrected the NaN error given to me by those nasty irritable doubles (Sod's law at its finest, after complaining about the problem to the world, it gets fixed).

The error, as mentioned previously, was caused by division of zero due to two vertices being on the exact same spot (distance apart = 0.0). Having looked over the code and spending more time than I would like with my face in the debugger (according to the radio Ive been here for 7hrs 35mins...), it appears for reasons unknown, the list of vertices has added an additional vertex (the last has been added twice).

This was easily fixed by adding a loop to check if the vertex has already been added (inefficient for now as this shouldnt be necessary but I can worry about this later). This led to the very first output from my multilevel graph drawing algorithm, albeit a drawing of a coarsened graph.

Unfortunately nothing ever works the way we want it to and the drawing was of a very straight line along x=y. Now to me, this means that the forces added to the location are either all the same, or counteract each other. Outputting each step as it happened showed that everything was happening twice, and the algorithm (unchanged from my original implementation) was ignoring whether vertices were adjacent or not. See below for an example of output.

Apparently, putting the Eade's algorithm into its own method, fixed this problem. I will have to compare the code in order to fully understand what is happening as this should not be the cause, but I will see.

Thanks to this little change, the graph drawn for cube.graph (a 3d cube), resembles that of 2dsquare.graph (remember, a 3d cube coarsened is a 2d square if coarsened perfectly).

Next on the agenda, iterating these coordinates down into the uncoarsened graph. Uncoarsening works on itself, so now placing the lower level vertices is all that is left. I forecast this for tomorrow (Friday evening) if all goes smoothly - which as always, will not happen.

Have a good weekend if I dont update you sooner.

Error: Output is not useful

The output is indeed, useless. In fact its the worst kind of useless, its double i = NaN useless.

Having completed my coarsening and an initial version of uncoarsening, I have spent the past few days placing the infamous Eades heuristic for graph drawing (my first implementation of a force directed graph drawing algorithm) on top. In theory, this is quick. In implementation, this is also quick, with it currently sat comfortably on top, a surprise for everyone involved (so just me...).

An unexpected consequence was a problem (a problem? i'm so surprised /sarcasm) with the algorithm itself. When a set of vertices are input, for example, a coarsened version of cube (coarsened by one level - so essentially 2dsquare.graph), the algorithm works up to an undefined point until all further values change to NaN (Not a Number).

After a little research as to what had happened, it turns out, in this instance, the cause is division by zero (meaning two of the vertices are in exactly the same position - something which shouldn't happen, odd...). Unlike integers, which throw useful exceptions when this occurs, doubles turn to Infinity, and/or NaN.

Moving on from my frustration and anger towards Java, the implementation appears to be going well and I am on schedule for my monthly deadline. My smaller deadline of getting an output that can be drawn before the end of the week, is still up to fate and the intake of cups of tea. I will update next when I have the chance/remember. Ciao.

Sod's Law: "anything that can go wrong, will"

In this cruel world of games, I have fixed whatever problems I had previous to the meeting - which is slightly annoying but at the same time relieving that I did not have to make any big changes to my current work.

Coarsening works (note how I want it to work may differ greatly to how others want it to work, regardless it is a "form" of coarsening a graph). Uncoarsening is under way, and I feel like I'm beginning to catch up, with an implementation of Eades heuristic for graph drawing being implemented with Walshaws multilevel algorithm, during the next week (or two).

The monthly meeting was focused on my current position, what I am aiming for and what I expect to get done before next meeting. The answers to these can be described as one:

"I want to get an implementation of a dynamic multilevel graph drawing algorithm, ideally that which is demonstrated by Veldhuizen, before Christmas".

This is a large undertaking, considering my current position, however, I am confident that if I can complete Walshaws multilevel graph drawing algorithm before the end of next week, I will be able to meet this deadline (fingers crossed).

In other news, my office is now underway, and although it is not as private and secure as I would like (soon to be fixed I've been kindly told), I have an ideal working area. I am also due to be paid for my tutoring next week and am looking forward to that.

In completely unrelated news, my first inlay has been finished (I'm excited about it and needed to share that with the world), with only one more to go! NB: don't let a tooth decay for 3years before seeing a dentist, it messes up the nerves a little...

Thats all for this week, next update - Monday 19th (11/10) - have a good weekend!

Coarsening sucks. That is all.

Firstly, apologies for the late blog post, this week has been extremely busy.

Work/Research has been focused on implementing an iterative method of coarsening, which this far, has not been accomplished. The silver lining to this, is that a method hasn't currently been implemented due to my programming, not through lack of understanding.

I have the methodology for such implementation written out on several pieces of paper (NB several in this instance, means about 30...), which works almost perfectly, as is always the case with theories, but I am limited by my use of Arrays.

In reaction to these problems, I have returned to using my own "Component" class, which stores information of vertices or edges (dependant on how it is initialised). This isn't important for now, but hopefully a better explanation will come in the future.

Monthly Meeting tomorrow with both supervisors, I will be utterly disappointed if I do not get some form of output from my implementation, to show them. This is a good sign for me to increase my power (work rate) as I am falling behind my own deadlines.

Anyway, must go, work calls. Next update planned for Friday (or tomorrow dependant on how the meeting goes).

Again with the matching, I think I need to move on

Having read more about matching, more specifically, the problems of finding a maximal independant set, I have discovered my algorithm is unusually quick for a number of reasons. Several methods have been implemented to find the maxmimal set most efficiently, and quickly, including a path orientated approach [1] - by creating an alternating or augmented path through the graph, or a debt-first search [2] - where each adjacent vertex of a singular vertex, is visited to determine if at all, its best fit.

[1] Combinatorial Optimization, Algorithms and Complexity - Papadimitriou & Steiglitz
[2] A multilevel Algorithm for Partitioning Graphs - Hendrickson & Leland

These are both mentioned in Walshaws Multilevel Force Directed Drawing, which uses the same method for finding a maximal independant set as [2], due to [1] being too slow, and not essential.

My method of finding a maximal independant set differs greatly, in that it completely ignores weighting or finding the best edge matching, and goes for the closest and first available match. Having check this in comparison to the methods above, in theory, this does not greatly affect the matching of edges, and any differences, are minimal. This is open to speculation, and more research should be carried out to find an optimal solution which is both quick and efficient.

One large noticeable issue, is the lack of weighting in the matching. Vertices are paired on a first come first serve basis, whereas a more intelligent algorithm would match the vertices with less or similar weights. The way in which data is stored may also need to change, so to include these weights if and where necessary.

The next step, as mentioned previously, is coarsening, giving the new vertices edges in place of lower level edges, and iterating the matching algorithm. Other work may include experimentation with this maximal matching problem.

Meeting

Today I met with my supervisor to discuss my work with matching and my change to storing the graph data. Although the matching may be efficient, a bug is expected to appear when applying force-directed drawing techniques. Whether or not I have to change my current model is yet to be determined, but it is very likely. In anticipation of this, me and my supervisor discussed making my code polymorphic, so that if I do change my method of storing information, the code will work in the same manner.

Our monthly meeting is to be scheduled for next week, where I will hopefully have something to report upon (more than my matching algorithm).

Testing: The Matching Chronicles

Introduction to Testing: Matching
Testing for the matching part of the coarsening in Walshaws Multilevel algorithm was important to ensure everything works as it should (or as close as can be). Testing was carried out by simply inputting the chaco files of some familiar graphs, and reading the output. To check the output, I would work through the algorithm by hand on each graph to ensure (and see) which matches are made and where.

Measuring Success
At this stage, a success would be if the program output a number of matches that is feasible. That is to say, the matches meet the criteria that:
- no vertex is shared with another matching
- edges can only be matched once
- the number of matchings is maximal

Test Subjects
2dSquare - a simple 4 vertex graph with 4 edges, each edge being the same size, with the outcome being a square. The expected output would be 2 matchings*.

9square - simlar to 2dsquare, except a grid of 9 squares, with 16 vertices and 24 edges. The expected output is 8 matchings*.

own - my own graph, shown in previous posts, a disjoint graph: 1) 6vertices 6 edges, 2) 4 vertices 4 edges. This has been used to test previous implementations and has worked well at providing an "irregular" graph. Expected 5 matchings*.

1ma** - a graph taken from [1], 6 vertices 6 edges

2ma** - as above, taken from [1], 6 vertices 7 edges

3ma** - again, as above, taken from [1], 5 vertices 6 edges

*previous to the tests, I went through each graph as the algorithm would, and noted down which matchings should be made

**taken from [1], these graphs proved useful regarding my research into matching and I expect them to be as useful as test subjects - please note not all research for matching was through wikipedia

Results
2dsquare.graph - 2 matchings
9square.graph - 8 matchings
own.graph - 5 matchings
ma1.graph - 1 matching
ma2.graph - 3 matchings
ma3.graph - 2 matchings

Conclusions
The results show that the matchings made are feasible and realistic, however, they are not always maximal, for example, ma1.graph recieved 1 matching, where it could have 2 matchings. This is due to the way the program looks through edges (linearly), which can and should be changed.

For the purpose of continuing with more important aspects of the multilevel paradigm, this implementation will continue without changes.

Complexity wise, this needs to be checked over by my supervisor, but should be O(|V| . |E|).

References
[1] https://secure.wikimedia.org/wikipedia/en/wiki/File:Maximal-matching.svg , accessed 05.11.10, Author: Miym

Matching: Works! Brain: NullPointerException!

Success! The matching appears to work!

I have successfully fixed several errors in my code, most of which were with my loops (NB: Fear the ConcurrentModificationException, it makes life difficult). The algorithm works as mentioned in my previous post and checks both vertices of an edge, against the vertices in an "already matched" list, making it semi-efficient. Research and consultation will tell if its as efficient as it could be, but a working algorithm is good news regardless!

I have tested the algorithm with my several small graphs, however I intend to stress test it over the weekend with some others to find if any subtle bugs exist. The next step will be to combine the matchings into single vertices (creating the coarser graph) using the vertices array structure used previously, and then to try and iterate this process (first 2 times, then implement a method of determining the coarsest graph).

I will post test results next week (if not over the weekend), have a good fireworks night!

Never give up hope... unless you get an exception

Small update this week: did you know that the date on the 01.11.10 is the same written backwards? I'm only 2 days late...

Back to the real world for a second, this week has been focused on creating a working matching algorithm. The new method of storing information appears to work, though retrieving useful information is difficult as nothing is given names - but as far as can be seen (and drawn out via debugging, and writing down the objects position in memory), it works.

The matching implementation currently looks through the list of edges (that's right, I have edges!), any edges which contain vertices not in a temporary "store" list get paired. When matched, the vertices of said edge get stored in this temporary store so they algorithm knows not to use them again.

There are other methods, such as using flags to determine whether vertices or edges have been matched, or by removing matched edges from the list (in an Array, this is quite difficult). Other methods do exist, however, I am not concerned about efficiency yet, so have no looked into these.

As mentioned before, I am still having some issues with my algorithm but hope to have matching (and so coarsening) finished before the end of the week.

One again, cya!

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.

Keep it short

In a bid to keep future posts as short as possible, I am trying to update this more often. As far as can be told, the algorithm for determining disjoint graphs works with what I now to believe O(|V| + |E|) at worst. Too much time has been spent on this so moving on.

I very much enjoy Fruchterman and Reingold's method of modelling particle physics, and thought about how I could utilise some physics myself, such as Entropy as a cooling method and global force acting on every vertex, instead of the annealing method used by Walshaw and Veldhuizen. This obviously needs more research and may prove to be less efficient, then again, it may not, we cant know until we try (or see if anyone else has done it).

Need to do more research on Todd L. Veldhuizen's Dynamic Multilevel Graph Visualisation to see how his algorithm acts on large changes higher in the vertex list (so whilst others are added, what happens if a large number of original vertices dissapears).

Another Day, Another Planet

A shorter blog entry this time if it can be helped, having found a method of checking if graphs are connected or not and keeping the efficiency of said algorithm to a minimum O(|V|) at best, the next step included some testing to check if it works, and so, some assumptions have to be made in order for success.

1. The file input should be in the "Chaco" format (NB to self and advise to readers: find original source for this file type, might be useful)

2. The file input is read in the correct order, so the first vertex read in is vertex 1, 2nd is 2 and so on. Disruption of this order may cause some undesired or unexpected issues (as far as can be told, if the rule above holds, this should not be an issue as chaco files tend to be in the correct order)

3. The vertices are in order, so for part of a disjoint graph Ga = Va; Va { v1, v2, v3 } and Gb = Vb; Vb { v4, v5, v6}, the vertices are in some kind of order, whereas if Va { v1, v4, v2} and Vb {v3, v5, v6}, this may cause some unexpected issues.

More on these assumptions and rules after some more research and testing. The algorithm I'm using is actually a variant of the breadth-first search algorithm. I am also aware of Menger's theorem.

NB: Yesterday (Monday 27th was my first Tutorial, 2hours with group 6, and 2hours with group 10), not of interest to you readers but its always good to have somewhere to look up things in case something goes missing.

Getting Settled

This week has been a blast, I have done quite a lot of reading, experimenting with matrices and understanding the coarsening and uncoarsening algorithms, most noticeably my latest research topic has been to find how to see if a graph (set of vertices and edges) is disconnected or not.

This topic did not show itself before, however, its importance has been realised. If a graph is disconnected (so have a graph of two main disconnected partitions for example), the global forces on one can or can not affect the other, so most philosophers have designed their algorithm for either only fully-connected graphs or disconnected graphs.

The aim of my research here (well not research, but my mental action) was to find a method of looking through a graph's data and finding how many disconnected graphs exist, if any. This is relatively easy until you have to take into account the efficiency, which more than often results as O(E^2) where E is the number of edges. This was less efficient than my supervisors algorithm of O(E), and instead of reading up (y'know, like I probably should have done) I decided to try and get the algorithm to this efficiency alone.

After a long battle with it, and the introduction to the Chaco file for holding information regarding vertices and their adjacent neighbours, I have (hopefully) managed to get it to O(E). The theory being, when a chaco file is read, the vertices are given a graph number indicating which graph they belong to. If all the vertices are connected, then they are all for graph 1, however if they are not, they are given different graphs. Describing it here does not do the theory justice, however, I will add my sudo code here when I have transcribed it from my scibbles of notes (with my working Java source code).

Other events this week include helping the University's Computing and Mathematical Sciences Mentor team, with tasks such as helping the new students find their way around, giving them information and handing out sweets. Another event, also involving the CMS Mentors, was helping new CMS students use the computer labs, and advising them when needed, which included a brief introduction to NetBeans and programming Java (much like I expect I will be dealing with in my tutoring).

This is all a bit rushed so expect corrections and additions when I read over this!

Thanks for reading and remember, work is fun!

"Oh dear! Oh dear! I shall be too late!"

A bad start to a degree but we all miss some deadlines. The reason for my lateness is due to the business of the past few days, so work had been put on hold, however, it is now continued and all is right with the universe again.

Monday(Excuse 1) [13/09/2010]

Mondays schedule started early, with a 5.00am wake-up and a nice 2hour 30minutes journey to Greenwich. A general meeting between tutors and more admin work were carried out throughout the day. The good news is, I now have a work-related laptop (instead of using my own), I will be moving into University Maintained Accommodation this coming week and I am now officially a "staff" member (though I use this term loosely).

Though the activities of the day only took 3-4hours, the travel took up much of the day so I could only spend my limited amount of time research a paper by Yufan Hu (more details regarding this in the next blog entry).

http://math.nist.gov/MatrixMarket/ - a new link found by the paper which will answer many of my questions and may give me some useful testing data.

Tuesday(Excuse 2) [14/09/2010]

Once again an early get-up, for today, is the day, I learn to teach. A wonderful 7hour day (+4hours for travel), at least they supply tea and coffee. Some very cool techniques to help with teaching i.e. using different methods to reach different learners and the importance in good assessment.

The course was very useful to me and has made me a little more confident about what Im walking in to, having faced my fear (of having a class turn against me and maul me to death), whats the worst that can happen.

Though this is not directly related to my research, I am telling you this as an excuse as to why there has been limited progress. On that note, I have read more of the Yufan Hu paper and have found a few more relevant papers, with ideas on where I could specialise my research (however preliminary and unsure they are).

Wedneday(Today! a.k.a Excuse 3) [15/09/2010]

Today was spent mostly at home, however, once again (you guessed it), only a limited amount of work was carried out. This is mostly due to the preparation of moving to Greenwich and clearing my current accommodation of my stuff.

In Conclusion

So far, this week has been very bad for research, but very good for other semi-related tasks as I can now tutor classes, I have access to staff teaching material, my CMS account is activated and as far as I have proven, my emails are correctly sent to me.

The next two days are planned for reading and possibly some coding, so we will see how it goes. My next update will be aimed for Friday evening, if not, See you next Monday!

Second (to none) Log: I will not be dealing with coordinated graphs!

Welcome back to another episode of Carls Cooking Colosseum, todays specialities are pretty pictures of something that can be mistaken for work. Since my last blog entry, I have concentrated my efforts on physical and existential work as a ground for my future research.

A Start

A static 3D cube using cartesian coordinate's was created. An easy start but necessary to get used to programming with JOGL again. Each vertex's coordinates were calculated beforehand and hardcoded in, represented as spheres. Edges are implemented using cylinders and moved into place manually. This was then improved to have an algorithm to program anything providing their coordinates were input into an ArrayList (a form of vertex list).

This is a very simplistic model/algorithm and is probably as far from real graph drawing as you can get, however, it enabled me to think of how parts of a fully functional algorithm may work, such as the input of data which is not convered in the paper "A multilevel algorithm for force directed graph drawing".

Input of Vertices and Edges

In the model above, vertices are stored as an instance of a Vertex class (created by myself and not sun.security.provider.certpath.Vertex;) and edges as Edge (again made by myself). Verteices are created by inputing their coordinates, and edges, by inputing the two adjacent vertices (so completely based on a coordinate system as mentioned before).
Since this implementation, research suggests that the most likely form of input for vertices and edges is a form of matrix. Which type of matrix is used for graph-drawing is yet to be researched and discussed with my supervisor, but for now, an incidence matrix will be used (http://en.wikipedia.org/wiki/Incidence_matrix).

Dynamic

After creating a static model, I have begun to think about ways of making graphs dynamic (move and update in real time, such as nodes being added or taken away). At first thought, a java animator can be used with a thread to update every few milliseconds, or a polling system to update whenever a new node is added. The paper by Todd L. Veldhuizen "Dyanmic Multilevel Graph Visualisation" mentions use of a 'key frame' which is updated and displayed for every change, though this is not fully understood. Once again further research is needed (I'm starting to understand why this is called a Research Degree).

Additional Reading
Having now created a play toy to test my newly discovered powers upon, my next port of call is several more papers;

• "Graph Drawing by Force-directed placement" - Fruchterman and Reingold 1991
• "An Efficient Heuristic Procedure for Partitioning Graphs" - Kernighan and Lin 1970
• "Efficient and High Quality Force-Directed Graph Drawing" - Yifan Hu 2005
• "A childs guide to drawing" - Old McDonald 1876 (if i get stuck badly)
  

As promised, the pretty pictures:

The easiest of easiest; a 3 dimensional wire cube plotted out.

The same cube, plotted using an algorithm and a drawLine() method to draw lines between two plotted points (as opposed to just moving a cylinder there by trial and improvement). It looks worse but until I find a new way, this will have to do.



A random 3D graph to test coarsening on, until I got stuck with the way I was inputing data and realised that I won't be dealing with coordinated graphs. I may still test coarsening on it to see what affect multi-leveling can have on a coordinated graph system.

Once again, thats all folks! Look out for my next update!

Beginning of the End of the World (BEW BEW)

Hi, I'm currently studying Dynamic Graph Layout and Visualisation and have created this blog for you to follow and track my progress, beginning to end. The official start for my research course was 1st September 2010, so im already several days behind (blog-wise) so for now, I will add the additional days to this post.

Firstly, a little about me and my work, I am a research student at the University of Greenwich, Maritime Greenwich Campus, in London and have just finished a Bachelors in Computer Science with a 2.1 grade (not great as I was expecting a 1st but we cant all be winners). I'm a video game enthusiast, have an obsession for cats (like most of us internet-dwellers) and I like penny-sweets.

My work is to research into graph layout algorithms, starting with Chris Walshaw's "A Multilevel Algorithm for Force-Directed Graph-Drawing" and Todd L. Veldhuizen's "Dynamic Multilevel Graph Visualization".

Now for my previous entries;

[01/09/2010] - Day Zero
First day as a Research Student took me to Greenwich to meet with my supervisors Dr Chris Walshaw and Dr Alan Soper. I was also introduced to some of the members of staff I may or will be working with, and was able to complete my registration for the course. My new email address and user account was also created (though this needs to be checked), the Research Students and Supervisors handbook printed and the Research Student Log and Professional Development Portfolio also printed. I was also given permission to work from home due to my term-time accommodation not being ready.

Work-wise, I was directed to read through several existing research papers and begin modelling the algorithms for graph drawing (starting with the multilevel force directed approach).

[06/09/2010] - Week Zero
Third day of work, and the start of my first full week in research. Home workstation and software set-up and configured and all research papers required, printed for easy reading. Both Walshaw and Veldhuizen papers have been read (over and over) and physical work has begun.

Following my normal approach to work, I have decided to start at the bottom and work my way to the top, my first attempt being an application to draw a 3D cube frame where each vertex is represented by a sphere and edges, by a cylinder. There is no algorithm in use for now but the aim for this program is to refresh my JOGL programming skills. This should take less than a day.

[07/09/2010] - Project BlogBook.. I mean LogBlog... I mean...
This is literally to identify that this is the day I have started my blog/log book. Articles will/should be submited every few days (maximum 5 working days). Paper articles may also be written and will be attached to the next digital article.

Thats all folks, see you next blog post.