Perform the force-based algorithm on a graph.
[go] = NARVAL_G_ForceBasedA(g,d,t,m,le,kc,kh,ket,ind)
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.
NARVAL_G_ForceBasedA performs a 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 a 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 le. For that purpose, each edge with a length l, is subjected to the force equal to kh*(l-le). 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 qi and qj, distant from each other of lij is equal to kc*qi*qj/(lij)^2 where kc represents the Coulomb's coefficient. The movement of nodes generates the global kinetik energy KE. The simulation displayed inside the window ind is stopped when KE reaches the threshold ket. The output graph is finally stored in go.
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 | ![]() | ![]() |
Dr. Foued Melakessou
Research Associate
Interdisciplinary Centre for Security, Reliability and Trust
Room F106
University of Luxembourg
6, rue Coudenhove Kalergi
L-1359 Luxembourg-Kirchberg
E-mail: foued.melakessou@uni.lu
Tel: (+352) 46 66 44 5346