Repository Public
1// Author: Simon-Pierre Boucher — contact@spboucher.ai2// File: SPChat/Core/Graph/ForceLayout.swift3// Description: Deterministic force-directed graph layout (Fruchterman–Reingold with gravity and cooling), pure and seedable, meant to run off the main thread.4import Foundation56/// A small force-directed layout for graphs of a few hundred nodes.7///8/// Pure function of its inputs: the same nodes, edges, size and seed always give the same positions (the only9/// randomness is a seeded generator for the starting positions). The temperature cools to zero, so the simulation10/// always settles; every position is finite and inside the bounds, whatever the input (isolated nodes, duplicate11/// or invalid edges, a single node, zero size).12public enum ForceLayout {13 public struct Point: Sendable, Hashable {14 public var x: Double15 public var y: Double16 public init(x: Double, y: Double) { self.x = x; self.y = y }17 }1819 public struct Edge: Sendable, Hashable {20 public var a: Int21 public var b: Int22 /// 0…1 — how strongly the two nodes attract each other.23 public var strength: Double24 public init(_ a: Int, _ b: Int, strength: Double = 1) { self.a = a; self.b = b; self.strength = strength }25 }2627 public struct Configuration: Sendable, Hashable {28 public var iterations = 32029 public var seed: UInt64 = 130 /// Space kept free along the edges of the bounds.31 public var padding = 28.032 /// Pull towards the centre: keeps unconnected nodes and components from drifting to the corners.33 public var gravity = 0.04534 /// Multiplies the ideal distance between two nodes.35 public var spread = 0.936 public init() {}37 }3839 public struct Result: Sendable, Hashable {40 public var positions: [Point]41 /// Largest move of a node during the last iteration (points): close to zero once settled.42 public var residual: Double43 public var iterations: Int44 }4546 /// SplitMix64: tiny, well distributed, and identical on every platform.47 struct Generator {48 var state: UInt6449 mutating func next() -> UInt64 {50 state &+= 0x9E37_79B9_7F4A_7C1551 var z = state52 z = (z ^ (z >> 30)) &* 0xBF58_476D_1CE4_E5B953 z = (z ^ (z >> 27)) &* 0x94D0_49BB_1331_11EB54 return z ^ (z >> 31)55 }56 /// Uniform in [0, 1).57 mutating func unit() -> Double { Double(next() >> 11) / Double(1 << 53) }58 }5960 /// - Parameters:61 /// - radii: radius of each node (its count is the node count); used to keep big nodes apart and inside the bounds.62 /// - edges: pairs of node indices; out-of-range and self edges are ignored.63 /// - width, height: the bounds, origin at the top-left corner.64 public static func run(radii: [Double], edges: [Edge], width: Double, height: Double, configuration: Configuration = Configuration()) -> Result {65 let n = radii.count66 guard n > 0 else { return Result(positions: [], residual: 0, iterations: 0) }67 let w = width.isFinite ? max(width, 1) : 1, h = height.isFinite ? max(height, 1) : 168 let r = radii.map { $0.isFinite ? max($0, 0) : 0 }69 let pad = max(configuration.padding, 0)70 func clamp(_ p: Point, _ i: Int) -> Point {71 let mx = min(pad + r[i], w / 2), my = min(pad + r[i], h / 2)72 return Point(x: min(max(p.x, mx), w - mx), y: min(max(p.y, my), h - my))73 }74 let centre = Point(x: w / 2, y: h / 2)75 guard n > 1 else { return Result(positions: [centre], residual: 0, iterations: 0) }7677 var rng = Generator(state: configuration.seed)78 // start on a jittered disc around the centre: no two nodes share a position79 var pos = (0..<n).map { i -> Point in80 let angle = rng.unit() * 2 * Double.pi, radius = (0.15 + 0.85 * rng.unit().squareRoot()) * min(w, h) * 0.3881 return clamp(Point(x: centre.x + cos(angle) * radius, y: centre.y + sin(angle) * radius), i)82 }83 let valid = edges.filter { $0.a != $0.b && $0.a >= 0 && $0.b >= 0 && $0.a < n && $0.b < n && $0.strength.isFinite }84 let usable = max((w - 2 * pad) * (h - 2 * pad), 1)85 let k = max(configuration.spread * (usable / Double(n)).squareRoot(), 1)86 let steps = max(configuration.iterations, 1)87 let t0 = min(w, h) / 888 var disp = [Point](repeating: Point(x: 0, y: 0), count: n)89 var residual = 0.09091 for step in 0..<steps {92 for i in 0..<n { disp[i] = Point(x: 0, y: 0) }93 // repulsion between every pair (n ≤ a few hundred)94 for i in 0..<(n - 1) {95 for j in (i + 1)..<n {96 var dx = pos[i].x - pos[j].x, dy = pos[i].y - pos[j].y97 var d = (dx * dx + dy * dy).squareRoot()98 if d < 1e-6 { // coincident nodes: push apart along a direction that depends only on the indices99 let a = Double((i &* 31 &+ j &* 17) % 360) * Double.pi / 180100 dx = cos(a); dy = sin(a); d = 1101 }102 let gap = max(d - r[i] - r[j], 1)103 let force = k * k / gap104 let fx = dx / d * force, fy = dy / d * force105 disp[i].x += fx; disp[i].y += fy; disp[j].x -= fx; disp[j].y -= fy106 }107 }108 // attraction along the edges109 for e in valid {110 let dx = pos[e.a].x - pos[e.b].x, dy = pos[e.a].y - pos[e.b].y111 let d = (dx * dx + dy * dy).squareRoot()112 guard d > 1e-6 else { continue }113 let gap = max(d - r[e.a] - r[e.b], 0)114 let force = gap * gap / k * min(max(e.strength, 0), 1)115 let fx = dx / d * force, fy = dy / d * force116 disp[e.a].x -= fx; disp[e.a].y -= fy; disp[e.b].x += fx; disp[e.b].y += fy117 }118 // gravity, then a move limited by the temperature (which cools to zero)119 let t = t0 * (1 - Double(step) / Double(steps))120 residual = 0121 for i in 0..<n {122 disp[i].x += (centre.x - pos[i].x) * configuration.gravity * k * 0.1123 disp[i].y += (centre.y - pos[i].y) * configuration.gravity * k * 0.1124 let len = (disp[i].x * disp[i].x + disp[i].y * disp[i].y).squareRoot()125 guard len > 1e-9, len.isFinite else { continue }126 let move = min(len, t)127 let next = clamp(Point(x: pos[i].x + disp[i].x / len * move, y: pos[i].y + disp[i].y / len * move), i)128 residual = max(residual, abs(next.x - pos[i].x), abs(next.y - pos[i].y))129 pos[i] = next130 }131 }132 return Result(positions: pos, residual: residual, iterations: steps)133 }134}135