<< NARVAL_G_EdgesOfNode NARVAL NARVAL_G_GraphConnex >>

NARVAL >> NARVAL > NARVAL_G_ForceBasedA

NARVAL_G_ForceBasedA

Perform the force-based algorithm on a graph.

Calling Sequence

[go]=NARVAL_G_ForceBasedA(g,d,t,m,le,kc,kh,ket,ind)

Parameters

g :

graph.

d :

damping factor.

t :

time step.

m :

node mass.

le :

edge length at the equilibrium.

kc :

Coulomb's coefficient.

kh :

Hooke's coefficient.

ket :

kinetik energy threshold.

ind :

window index.

go :

output graph.

Description

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. 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 each edge with a longer 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 in window ind is stopped when KE reaches the threshold ket. The output graph is finally stored in go.

Pseudo-Code (Wikipedia)

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

Examples

n=25;//network size
l0=5;//a maximum of 5 links are created for any created node
L=1000;//network square area side 
[g,d]=NARVAL_T_BarabasiAlbert(n,l0,L);//generation of the topology
i1=1;
f=NARVAL_G_ShowGraph(g,i1);
damping=0.1;
timestep=1;
m=1;
lequilibrium=10;
kh=100/(L);
kc=10*L;
tkel=10^(-3);
i2=2;
[go]=NARVAL_G_ForceBasedA(g,damping,timestep,m,lequilibrium,kc,kh,tkel,i2);//application of NARVAL_G_ForceBasedA
i3=3;
f=NARVAL_G_ShowGraph(go,i3);

Dependency

NARVAL_F_Remov, NARVAL_G_NodeNeighbors, NARVAL_G_CoulombForce, NARVAL_G_HookeForce

Author

http://wwwen.uni.lu/interdisciplinary_centre_for_security_reliability_and_trust

Contact

<< NARVAL_G_EdgesOfNode NARVAL NARVAL_G_GraphConnex >>