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.