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 another by spring forces, particles that are too close repel one another.

• 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.

• 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.

• 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 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.

  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. The second iteration phase is omitted if there is only one magnetic field.

One iteration phase consists of a loop of iteration steps that are executed until the global temperature value has fallen below a specified threshold value 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.

Finally, 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. Afterwards, the start and end points of the edges are calculated.