|
|
The J algorithm is a force-directed simulated annealing algorithm.
The vertices are moving in a potential space generated by three type of
forces: gravitation, vertex repulsion and edge attraction.
The algorithm is divided into rounds. In each round all vertices make a step.
The step of a vertex is constituted of 2 parts: a random movement and a
force-driven move.
- a) The random move
At the beginning of each step we try to move the vertex randomly.
The length of the movement depends on the temperature of the vertex and the
length of the last step of the vertex.
If by chance we stepped to a position with a lower potential
or we did not but the temperature of the vertex is high enough then we
leave the vertex at the new position. Otherwise we roll back the move,
and make a very small random step.
The length of that small movement depends on the temperature and the (geometric)
size of the system.
- b) The force-driven move
We calculate the forces applied to the vertex:
i) 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.
ii) Vertex repulsion: Each vertex repulses each other. The repulsion force depends
reciprocally on the square distance between the vertices and linearly
on the mass. If the mass of the vertices is not specified then all vertices
are considered having unit mass. There is a specifiable scaling parameter of the
repulsion force.
iii) Edge attraction:
The edges are similar to a spring, they converge to an uniform optimal
length. (This is a specifiable parameter too.) If two vertices are
neighbours in the graph and they are far away, then they attract each
other. The attraction force is a square function of the distance between the
vertices. There is a specifiable scaling parameter of the attraction
force. If the two vertices are close then they repulse each other
like in ii).
After we have calculated the forces we try to move the vertex towards the
direction of the resultant force. We find the new position of the vertex
by an iteration.
1. At first the length of the movement is equal
to the length of the previous step. If the potential in the new
position is lower then we put the vertex there, otherwise we
leave it where it is.
2. Now depending on the success of the step, we either double or
halve the step length.
3. We try to step again. The step is succesful if it goes to
a lower potential place and unsuccessful if it does not.
4. Go to 2. if we did not exceed the number of cycles yet.
The number of the cycles we make is a specifiable scaling parameter
of the algorithm. There is also a maximal and a minimal limit of the length
of the movement of the vertex.
After moving the vertex we modify the temperature of it. The
new temperature depends on the old temperature, on the average
potential of the vertices, on the rate of the new and the old
potential, and on a lot of specifiable parameters.
We tried to cook the best soup out of all the available parameters,
and make up the best working cooling function. The result is
what we left in our program.
However, we found that a simple 0.95-exponential function is almost as
good as this.
If two vertices are distant and they aren't neighbours then the
repulsion force between them is very small. When we calculate the forces or the
potentials we don't care about these small forces.
We try to detect the oscillations. The vertices have a "history", each
vertex remember some previous positions. (The size of the history is a
specifiable parameter.) When If the vertex has oscillation, we cool it
better.
|