aiSee User Manual: Force-Directed Layout

Force-directed layout schemes are usually selected for undirected graphs, this being ideal for simulating physical and chemical models. aiSee combines the following four ideas in its force-directed layout algorithm:

Spring forces

A spring embedder is simulated. The nodes of a graph are regarded as electrically charged particles that repel one another, the edges being regarded as springs connecting the particles. Particles that are far away from one another attract each other by spring forces, particles that are too close repel one another. (See graph attributes attraction and repulsion.)

Magnetic forces

Spring forces do not take the direction of edges into account. In directed graphs all edges should have a uniform direction to point in. Here the edges are interpreted as magnetic needles that align themselves according to a magnetic field. (See graph attributes magnetic_field1, magnetic_field2, magnetic_force1, and magnetic_force2.)

Gravitational forces

The problem with spring forces is that they are only effective in connected graphs. In unconnected graphs simulating a spring embedder makes unconnected nodes move away from one another as there are only repulsive forces but no attractive forces. That is why gravitational forces are introduced. All nodes are attracted to the bary center of all the other nodes. (See graph attribute gravity.)

Simulated annealing

The simulated annealing model is oriented to the physical process of annealing, which often leads to very regular structures (e.g. like crystals). A global energy level is computed for a graph which is the sum of all energy levels of the nodes. The energy level at a node is determined from the forces acting on it, much like the elongation of the springs. The spring embedder tries to minimize the global energy level by moving the nodes in the direction of the forces. In addition, nodes are randomly moved so as to avoid being trapped at a local energy minimum. At the beginning this is done more vigorously, with random movement being ceased towards the end in order to stabilize the final layout. The amount of random movement depends on the “temperature”, which is controlled by a temperature scheme. aiSee also supports the concept of local temperatures for a node. The temperature takes the local situation of the graph into account (see energetic) and regulates how much and how often a node is randomly moved.

The force-directed placement algorithm consists of four phases:

• Initialization phase
• First iteration phase
• Optional second iteration phase
• Final improvement phase

The two iteration phases are conceptionally the same. They simply sequentially simulate the two magnetic fields acting on the system (see graph attribute magnetic_field). The second iteration phase is omitted if there is only one magnetic field. Each iteration phase consists of a loop of iteration steps that are executed until the global temperature value has fallen below a specified threshold value (see graph attribute temptreshold) or until a maximum number of iterations is reached. In each iteration step the new impulses of the nodes (force directions) are calculated, the nodes moved to their new positions according to the impulses, and the global temperature adjusted.

In the final improvement phase, the node positions can be rastered. This is done by moving a node to its closest raster point after each iteration step.

Afterwards, the minimum x and y coordinates are calculated and the entire layout is moved so that the minimum coordinates are just zero. This step is necessary because all nodes move during the iteration phase, meaning they could have all moved away from the origin of the coordinate system. Finally, the start and end points of the edges are calculated.

aiSee offers the option of animating its internal force-directed layout calculations. Simply use the command-line option -epanim, for example:

> aisee -epanim torus.gdl