Glay: Graph Visualization and Analyzation System
PrevNext

Chapter 3. On the builtin graph layout algorithms

As already said in Chapter 2 there are currently three layout algorithms available in Glay: Gem, J and JX. Gem was developed by Ingo Bruß and Ame Frick at the University of Karlsruhe. Their webpage is "http://www.info.uni-karlsruhe.de/~frick/gd/". The J algorithm was developed by us. Algorithm JX is a simple extension of J. In this chapter you find the theoretical description of these three (basically two) different layout algorithms.

3.1. The GEM algorithm

The Gem algorithm was developed by Ingo Bruss and Arne Frick, (Fakultät für Informatik, Universität Karlsruhe). The homepage of Gem is http://www.info.uni-karlsruhe.de/~frick/gd/gem3Ddraw/ The original paper on Gem: ftp://i44ftp.info.uni-karlsruhe.de/pub/papers/frick/gd95p.ps.gz

We changed the input part and the visualization part of the gem3d program, but the algorithm is the original.

You can still use the original gem input format, but now the input/output is separated, and we refer only to the algorithm when we talk about gem.

3.1.1. The gem input format

The gem input file format is the following:

1st line:

On the first line there are 2 numbers and a character separated by spaces: The number of the vertices, the number of the edges, and a character "n". ("n" would mean that the graph is undirected however the handling of directed graphs was never implemented by the authors of gem.)

vertices:

The next lines define the vertices. The first number in these lines is the index of the vertex (The first vertex should always have the number 1), then follows the shape of the vertex (quader, sphere, cone, cube, ...), finally the color (red, green, blue, balck, white, yellow, magenta, pink). Glay actually allows any colors and shapes valid elsewhere also in the gem input files.

edges:

The last part of the gem input file defines the edges. It's a simple edgelist: each line of it has 2 numbers separated by some space. Those are the indeces of the vertices incident to the edge.

3.1.2. The algorithm

The gem layout algorithm is a force-directed simluated annealing algorithm. Each vertex is affected by four forces: gravity, vertex repulsion, edge attraction, and a random force.

A very important and interesting aspect of the algorithm is how it cools the system. It defines a "local temperature" of each vertex, and modifies those independently. The "global temperature" is defined as the sum of the locals, but its only role is to stop the algorithm if it gets too low.

We talk about these later, now let's iterate the forces that act in the algorithm:

a) gravity:

The program calculates the center of mass, and after each vertex movement updates it. The garvity is a force directed towards the center of mass and depending on the distance from the center of mass linearly. The linearity constant is a specifiable parameter of the algorithm.

b) vertex repulsion:

Each vertex repulses each other. The repulsion depends on the constant "EdesSQR", which is typically equals to the (number of edges) / (number of vertices).

c) edge attraction:

If two vertices are neighbours in the graph, they attract each other. The force of this attraction is asymmetric: the vertices with higher degree are attracted weaker. Additionally there's a rule that really close vertices don't attract each other.

d) random force:

At each step there is a random force the magnitude of which is depends only on the number of vertices and edges.

3.1.2.1. A step of the algoritm

In each step the algorithm moves all the vertices one by one, in an order randomized at the beginning of the step.

The move of a vertex depends only on the direction of the resultant force, not on the magnitude of it. The length of the move is "equal" to the temperature of the vertex.

3.1.3. Specialities

The gem algorithm has protection against oscillation and rotation of vertices. These operate by heating and cooling the points depending on the directions of the sequential steps. In this algoritm this is the only source of the temperature-change: no global cooling at all! However, the vertices do not have impulse, they just step from a standing position each time, so this "oscillation protection" and "rotation protection" has a great deal of randomness in it: they realize roughly the global cooling, and a little "plus". And this little "plus" is what we think its power is...

a) oscillation-protection:

If the direction of the new step of the vertex is almost opposite to the direction of the former step, then we cool the vertex. If those directions are nearly equal, then we heat the vertex creating a positive feedback to encourage the motion.

b) rotation-protection:

The new temperature of the vertex also depends on the angle of the turn. If the vertex turns less, then it is cooled slower.

3.1.4. Our experiences and opinions

* The algorithm works very fast.

* It is very strong in the case of some symmetric, sphere like graphs.

* We feel that it lacks a little bit in the clarity of using notations of physics like temperature and heat, impulse, length, weight, degree, or force.

* When we experimented with it and we needed to produce a layout of some real life biological network we needed some extra parameters, like for adjusting the strength of the attractive or the repulsive forces. The algorithm actually proved to be very sensitive to a lot of constants.

* In some cases adding some global cooling (as present in traditional simulated annealing algorithms) made the results better.

Finding the ideas in gem very interesting but the original source having these issues made us decide to write our own algorithm. We tried to incorporate all the best ideas, and make it even better. What we got is certainly different. It is slower, but for some cases we had nicer results. However, for some cases -- like for the buckey-ball -- Gem seems to be unbeatable and we think the original Gem very well deserves to be kept as one of the choices among the layout algorithms we have in Glay.

PrevHomeNext
Getting more control by action files The J algorithm