Will Anderson
353 lines
14 KiB
EmacsLisp
353 lines
14 KiB
EmacsLisp
// layout.el — Force-directed layout engine (pure El math).
|
|
//
|
|
// Implements a basic spring-force simulation:
|
|
// - Coulomb repulsion between every pair of nodes (O(n²))
|
|
// - Hooke spring attraction along edges
|
|
// - Weak gravity toward the canvas center
|
|
// - Velocity damping per iteration
|
|
//
|
|
// Float representation: El stores floats as bit-cast int64_t values.
|
|
// All math uses int_to_float() for literals and math_sqrt() for sqrt.
|
|
//
|
|
// Public API:
|
|
// layout_run(nodes_json, edges_json, width, height, iterations) -> String
|
|
// nodes_json — JSON array: [{ id, salience, ... }, ...]
|
|
// edges_json — JSON array: [{ source_id, target_id, weight }, ...]
|
|
// width/height — canvas Float dimensions
|
|
// iterations — simulation steps (default 150 for good convergence)
|
|
// Returns JSON array: [{ id, x, y }, ...]
|
|
|
|
// ── Constants ────────────────────────────────────────────────────────────────
|
|
|
|
fn layout_repulsion_k() -> Float {
|
|
// Coulomb constant — controls node spread.
|
|
int_to_float(3000)
|
|
}
|
|
|
|
fn layout_spring_k() -> Float {
|
|
// Spring stiffness for edge attraction.
|
|
int_to_float(1)
|
|
}
|
|
|
|
fn layout_spring_rest() -> Float {
|
|
// Rest length for edges (px).
|
|
int_to_float(80)
|
|
}
|
|
|
|
fn layout_gravity_k() -> Float {
|
|
// Gravity toward center (gentle).
|
|
int_to_float(1)
|
|
}
|
|
|
|
fn layout_damping() -> Float {
|
|
// Velocity decay per step (0.85 = 15% loss per step).
|
|
let d: Float = int_to_float(85)
|
|
d / int_to_float(100)
|
|
}
|
|
|
|
fn layout_max_velocity() -> Float {
|
|
// Cap velocity per step to avoid explosion.
|
|
int_to_float(50)
|
|
}
|
|
|
|
fn layout_min_dist() -> Float {
|
|
// Minimum distance to prevent division by zero in repulsion.
|
|
int_to_float(1)
|
|
}
|
|
|
|
// ── State keys (process state for per-node data) ─────────────────────────────
|
|
//
|
|
// We use process state (state_set/state_get) as a flat key/value store since
|
|
// El does not have mutable arrays or map mutation without re-assignment.
|
|
// Key patterns:
|
|
// "node_ids" — comma-separated node id list
|
|
// "node_x_<id>" — x position
|
|
// "node_y_<id>" — y position
|
|
// "node_vx_<id>" — x velocity
|
|
// "node_vy_<id>" — y velocity
|
|
|
|
fn layout_key_x(node_id: String) -> String { "node_x_" + node_id }
|
|
fn layout_key_y(node_id: String) -> String { "node_y_" + node_id }
|
|
fn layout_key_vx(node_id: String) -> String { "node_vx_" + node_id }
|
|
fn layout_key_vy(node_id: String) -> String { "node_vy_" + node_id }
|
|
|
|
// ── Initialization ───────────────────────────────────────────────────────────
|
|
//
|
|
// Distribute nodes in a circle around the center so no two start at the
|
|
// same position (which would make repulsion forces zero and give no movement).
|
|
|
|
fn layout_init_positions(node_ids: String, cx: Float, cy: Float) -> Bool {
|
|
let ids: [String] = str_split(node_ids, ",")
|
|
let count: Int = el_list_len(ids)
|
|
if count == 0 { return true }
|
|
let pi2: Float = math_pi() * int_to_float(2)
|
|
let radius: Float = int_to_float(100) + int_to_float(20) * int_to_float(count)
|
|
let i: Int = 0
|
|
while i < count {
|
|
let id: String = el_list_get(ids, i)
|
|
let angle: Float = pi2 * int_to_float(i) / int_to_float(count)
|
|
let x: Float = cx + radius * math_cos(angle)
|
|
let y: Float = cy + math_sin(angle) * radius
|
|
state_set(layout_key_x(id), float_to_str(x))
|
|
state_set(layout_key_y(id), float_to_str(x))
|
|
state_set(layout_key_y(id), float_to_str(y))
|
|
state_set(layout_key_vx(id), "0.0")
|
|
state_set(layout_key_vy(id), "0.0")
|
|
let i = i + 1
|
|
}
|
|
true
|
|
}
|
|
|
|
// ── Float helpers ─────────────────────────────────────────────────────────────
|
|
|
|
fn layout_get_x(id: String) -> Float {
|
|
str_to_float(state_get(layout_key_x(id)))
|
|
}
|
|
|
|
fn layout_get_y(id: String) -> Float {
|
|
str_to_float(state_get(layout_key_y(id)))
|
|
}
|
|
|
|
fn layout_get_vx(id: String) -> Float {
|
|
str_to_float(state_get(layout_key_vx(id)))
|
|
}
|
|
|
|
fn layout_get_vy(id: String) -> Float {
|
|
str_to_float(state_get(layout_key_vy(id)))
|
|
}
|
|
|
|
fn float_clamp(v: Float, lo: Float, hi: Float) -> Float {
|
|
if v < lo { return lo }
|
|
if v > hi { return hi }
|
|
v
|
|
}
|
|
|
|
fn float_abs(v: Float) -> Float {
|
|
if v < int_to_float(0) { return int_to_float(0) - v }
|
|
v
|
|
}
|
|
|
|
// ── Repulsion pass ────────────────────────────────────────────────────────────
|
|
//
|
|
// For each pair (a, b): compute Coulomb repulsion and accumulate forces.
|
|
// Force direction: along the vector from b to a (a is pushed away from b).
|
|
// Magnitude: k / dist^2
|
|
|
|
fn layout_repulsion_pass(node_ids: String) -> Bool {
|
|
let ids: [String] = str_split(node_ids, ",")
|
|
let n: Int = el_list_len(ids)
|
|
let i: Int = 0
|
|
while i < n {
|
|
let id_a: String = el_list_get(ids, i)
|
|
let ax: Float = layout_get_x(id_a)
|
|
let ay: Float = layout_get_y(id_a)
|
|
let fx: Float = int_to_float(0)
|
|
let fy: Float = int_to_float(0)
|
|
let j: Int = 0
|
|
while j < n {
|
|
if j != i {
|
|
let id_b: String = el_list_get(ids, j)
|
|
let bx: Float = layout_get_x(id_b)
|
|
let by: Float = layout_get_y(id_b)
|
|
let dx: Float = ax - bx
|
|
let dy: Float = ay - by
|
|
let dist_sq: Float = dx * dx + dy * dy
|
|
let dist: Float = math_sqrt(dist_sq)
|
|
let safe_dist: Float = if dist < layout_min_dist() { layout_min_dist() } else { dist }
|
|
let force: Float = layout_repulsion_k() / (safe_dist * safe_dist)
|
|
let nx: Float = dx / safe_dist
|
|
let ny: Float = dy / safe_dist
|
|
let fx = fx + nx * force
|
|
let fy = fy + ny * force
|
|
}
|
|
let j = j + 1
|
|
}
|
|
// Accumulate: store forces temporarily in velocity (they are scaled later)
|
|
// Use "fx_<id>" keys for accumulation.
|
|
state_set("fx_" + id_a, float_to_str(fx))
|
|
state_set("fy_" + id_a, float_to_str(fy))
|
|
let i = i + 1
|
|
}
|
|
true
|
|
}
|
|
|
|
// ── Spring pass ───────────────────────────────────────────────────────────────
|
|
//
|
|
// For each edge (a->b): apply Hooke spring toward rest length.
|
|
// Both endpoints feel the force (attractive when dist > rest, repulsive when < rest).
|
|
|
|
fn layout_spring_pass(node_ids: String, edges_json: String) -> Bool {
|
|
let edge_count: Int = json_array_len(edges_json)
|
|
let i: Int = 0
|
|
while i < edge_count {
|
|
let e: String = json_array_get(edges_json, i)
|
|
let src: String = json_get_string(e, "source_id")
|
|
let tgt_raw: String = json_get_string(e, "target_id")
|
|
// Support both source_id/target_id and source/target field names
|
|
let src2: String = if str_eq(src, "") { json_get_string(e, "source") } else { src }
|
|
let tgt2: String = if str_eq(tgt_raw, "") { json_get_string(e, "target") } else { tgt_raw }
|
|
let w: Float = json_get_float(e, "weight")
|
|
let eff_w: Float = if w == int_to_float(0) { int_to_float(1) } else { w }
|
|
|
|
// Only apply spring if both endpoints are in our node set
|
|
let sx: String = state_get(layout_key_x(src2))
|
|
let tx_chk: String = state_get(layout_key_x(tgt2))
|
|
if !str_eq(sx, "") {
|
|
if !str_eq(tx_chk, "") {
|
|
let ax: Float = layout_get_x(src2)
|
|
let ay: Float = layout_get_y(src2)
|
|
let bx: Float = layout_get_x(tgt2)
|
|
let by_val: Float = layout_get_y(tgt2)
|
|
let dx: Float = bx - ax
|
|
let dy: Float = by_val - ay
|
|
let dist_sq: Float = dx * dx + dy * dy
|
|
let dist: Float = math_sqrt(dist_sq)
|
|
let safe_dist: Float = if dist < layout_min_dist() { layout_min_dist() } else { dist }
|
|
let stretch: Float = (safe_dist - layout_spring_rest()) * layout_spring_k() * eff_w
|
|
let nx: Float = dx / safe_dist
|
|
let ny: Float = dy / safe_dist
|
|
let spring_fx: Float = nx * stretch
|
|
let spring_fy: Float = ny * stretch
|
|
|
|
// Add to accumulated forces
|
|
let cur_fx_a: Float = str_to_float(state_get("fx_" + src2))
|
|
let cur_fy_a: Float = str_to_float(state_get("fy_" + src2))
|
|
state_set("fx_" + src2, float_to_str(cur_fx_a + spring_fx))
|
|
state_set("fy_" + src2, float_to_str(cur_fy_a + spring_fy))
|
|
|
|
let cur_fx_b: Float = str_to_float(state_get("fx_" + tgt2))
|
|
let cur_fy_b: Float = str_to_float(state_get("fy_" + tgt2))
|
|
state_set("fx_" + tgt2, float_to_str(cur_fx_b - spring_fx))
|
|
state_set("fy_" + tgt2, float_to_str(cur_fy_b - spring_fy))
|
|
}
|
|
}
|
|
let i = i + 1
|
|
}
|
|
true
|
|
}
|
|
|
|
// ── Gravity pass ──────────────────────────────────────────────────────────────
|
|
//
|
|
// Weak attraction toward canvas center to prevent isolated nodes from drifting.
|
|
|
|
fn layout_gravity_pass(node_ids: String, cx: Float, cy: Float) -> Bool {
|
|
let ids: [String] = str_split(node_ids, ",")
|
|
let n: Int = el_list_len(ids)
|
|
let i: Int = 0
|
|
while i < n {
|
|
let id: String = el_list_get(ids, i)
|
|
let x: Float = layout_get_x(id)
|
|
let y: Float = layout_get_y(id)
|
|
let gx: Float = (cx - x) * layout_gravity_k() / int_to_float(100)
|
|
let gy: Float = (cy - y) * layout_gravity_k() / int_to_float(100)
|
|
let cur_fx: Float = str_to_float(state_get("fx_" + id))
|
|
let cur_fy: Float = str_to_float(state_get("fy_" + id))
|
|
state_set("fx_" + id, float_to_str(cur_fx + gx))
|
|
state_set("fy_" + id, float_to_str(cur_fy + gy))
|
|
let i = i + 1
|
|
}
|
|
true
|
|
}
|
|
|
|
// ── Integration pass ──────────────────────────────────────────────────────────
|
|
//
|
|
// Apply forces to velocities (with damping), then update positions.
|
|
// Clamp positions to stay within canvas bounds (with 20px margin).
|
|
|
|
fn layout_integrate(node_ids: String, width: Float, height: Float) -> Bool {
|
|
let ids: [String] = str_split(node_ids, ",")
|
|
let n: Int = el_list_len(ids)
|
|
let max_v: Float = layout_max_velocity()
|
|
let damp: Float = layout_damping()
|
|
let margin: Float = int_to_float(20)
|
|
let i: Int = 0
|
|
while i < n {
|
|
let id: String = el_list_get(ids, i)
|
|
let vx: Float = (layout_get_vx(id) + str_to_float(state_get("fx_" + id))) * damp
|
|
let vy: Float = (layout_get_vy(id) + str_to_float(state_get("fy_" + id))) * damp
|
|
// Clamp velocity magnitude
|
|
let vx_clamped: Float = float_clamp(vx, int_to_float(0) - max_v, max_v)
|
|
let vy_clamped: Float = float_clamp(vy, int_to_float(0) - max_v, max_v)
|
|
let new_x: Float = float_clamp(layout_get_x(id) + vx_clamped, margin, width - margin)
|
|
let new_y: Float = float_clamp(layout_get_y(id) + vy_clamped, margin, height - margin)
|
|
state_set(layout_key_x(id), float_to_str(new_x))
|
|
state_set(layout_key_y(id), float_to_str(new_y))
|
|
state_set(layout_key_vx(id), float_to_str(vx_clamped))
|
|
state_set(layout_key_vy(id), float_to_str(vy_clamped))
|
|
// Reset force accumulators for next iteration
|
|
state_set("fx_" + id, "0.0")
|
|
state_set("fy_" + id, "0.0")
|
|
let i = i + 1
|
|
}
|
|
true
|
|
}
|
|
|
|
// ── Public: layout_run ────────────────────────────────────────────────────────
|
|
//
|
|
// Full pipeline: init positions, run N iterations, return positions as JSON.
|
|
//
|
|
// Input nodes_json must be a JSON array of objects with at least an "id" field.
|
|
// Returns: JSON array [{ "id": "...", "x": 123.0, "y": 456.0 }, ...]
|
|
|
|
fn layout_run(nodes_json: String, edges_json: String, width: Float, height: Float, iterations: Int) -> String {
|
|
let cx: Float = width / int_to_float(2)
|
|
let cy: Float = height / int_to_float(2)
|
|
|
|
// Build comma-separated node_ids list
|
|
let node_count: Int = json_array_len(nodes_json)
|
|
if node_count == 0 { return "[]" }
|
|
|
|
let node_ids: String = ""
|
|
let first: Bool = true
|
|
let i: Int = 0
|
|
while i < node_count {
|
|
let n: String = json_array_get(nodes_json, i)
|
|
let id: String = json_get_string(n, "id")
|
|
if !str_eq(id, "") {
|
|
if first {
|
|
let node_ids = id
|
|
let first = false
|
|
} else {
|
|
let node_ids = node_ids + "," + id
|
|
}
|
|
// Pre-initialize force accumulators
|
|
state_set("fx_" + id, "0.0")
|
|
state_set("fy_" + id, "0.0")
|
|
}
|
|
let i = i + 1
|
|
}
|
|
|
|
// Initialize positions (circle around center)
|
|
layout_init_positions(node_ids, cx, cy)
|
|
|
|
// Simulation loop
|
|
let iter: Int = 0
|
|
while iter < iterations {
|
|
layout_repulsion_pass(node_ids)
|
|
layout_spring_pass(node_ids, edges_json)
|
|
layout_gravity_pass(node_ids, cx, cy)
|
|
layout_integrate(node_ids, width, height)
|
|
let iter = iter + 1
|
|
}
|
|
|
|
// Collect results as JSON array
|
|
let result: String = "["
|
|
let ids: [String] = str_split(node_ids, ",")
|
|
let n2: Int = el_list_len(ids)
|
|
let j: Int = 0
|
|
while j < n2 {
|
|
let id: String = el_list_get(ids, j)
|
|
let x: Float = layout_get_x(id)
|
|
let y: Float = layout_get_y(id)
|
|
let entry: String = "{\"id\":\"" + id + "\",\"x\":" + format_float(x, 1) + ",\"y\":" + format_float(y, 1) + "}"
|
|
if j == 0 {
|
|
let result = result + entry
|
|
} else {
|
|
let result = result + "," + entry
|
|
}
|
|
let j = j + 1
|
|
}
|
|
let result = result + "]"
|
|
result
|
|
}
|