Coming next month, more work!

We do it because we love it. Another monthly meetings completed, this time the focus was on discussing my results (looking at the larger graphs as previously I have only showed my supervisors cubes... which now seems very sad), and future work.

Minutes for the month can be found here.

To summarise, my future work is mostly experimentation, looking at why I have chosen the parameters I am using, implementing mechanisms to help speed up and make a more aesthetically pleasing layout, and eventually, creating a more interactive viewer - much like Visual Thesaurus - http://www.visualthesaurus.com/ - with sliders and tick boxes to allow for different drawing mechanisms to be included or not (much like the Simulated Annealing approach with parameters).

In a bid to escape coding for a little while (and to hopefully come back with fresh eyes), I will also be concentrating on the Literature Review in the immediate future. Now I know I've said this before, but recently the coding has been eating away at my mind and any more may cause some kind of deep neural damage, which I would very much like to avoid.

As a side note, the next meeting will most likely be focusing on my upcoming Seminar (04/05/2011) which should be funny for everyone not me (I am not a confident speaker and badly suffer from dry mouth in front an audience).

In the mean time, I would like to share the following image with the world. It is of data.graph, drawn by two different algorithms. What's peculiar is the original graph is of an air foil, instead, I have somehow drawn a shark and a swan... NB: these images are drawn in 2D space.

Update 4.9: Hell has frozen over

Previously on MPHILLOG, "Oh god why...."

This week has started off relatively well, I have solved the issue shown in my previous post (regarding the global untangling of the graphs, and why such mechanism didn't appear to work). Outputting one of the coarser graphs showed that there were no attractive forces between vertices, and so, vertices could get into a comfortable position in the center of the plane. This led me to realise, as a consequence of using my "wrong" Eades' implementation, vertices did not have a populated vertices list.

This was easily fixed, and had I got the FR FDP working correctly, this could have been avoided. I am currently waiting on the last of my tests to output the results, but from those already retrieved, there is a large difference (for the better) in runtime (now running @50 iterations per level) and in quality of aesthetics. Edge crossings also down, for most. Due to the likeliness to previous tests, I will keep but not publish a full set of tests until there is a bigger difference in implementations.

My plans for the immediate future involve fixing the FR implementation, limiting global forces, continue working on an implementation of Veldhuizen's dynamics, and organising a monthly meeting with my supervisors to determine what else I should be doing.

Next week on MPHILLOG, "Oh god not again..."

"negative results are still results... even twenty thousand of them"

I do love Big Bang Theory, anyway, topic of the day - comparable results.

<Edit> I have since found the cause of the neglected global layout, and a fix is being developed. New results will be published when attained </Edit>

After the success of getting the skeleton of a multi-level force directed placement algorithm implemented, a means of checking the range of edge length and counting edge crossings, it was time to see what would happen with graphs of significant size. My predictions involved fire and computers falling from the sky, fortunately I was wrong and received reasonable-ish results.

NB: the implementation noted above, does not include many features of other graph drawing algorithms, such as C.Walshaws variable edge length for each level, or Fruchterman and Reingolds 'grid variant' to determine the strength of global forces. All graphs are displayed in Euclidean space.

# FDP was applied 500 times per iteration thus the extensive running times in larger graphs, the extensive iteration count is so the local layout can be perfected, so I can see where issues are.
# Graphs taken from C.Walshaws partitioning repository: http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/
# Simply drawing the larger graphs is a time consuming activity, in some cases, 1/4 of the runtime

Results

Graph	|V|	|E|	Runtime (ms)	Levels	Crossings	Average Edge	Largest Edge	Smallest Edge
k33.graph	6	9	275	3	3	1.755	2.89	1.27
cube.graph	8	12	249	3	2	1.93	2.5	1.36
disjoint2.graph	11	13	295	4	0	1.5	1.85	1.26
4grid.graph	16	24	391	4	0	2.04	2.38	1.75
HenHar.graph	19	45	628	6	28	2.34	4.51	1.22
disjoint5.graph	22	23	-	-	-	-	-	-
hex24.graph	24	30	536	6	0	2.2	2.94	1.78
9cube.graph	32	64	827	5	18	2.62	4.05	1.19
25square.graph	36	60	1322	6	4	2.55	4.25	1.26
hex54.graph	54	72	1768	7	0	2.65	3.65	1.95
add20	2395	13722	2966044	370	407983	78.78	73754.48	0.34
data.graph	2851	15093	6725219	13	85514	7.21	213.24	0.01
55grid.graph	3025	5940	3353044	12	15524	16.98	13925.83	1.35
3elt.graph	4720	13722	2147483647	14	-	-	-	-
finan512.graph	74752	261120	3510750	370	415477	82.45	73826.44	0.1

(General) Conclusions

As this is preliminary testing, there is a certain obviousness that results will not yet compete against already existing drawing algorithms. However, these results are very slow (for larger graphs) and the number of edge intersections in each of the graphs are above what you would expect, similarly, the range of edge lengths is too large, especially in the large graphs. These observations mean nothing alone, but when coupled with the visual feedback during the placement of the finest graph, the behaviour of the algorithm can be viewed and more useful conclusions can be made.

As can be seen, the local layout is perfected by the large amount of FDP applied, but the global layout is having an issue. Causes for this is most definitely within the multilevel part of the implementation and investigation will be undertaken as to why this is happening.

(Pretty Pictures) Graph; graphics

9cube.graph - 9 cubes in a 3x3grid

As can be seen, the layout is aesthetically pleasing and matches the expected/typical layout of this graph. The bowing of the edges is a result of global forces pulling the centre vertices outwards (can be fixed by using FR grid variant).

The graph below is of grid55, a 55x55 vertex grid. Although the overall layout is not aesthetically pleasing, investigating the structure at a local level reveals the expected grid layout. This suggests that the global untangling is not sufficient.

The graph below is of add20, and once again, the layout is not pleasing. This graph has the largest number of coarse levels due to its star-like mini-structures, as mentioned in previous posts. This can be verified by looking at the smaller structures within the graph. Global untangling proving an issue here to.

This graph is of data, and shows the global untangling problem again. Although not resembling its ideal layout, the information of the graph is still relevant, for example, there are 3 parts of the graph which are very loosely connected to the overall structure, which was also commented upon in C.Walshaw's "Multilevel Force-Directed Placement".

This is 3elt, which took too long to finish finding a layout. It also displays the global untangling problem but still shows its mesh like local structure.

Now for an interesting look at what's actually happening; 

From left to right, this is how the final graph is given its layout. In the first iteration of the FDP, it appears each of the centre vertices (of which there are very few, so possibly several vertices in the same position), splits into its respective vertices and spreads around it in a circular fashion. In the second iteration, the vertices spread again, outwards until the circle of vertices is larger. In a later iteration, these concentric circles can be seen clearly, and the graph begins to take its shape.

This suggests the multilevel part of the algorithm does very little, and so should be investigated.

Graph; Descriptions

• cube.graph - a simple cube of 8 vertices each with a degree of 3
• disjoint2.graph - a small graph comprised of two individual disconnected graphs
• disjoint5.graph - similar to above, but with 5 graphs. This show an issue with the current mechanism for testing if a graph is coarse enough (|v| =< 2), as 5 components coarsens into disconnected vertices, the algorithm will keep attempting to coarsen the graph until out of memory.
• 4grid.graph - a grid of 4x4 vertices
• 25square.graph - a graph of 6x6 vertices (5x5 squares thus the inaccurate name)
• 55grid.graph - a 55x55 vertex grid
• hex24.graph and hex54.graph - a honeycomb structure of hexagons, with 24 and 54 vertices respectively
• add20.graph - a graph used as an example for most general graph drawing algorithms, modelling an adder
• data.graph - used by C.Walshaw and part of his partitioning archive
• 3elt.graph - as above, also popular as an example among graph drawing algorithms
• finan512.graph - much larger than other tests, but has a very unique structure, and so wanted to test how the algorithm would react to such a graph

Next?
Figure out why the global forces are drawing graphs as a circle/mess of vertices. Also, implement other parts of the multilevel graph drawing algorithm, such as a mechanism to determine short and long range forces. There are many more improvements I could list, but for now, I will update you all as I go.

Now where was I?

Rejoice! I have managed to get (almost) back to where I was before the Monday incident. I say almost, I have not yet fully implemented Fruchterman and Reingolds force equations, as opposed to the Eades equations I've been using, however, everything else appears to be working smoothly.

Currently, I am trying to create a "nice" way for the multilevel algorithm to know when to stop coarsening a graph. I'm aware in most cases you could say "when |V| is equal to some designated size", however, what I have observed during some testing (specifically when coarsening add20.graph from Dr. Chris Walshaw's Graph Partitioning Archive here), is that coarsening a graph may result in a "star" type graph where all vertices are connected by a single edge to the centre vertex, making it difficult to coarsen further.

These graphs are typical in social network structures, and can be better coarsened by clumping a number of vertices at once. At the moment, however, I am only looking to identify when such a graph is created in coarsening, so I can stop the coarsening at a level which holds useful information (constantly coarsening a graph of 500vertices, where coarsening only collapses two vertices, isn't very useful). I will most likely include the feature mentioned before at a later date so I can compare results.

Alternatively, I have yet to implement a "working" weight based coarsening, which could solve the issue. This does not avoid the fact that star-like graphs will eventually turn up somewhere, and will need to be dealt with. Walshaw mentions in his paper how the multilevel  and FDP paradigms could be used to draw and explore social network structures.

In other news, for my own enjoyment, I have been testing the coarsening part of the algorithm on larger graphs (x10^5+) to get an idea of runtime. I am looking to have results for my Eades equations on Multilevel before the end of the week (with edge-crossings counted, because YAY! my edges now coarsen correctly!!!).

I will hopefully update on Friday. All the best!

I Hate Monday's

My title is incorrect, I don't just hate Mondays, I despise them, I want to see them suffer. Now before you think I am generally hate-filled and unhappy, allow me to paint a wonderful picture of the events/discoveries over the past few days, to bring about this change of character.

During last week, I had started looking for results from my graph drawing implementation, specifically edge crossings. Note, beforehand, I had seen the multilevel algorithm working visually, and all appeared fine, par some issues with the edges being drawn.

As optimisation and runtime wasn't an issue at this stage, I used a method from the java.awt.geom.Line2D library called linesIntersect() - as the name sounds, it determines if two line segments cross. This however, always returned (V^2)/2 results for line crossings. This, I found, is due to every edge being attached to another edge, intersecting at that vertex joining them. Easy fix: if the edges are adjacent, don't count the intersection. Wrong.

The issue with edges went deeper still. After the matching and coarsening stages had been complete, the previous graphs edges were no longer valid (due to the nature of my coarsening implementation) in that they no longer held the information about the graph, but of the coarser graph (not correctly either, see my matching posts).

So how can the multiple levels still be drawn in an aesthetically pleasing sense? Well, the rabbit hole gets deeper still, the force directed placement algorithm uses the adjacent vertices list stored in each vertex, to calculate the forces (horribly inefficient use of memory I know but more of this in a bit). So the edges are used for nothing more than coarsening graphs.

Now here's the kicker, my implementation of a spring embedder heuristic is wrong. I had misinterpreted what was being described, and due to concentration on other aspects, didn't realise until I began re-reading the journals in more detail. Below is some pseudo code for a simple spring embedder implementation O(|V|^2 + |E|)

for vertex vi

   for vertex vj

       calculate repulsive forces

for edge e {v, u}

      calculate attractive forces

Below is my own implementation (in pseudo code) O(|V| . |V| . |Tv|):

for vertex vi

   for vertex vj

      for vertex k in vi.adjacent

         if k = vj : calculate attractive forces

         else : calculate repulsive forces

Odd how I neglected this, however it worked and I didn't notice any extended runtime in any of the graphs so far, so continued blissfully aware. Now that I recognise the issue, I have attempted to implement a correct version (so to fix my issues with the edges), which currently does not work, I am still unsure as to why this is, but am comfortable that my theory is correct this time.

Another misunderstanding during the later half of last week, is that of Veldhuizens' work. When I first read "dynamic", I assumed a visually dynamic implementation of a force directed placement algorithm, that could be updated in real time. However, his dynamics are far more complicated than I realised, whereby all coarsened levels of a graph change at the same time using a system of interconnected differential equations acting as dynamics between different graph levels.

Now to some lighter news, I wouldn't have noticed these issues if it wasn't for the intensive amount of reading I have completed this month. Furthermore, thanks to this reading, I now have a solid understanding of almost all areas I had issues with before, for example, I now (almost) fully understand Kamada and Kawai's force directed approach, Davidson's and Harel's ingenious method of using different parameters to control different qualities of a graph (in their Simulated Annealing approach), and am (almost) fully aware of how the dynamics equations in Veldhuizen's approach works.

Now that I have vented some steam on what I would describe as one of my most testing and soul destroying tasks yet, its time to go back to work and get a move on with getting those results. Ciao.

And then it all went horribly wrong

As the title suggests, my work isn't the awesome perfection of greatness I had wished (and convinced myself) it was.

Previous to today's tinkering, I had a "roughly" working implementation of C.Walshaw's multilevel graph drawing algorithm, using P.Eade's heuristic as opposed to the more complex FR FDP algorithm. This wasn't yet the self iterating methodology described by C.Walshaw and required me to manually create different levels of a Graph G0, i.e. pseudo code below.

Graph G1 = coarsen(G0);

Graph G2 = coarsen(G1);

Attempting to finally retrieve some results, I needed a self iterating way of coarsening a graph, which fortunately was relatively easy given the way I had designed the code (with the limit of a graph must have 2 vertices at minimum). This affects the aesthetic view in an odd way which for now is not important, and appears to work ok.

The edges of the initial graph; after coarsening, FDP and uncoarsening, have changed. The only way I can describe it is, "They're broken." An example, printing the coordinates of edge e, e.v1 and e.v2, followed by the coordinates of all vertices:

e.v1.x: 0.8628966403487646 e.v1.y: -0.041670375602711654

e.v2.x: 0.8628966403487646 e.v2.y: -0.041670375602711654

x: 0.8628966403487646   y: -0.041670375602711654
x: 1.3628966403487646   y: 0.45832962439728836
x: 0.5485572219545054   y: 0.907640284847048
x: 1.0485572219545054   y: 1.407640284847048 

This shows that the vertices belonging to the edge, are one of the same. Of course, this would normally affect the layout, however, the list of edges are not quite used in this case (I believe I mentioned this madness before; my use of an adjacent vertices list), so one wouldn't notice this issue until one looked for it.

I will update after some investigation and a fix (as other changes are required also). Good Day.

It kind of, sort of, somewhat, makes sense (touch wood)

<EDIT> I knew something was wrong with my implementation, I have found my FDP implementation is not an accurate model of Peter Eade's heuristic, in that it is slightly more complex O(|V| x (|V| x |Tv|))*. Although complex, I will (eventually) run a few tests to compare output and runtime. NB: its my hypothesis that the visual results should remain the same, however, runtime will be faster than traditional spring-embedder implementations. Testing may be unnecessary but I would like some empirical evidence in case I am wrong.

*where V is the set of vertices and Tv is the neighbourhood of vertices for vertex v (degree of v?)</EDIT>

Two weeks of extensive reading (NB: below), but I have finally come up with an excuse as to why I haven't got any results of my work (or more correctly, my implementation of others work) yet. I have been unhappy with my implementations for many reasons, so I have been reading to ensure my understanding is correct, so to avoid so many differences between my results and the results of others. Moreover, in my reading, I am finding an understanding of how different techniques change results, and consequently, am getting ideas as to how I can create my own technique for drawing graphs.

(NB: I still only recognise one week, as the first week involved tinkering and playing with my code, and not much reading actually took place).

Once again I am beginning the week with reading, however, I am at a point where after I can tweak my system and begin offering results. I am intending to have compareable results towards the end of the week, and possibly part of a draft literature review (mostly pre-2000 paper reviews), but we shall see how it goes.

This is just a small update to notify readers of my continuation of reading and the likelihood of results. Other than that, have a happy Monday...

Reading Material

An update with no update, unfortunately.

Much of my time this past week has been spent reading. Whether this is subconscious procrastination or a bid to get work done, is open for debate, however, I am formulating new ideas and changes for my current work (and future work) that should eventually make the outcome more desirable (and hopefully, make more of an impact).

I have been working through papers in as much of a chronological order as possible, this time focusing on those 'bits' I missed, willingly ignored or couldnt understand (such as Kamada and Kawai's partial differential equations) which appears to be going well. Oddly enough, reading items in an order makes concepts easier to understand.

Model/Results related, I appear to be putting this off. The intention to complete these before the next monthly or significant meeting is there, however. Giving myself a deadline of the 18th of February to complete these, amongst other things, I am aware of my current progress and my direction and will meet this, dead or alive.

For now, I will leave some internet wisdom; "If you assume I do no work, you will always be surprised when you ask for something".