Utilitaire pour indexer des informations de la blockchain et dessiner des Plots. Focalisé sur la toile de confiance. http://datajune.coinduf.eu/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

136 lines
5.4 KiB

module ForceLayout
"""
ForceLayout module implements force layout methods with fine grain
to allow building step by step custom layout algorithms
uses 2D positions defined as a 2×N array
"""
using LightGraphs, Random, Statistics
"like LightGraphs random_layout, but scales to the square of size a, allows fixed seed"
function random_layout(N::Int, a::Float64; seed::Integer=rand(UInt))
rng = MersenneTwister(seed)
return reshape(a*(2 .* rand(rng, N*2) .- 1.0), 2, N)
end
"modifies force vector with quadratic force applying on each point"
function quadratic!(locs::AbstractMatrix, forces::AbstractMatrix, ::Float64)
N = size(locs, 2)
for i in 1:N
for j in 1:i-1
vx, vy = locs[1,j] - locs[1,i], locs[2,j] - locs[2,i] # vector IJ
α = / (0.1 + vx^2 + vy^2) # k²/d² factor
Fix = α*vx; Fiy = α*vy; # force
forces[1,i] += Fix; forces[2,i] += Fiy # updates force vector
forces[1,j] -= Fix; forces[2,j] -= Fiy # updates force vector
end
end
end
"modifies force vector with quadratic force applying on each point and a charge"
function quadratic_with_charge!(locs::AbstractMatrix, forces::AbstractMatrix, ::Float64, charge::AbstractVector)
N = size(locs, 2)
for i in 1:N
for j in 1:i-1
vx, vy = locs[1,j] - locs[1,i], locs[2,j] - locs[2,i] # vector IJ
α = charge[i] * charge[j] * / (0.1 + vx^2 + vy^2) # k²/d² factor
Fix = α*vx; Fiy = α*vy; # force
forces[1,i] += Fix; forces[2,i] += Fiy # updates force vector
forces[1,j] -= Fix; forces[2,j] -= Fiy # updates force vector
end
end
end
"modifies force vector with attractive force (called gravity in fa2)"
function center_attraction!(locs::AbstractMatrix, forces::AbstractMatrix, g::Float64, mass::AbstractVector)
N = size(locs, 2)
for i in 1:N
vx, vy = locs[1,i], locs[2,i] # vector OI
α = mass[i] * g / (vx^2 + vy^2) # k²/d² factor
forces[1,i] -= α*vx; forces[2,i] -= α*vy # updates force vector
end
end
"""modifies force vector with linear attraction force for each node trough edge
(intended to work on undirected graph)"""
function edge_linear!(g::AbstractGraph, locs::AbstractMatrix, forces::AbstractMatrix, mass::AbstractVector, α::Float64)
for e in edges(g)
a = e.src; b = e.dst
vx, vy = locs[1,b] - locs[1,a], locs[2,b] - locs[2,a] # vector AB
forces[1,a] += α*vx ./ mass[a]; forces[2,a] += α*vy ./ mass[a] # adds αAB/m_a to a
forces[1,b] -= α*vx ./ mass[b]; forces[2,b] -= α*vy ./ mass[b] # adds αBA/m_b to b
end
end
"""modifies force vector with 'linlog' attraction force for each node trough edge
(intended to work on undirected graph)"""
function edge_linlog!(g::AbstractGraph, locs::AbstractMatrix, forces::AbstractMatrix, mass::AbstractVector)
for e in edges(g)
a = e.src; b = e.dst
vx, vy = locs[1,b] - locs[1,a], locs[2,b] - locs[2,a] # vector AB
dist = sqrt(vx^2 + vy^2)
α = log(1+dist)/dist # 'linlog' factor
forces[1,a] += α*vx ./ mass[a]; forces[2,a] += α*vy ./ mass[a] # adds αAB/m_a to a
forces[1,b] -= α*vx ./ mass[b]; forces[2,b] -= α*vy ./ mass[b] # adds αBA/m_b to b
end
end
"roll displacement and stabilize with limitations based on old displacement"
function stabilize!(disp::AbstractMatrix, o_disp::AbstractMatrix)
for i = 1:size(disp, 2)
a_i = sqrt( (o_disp[1,i] - disp[1,i])^2 + (o_disp[2,i] - disp[2,i])^2 ) # acceleration (swinging)
p_i = sqrt( (o_disp[1,i] + disp[1,i])^2 + (o_disp[2,i] + disp[2,i])^2 ) # persistence (traction)
α = log(1+p_i)/(1+sqrt(a_i)) # stabilisation factor
o_disp[1,i] = disp[1,i]; o_disp[2,i] = disp[2,i] # roll disp to old_disp
disp[1,i] *= α; disp[2,i] *= α # apply stabilization factor
end
end
"applies edge linear attraction, electrostatic repulsion, and stabilisation before applying"
function custom_layout_0!(g::AbstractGraph,
fixed::AbstractVector,
locs::AbstractMatrix,
disp::AbstractMatrix,
o_disp::AbstractMatrix,
mass::AbstractVector,
charge::AbstractVector)
N = nv(g)
disp[:] .= 0.0 # reinit forces (displacement is treated like a force)
edge_linear!(g, locs, disp, mass, 0.5) # compute linear force on edge ends
quadratic_with_charge!(locs, disp, -5.0, charge) # compute electrostatic repulsion
stabilize!(disp, o_disp) # roll displacement and smooth it
disp[:, fixed] .= 0 # remove displacement of fixed nodes
locs .+= disp
end
"edge linear attraction, move, electrostatic repulsion, move"
function custom_layout_1!(g::AbstractGraph,
locs::AbstractMatrix,
disp::AbstractMatrix,
mass::AbstractVector)
N = nv(g)
disp[:] .= 0.0
edge_linear!(g, locs, disp, mass, 0.5)
locs .+= disp
quadratic!(locs, disp, -5.0)
locs .+= disp
end
"""ForceAtlas2 algorithm
(not sure it's consistent with reference implementation)"""
function force_atlas_2!(g::AbstractGraph,
locs::AbstractMatrix,
disp::AbstractMatrix,
o_disp::AbstractMatrix,
mass::AbstractVector)
N = nv(g)
disp[:] .= 0.0
edge_linlog!(g, locs, disp, mass)
quadratic_with_charge!(locs, disp, -1/500000, mass)
center_attraction!(locs, disp, 1/200, mass)
stabilize!(disp, o_disp)
locs .+= disp./2
end
end