SPB Git

Repository Public

ForceLayout.swift 6.7 KB 135 lines swift

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
Files main
Menu

Theme