Script pour obtenir une animation de la toile de confiance duniter. [dépôt archivé] le code a été intégré à DataJune (https://git.42l.fr/HugoTrentesaux/DataJune.jl)
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.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.
 
 
 

145 lines
5.7 KiB

# Custom layout algorithms that could be integrated into GraphPlot
# locs is a 2×N array
module CustomLayout
using LightGraphs
using Random
using Statistics
using WotUtils
function random_layout(g::AbstractGraph; seed::Integer=rand(UInt))
"""like LightGraphs random_layout, but scales to the square of size N, allows fixed seed"""
N = nv(g)
rng = MersenneTwister(seed)
return reshape(sqrt(N)*(2 .* rand(rng, N*2) .- 1.0), 2, N)
end
function quadratic!(locs::AbstractArray, forces::AbstractArray, ::Float64)
"""modifies force vector with quadratic force applying on each point"""
N = size(locs, 2)
@fastmath @inbounds for i in 1:N
@simd 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
function quadratic_with_charge!(locs::AbstractArray, forces::AbstractArray, ::Float64, charge::AbstractArray)
"""modifies force vector with quadratic force applying on each point"""
N = size(locs, 2)
@fastmath @inbounds for i in 1:N
@simd 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
function center_attraction!(locs::AbstractArray, forces::AbstractArray, g::Float64, mass::AbstractArray)
"""modifies force vector with attractive force (called gravity in fa2)"""
N = size(locs, 2)
@fastmath @inbounds @simd 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
function edge_linear!(g::AbstractGraph, locs::AbstractArray, forces::AbstractArray, mass::AbstractArray, α::Float64)
"""modifies force vector with linear attraction force for each node trough edge
intended to work on undirected graph"""
@fastmath @inbounds 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
function edge_linlog!(g::AbstractGraph, locs::AbstractArray, forces::AbstractArray, mass::AbstractArray)
"""modifies force vector with linear attraction force for each node trough edge
intended to work on undirected graph"""
@fastmath @inbounds 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
function stabilize!(disp::AbstractArray, o_disp::AbstractArray)
"""roll displacement and stabilize with limitations based on old displacement"""
@fastmath @inbounds 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
function my_layout_0!(g::AbstractGraph,
fixed::AbstractArray,
locs::AbstractArray,
disp::AbstractArray,
o_disp::AbstractArray,
mass::AbstractArray,
charge::AbstractArray)
"""applies edge linear attraction, electrostatic repulsion, and stabilisation before moving"""
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
function my_layout_1!(g::AbstractGraph,
locs::AbstractArray,
disp::AbstractArray,
mass::AbstractArray)
"""edge linear attraction, move, electrostatic repulsion, move"""
N = nv(g)
disp[:] .= 0.0
edge_linear!(g, locs, disp, mass, 0.5)
locs .+= disp
quadratic!(locs, disp, -5.0)
locs .+= disp
end
function force_atlas_2!(g::AbstractGraph,
locs::AbstractArray,
disp::AbstractArray,
o_disp::AbstractArray,
mass::AbstractArray)
"""use forceAtlas2 computation
I'm not sure why I do not get better constants"""
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
function custom_layout!(state::WotUtils.WotState; ITER=100)
"""run my_layout_0 on state multiple times and then electrostatic once"""
for i = 1:ITER
my_layout_0!(state.ug, state.fixed, state.locs, state.disp, state.prev_disp, state.mass, state.charge)
end
end
end