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!