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

}