<< NL_G_EdgesOfNode NL_G: Graph NL_G_GraphCenter >>

NARVAL >> NL_G: Graph > NL_G_ForceBasedAlgo

NL_G_ForceBasedAlgo

Perform the force-based algorithm on a graph.

Calling Sequence

[Go] = NL_G_ForceBasedAlgo(G,D,T,M,Le,Kc,Kh,Kt,I)

Arguments

G :

Graph.

D :

Damping factor.

T :

Time step.

M :

Node mass.

:

Edge length at the equilibrium.

:

Coulomb's coefficient.

:

Hooke's coefficient.

:

Kinetik energy threshold.

I :

Window index.

:

Output graph.

Description

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 .

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]=NL_T_BarabasiAlbert(n,l0,L);//generation of the topology
i1=1;//window index
f=NL_G_ShowGraph(g,i1);//graph visualization
damping=0.1;//parameters
timestep=1;
m=1;
lequilibrium=10;
kh=100/(L);
kc=10*L;
tkel=10^(-3);
i2=2;//window index
[go]=NL_G_ForceBasedAlgo(g,damping,timestep,m,lequilibrium,kc,kh,tkel,i2);//application of NL_G_ForceBasedAlgo
i3=3;//window index
f=NL_G_ShowGraph(go,i3);//graph visualization

Dependency

NL_M_GraphAnimation, , NL_G_CoulombForce, NL_G_NodeNeighbors, NL_G_HookeForce

Report an issue
<< NL_G_EdgesOfNode NL_G: Graph NL_G_GraphCenter >>