SPB Git

Repository Public

ForceLayout.swift 7.4 KB 160 lines swift

1//2//  SP Chat iOS3//  File: SPChat-iOS/Features/Constellation/ForceLayout.swift4//  Description: A small deterministic force-directed layout (repulsion, springs, centring) for the Conversation5//               Constellation. A pure value type: it runs off the main thread and is tested without any view.6//7//  Author: Simon-Pierre Boucher8//  Contact: contact@spboucher.ai9//1011import CoreGraphics12import Foundation1314struct ForceLayout: Sendable, Equatable {15    struct Edge: Sendable, Equatable {16        var a: Int17        var b: Int18        /// Rest length of the spring, in layout points.19        var length: Double20        /// 0…1: how hard the spring pulls.21        var strength: Double22    }2324    private(set) var x: [Double]25    private(set) var y: [Double]26    private var vx: [Double]27    private var vy: [Double]28    let edges: [Edge]29    /// Nodes held in place (being dragged).30    var pinned: Set<Int> = []31    /// Simulation temperature: forces are scaled by it and it cools at every step; the layout is settled below `minAlpha`.32    private(set) var alpha: Double33    static let minAlpha = 0.01234    private let repulsion: Double35    private let decay = 0.97236    /// Pull toward the centre on each axis: a tall canvas pulls harder sideways, so the graph grows along the screen.37    private let gravityX: Double38    private let gravityY: Double3940    var count: Int { x.count }41    var isSettled: Bool { alpha < Self.minAlpha || count < 2 }42    var positions: [CGPoint] { zip(x, y).map { CGPoint(x: $0, y: $1) } }4344    /// `seed` makes the initial placement reproducible: the same graph always settles in the same shape.45    init(count: Int, edges: [Edge], seed: UInt64 = 0x5EED_C0DE, spacing: Double = 90, aspect: Double = 1) {46        (gravityX, gravityY) = Self.gravity(aspect: aspect)47        var rng = SplitMix64(state: seed)48        var xs = [Double](repeating: 0, count: count), ys = xs49        // a sunflower spiral with a little jitter: no two nodes start at the same place, nothing starts aligned50        for i in 0..<count {51            let r = spacing * 0.55 * (Double(i) + 0.5).squareRoot(), a = Double(i) * 2.39996322972865352            xs[i] = r * cos(a) + (rng.unit() - 0.5) * 653            ys[i] = r * sin(a) + (rng.unit() - 0.5) * 654        }55        x = xs; y = ys56        vx = [Double](repeating: 0, count: count); vy = vx57        self.edges = edges.filter { $0.a != $0.b && $0.a >= 0 && $0.b >= 0 && $0.a < count && $0.b < count }58        alpha = 159        repulsion = spacing * spacing * 0.960    }6162    /// Starts from given positions (a node was dragged, the data was refreshed) with a lower temperature.63    init(positions: [CGPoint], edges: [Edge], alpha: Double = 0.35, spacing: Double = 90, aspect: Double = 1) {64        (gravityX, gravityY) = Self.gravity(aspect: aspect)65        x = positions.map { Double($0.x).isFinite ? Double($0.x) : 0 }; y = positions.map { Double($0.y).isFinite ? Double($0.y) : 0 }66        vx = [Double](repeating: 0, count: positions.count); vy = vx67        let n = positions.count68        self.edges = edges.filter { $0.a != $0.b && $0.a >= 0 && $0.b >= 0 && $0.a < n && $0.b < n }69        self.alpha = alpha70        repulsion = spacing * spacing * 0.971    }7273    /// `aspect` = height / width of the canvas, clamped: 1 = square (same pull on both axes).74    private static func gravity(aspect: Double) -> (Double, Double) {75        let a = min(max(aspect.isFinite ? aspect : 1, 0.5), 2)76        return (0.012 * a.squareRoot() * (a > 1 ? a : 1), 0.012 / a.squareRoot() / (a < 1 ? a : 1))77    }7879    mutating func move(_ index: Int, to p: CGPoint) {80        guard index >= 0, index < count, p.x.isFinite, p.y.isFinite else { return }81        x[index] = Double(p.x); y[index] = Double(p.y); vx[index] = 0; vy[index] = 082    }83    mutating func reheat(_ value: Double = 0.3) { alpha = max(alpha, value) }8485    /// One iteration. O(n²) repulsion: fine for the ≤ 200 conversations the constellation shows.86    mutating func step() {87        let n = count88        guard n > 1, alpha >= Self.minAlpha else { alpha = min(alpha, Self.minAlpha * 0.5); return }89        var fx = [Double](repeating: 0, count: n), fy = fx90        for i in 0..<n {91            for j in (i + 1)..<max(i + 1, n) {92                var dx = x[i] - x[j], dy = y[i] - y[j]93                var d2 = dx * dx + dy * dy94                if d2 < 0.01 { dx = Double((i &* 31 &+ j) % 7) - 3 + 0.5; dy = Double((j &* 17 &+ i) % 5) - 2 + 0.5; d2 = dx * dx + dy * dy }   // coincident nodes: a fixed nudge, never a division by zero95                let d = d2.squareRoot()96                let f = min(repulsion / d2, 40)97                let ux = dx / d, uy = dy / d98                fx[i] += ux * f; fy[i] += uy * f; fx[j] -= ux * f; fy[j] -= uy * f99            }100            // gentle pull toward the centre keeps unlinked nodes on screen101            fx[i] -= x[i] * gravityX; fy[i] -= y[i] * gravityY102        }103        for e in edges {104            let dx = x[e.b] - x[e.a], dy = y[e.b] - y[e.a]105            let d = max((dx * dx + dy * dy).squareRoot(), 0.01)106            let f = (d - e.length) * 0.06 * max(0.05, min(e.strength, 1))107            let ux = dx / d, uy = dy / d108            fx[e.a] += ux * f; fy[e.a] += uy * f; fx[e.b] -= ux * f; fy[e.b] -= uy * f109        }110        for i in 0..<n where !pinned.contains(i) {111            vx[i] = (vx[i] + fx[i] * alpha) * 0.82; vy[i] = (vy[i] + fy[i] * alpha) * 0.82112            let speed = (vx[i] * vx[i] + vy[i] * vy[i]).squareRoot()113            if speed > 28 { vx[i] *= 28 / speed; vy[i] *= 28 / speed }114            x[i] += vx[i]; y[i] += vy[i]115        }116        alpha *= decay117    }118119    /// Runs until settled (Reduce Motion: the layout is complete before the first display).120    mutating func settle(maxIterations: Int = 600) {121        var i = 0122        while !isSettled && i < maxIterations { step(); i += 1 }123    }124125    /// Bounding box of the layout (used to fit the graph in the canvas).126    var bounds: CGRect {127        guard let minX = x.min(), let maxX = x.max(), let minY = y.min(), let maxY = y.max() else { return .zero }128        return CGRect(x: minX, y: minY, width: maxX - minX, height: maxY - minY)129    }130}131132/// Small deterministic generator (the system generator is seeded differently at every launch).133struct SplitMix64: Sendable {134    var state: UInt64135    mutating func next() -> UInt64 {136        state &+= 0x9E37_79B9_7F4A_7C15137        var z = state138        z = (z ^ (z >> 30)) &* 0xBF58_476D_1CE4_E5B9139        z = (z ^ (z >> 27)) &* 0x94D0_49BB_1331_11EB140        return z ^ (z >> 31)141    }142    mutating func unit() -> Double { Double(next() >> 11) / Double(1 << 53) }143}144145extension ForceLayout {146    /// Springs of a constellation: a branch keeps parent and child close, a project groups loosely, a topic link pulls147    /// in proportion to its similarity.148    static func edges(for graph: Constellation) -> [Edge] {149        let index = Dictionary(graph.nodes.enumerated().map { ($0.element.id, $0.offset) }, uniquingKeysWith: { a, _ in a })150        return graph.links.compactMap { l in151            guard let a = index[l.source], let b = index[l.target] else { return nil }152            switch l.kind {153            case "branch": return Edge(a: a, b: b, length: 60, strength: 1)154            case "project": return Edge(a: a, b: b, length: 85, strength: 0.6)155            default: return Edge(a: a, b: b, length: 150 - 70 * min(max(l.weight, 0), 1), strength: 0.25 + 0.5 * min(max(l.weight, 0), 1))156            }157        }158    }159}160
Files main
Menu

Theme