Perform the force-based algorithm on a graph.
[Go] = NL_G_ForceBasedAlgo(G,D,T,M,Le,Kc,Kh,Kt,I)
Graph.
Damping factor.
Time step.
Node mass.
Edge length at the equilibrium.
Coulomb's coefficient.
Hooke's coefficient.
Kinetik energy threshold.
Window index.
Output graph.
NL_G_ForceBasedAlgo performs the generic force-based algorithm that aims to place graph nodes in an aesthetically pleasing way such that nodes are spread over the largest area, and there are as few crossing edges as possible (WIKIPEDIA). D is the damping factor that belongs to ]0..1[. Without the damping factor, the nodes' movement does not stop. T is the simulation time step. Two forces are used to reach the equilibrium: the Hooke's law that forces each edge of the graph to reach the optimal length . For that purpose, each edge with a length L, is subjected to the force equal to
. Moreover each node is assumed to have the mass M and the charge Q=1. Thus for each set of two distinct nodes, an electromagnetic force will try to separate them by increasing the distance between them. The Coulomb's law states that the force between two nodes with charges
and
, distant from each other of
is equal to
where
represents the Coulomb's coefficient. The movement of nodes generates the global kinetik energy
. The simulation displayed inside the window I is stopped when
reaches the threshold
. The output graph is finally stored in
.
set up initial node velocities to (0,0) set up initial node positions randomly // make sure no 2 nodes are in exactly the same position loop total_kinetic_energy := 0 // running sum of total kinetic energy over all particles for each node net-force := (0, 0) // running sum of total force on this particular node for each other node net-force := net-force + Coulomb_repulsion( this_node, other_node ) next node for each spring connected to this node net-force := net-force + Hooke_attraction( this_node, spring ) next spring // without damping, it moves forever this_node.velocity := (this_node.velocity + timestep * net-force) * damping this_node.position := this_node.position + timestep * this_node.velocity total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2 next node until total_kinetic_energy is less than some small number // the simulation has stopped moving | ![]() | ![]() |