SPB Git

Repository Public

GraphLayout.swift 10.4 KB 232 lines swift

1// SP Notes Core2// File: Sources/SPNotesFeatures/Knowledge/GraphLayout.swift3// Description: Pure geometry of the knowledge graph: a deterministic (seeded) force-directed layout that runs off the4//              main actor, and the viewport (pan / zoom / fit / hit testing) the screen applies to it. No UI.5//6// Author: Simon-Pierre Boucher7// Contact: contact@spboucher.ai8import CoreGraphics9import Foundation1011/// SplitMix64: a small deterministic generator (the same seed gives the same layout on every device).12struct GraphRandom: Sendable {13    private var state: UInt6414    init(seed: UInt64) { state = seed &+ 0x9E37_79B9_7F4A_7C15 }1516    mutating func next() -> UInt64 {17        state &+= 0x9E37_79B9_7F4A_7C1518        var z = state19        z = (z ^ (z >> 30)) &* 0xBF58_476D_1CE4_E5B920        z = (z ^ (z >> 27)) &* 0x94D0_49BB_1331_11EB21        return z ^ (z >> 31)22    }2324    /// Uniform in 0 ..< 1.25    mutating func unit() -> Double { Double(next() >> 11) / Double(1 << 53) }26}2728/// Force-directed layout (Fruchterman–Reingold with a linear cooling schedule and a gravity term so that disconnected29/// parts stay in view). Positions are normalised to the unit box `-1 ... 1` on both axes.30public enum GraphForceLayout {31    public struct Options: Sendable, Equatable {32        public var iterations: Int33        public var seed: UInt6434        public var gravity: Double35        /// Strength of the springs relative to the repulsion (lower = airier clusters).36        public var attraction: Double37        public init(iterations: Int = 260, seed: UInt64 = 20_261_119, gravity: Double = 0.035, attraction: Double = 0.4) {38            self.iterations = iterations39            self.seed = seed40            self.gravity = gravity41            self.attraction = attraction42        }43    }4445    /// A stable seed from the ids, so that the same graph always gets the same picture.46    public static func seed(for ids: [String]) -> UInt64 {47        var hash: UInt64 = 0xCBF2_9CE4_8422_232548        for id in ids.sorted() {49            for byte in id.utf8 { hash = (hash ^ UInt64(byte)) &* 0x0000_0100_0000_01B3 }50        }51        return hash52    }5354    /// - Parameters:55    ///   - nodes: node ids (duplicates are ignored after the first).56    ///   - edges: pairs of node ids; unknown ids and self-loops are ignored.57    /// - Returns: one point per node id, in `-1 ... 1`.58    public static func layout(nodes: [String], edges: [(String, String)], options: Options = Options()) -> [String: CGPoint] {59        var index: [String: Int] = [:]60        var ids: [String] = []61        for id in nodes where index[id] == nil {62            index[id] = ids.count63            ids.append(id)64        }65        let count = ids.count66        guard count > 0 else { return [:] }67        guard count > 1 else { return [ids[0]: .zero] }6869        var pairs: [(Int, Int)] = []70        var seen = Set<UInt64>()71        for (a, b) in edges {72            guard let i = index[a], let j = index[b], i != j else { continue }73            let key = UInt64(min(i, j)) << 32 | UInt64(max(i, j))74            if seen.insert(key).inserted { pairs.append((i, j)) }75        }7677        var random = GraphRandom(seed: options.seed)78        var x = [Double](repeating: 0, count: count), y = [Double](repeating: 0, count: count)79        // Start on a jittered circle: no two nodes at the same place, whatever the seed.80        for i in 0 ..< count {81            let angle = 2 * Double.pi * Double(i) / Double(count)82            let radius = 0.6 + 0.3 * random.unit()83            x[i] = cos(angle) * radius + (random.unit() - 0.5) * 0.0584            y[i] = sin(angle) * radius + (random.unit() - 0.5) * 0.0585        }8687        let area = 4.088        let k = sqrt(area / Double(count))89        var temperature = 0.2590        let cooling = temperature / Double(max(1, options.iterations))91        var dx = [Double](repeating: 0, count: count), dy = [Double](repeating: 0, count: count)9293        for _ in 0 ..< max(0, options.iterations) {94            for i in 0 ..< count { dx[i] = 0; dy[i] = 0 }95            for i in 0 ..< count {96                for j in (i + 1) ..< count {97                    var vx = x[i] - x[j], vy = y[i] - y[j]98                    var distance = (vx * vx + vy * vy).squareRoot()99                    if distance < 1e-6 {100                        // Coincident points: push apart along a deterministic direction.101                        vx = 1e-3 * Double((i &+ 1) % 7 + 1)102                        vy = 1e-3 * Double((j &+ 3) % 5 + 1)103                        distance = (vx * vx + vy * vy).squareRoot()104                    }105                    let force = k * k / distance106                    let fx = vx / distance * force, fy = vy / distance * force107                    dx[i] += fx; dy[i] += fy108                    dx[j] -= fx; dy[j] -= fy109                }110            }111            for (i, j) in pairs {112                let vx = x[i] - x[j], vy = y[i] - y[j]113                let distance = max(1e-6, (vx * vx + vy * vy).squareRoot())114                let force = distance * distance / k * options.attraction115                let fx = vx / distance * force, fy = vy / distance * force116                dx[i] -= fx; dy[i] -= fy117                dx[j] += fx; dy[j] += fy118            }119            for i in 0 ..< count {120                dx[i] -= x[i] * options.gravity * Double(count).squareRoot()121                dy[i] -= y[i] * options.gravity * Double(count).squareRoot()122                let length = max(1e-9, (dx[i] * dx[i] + dy[i] * dy[i]).squareRoot())123                let step = min(length, temperature)124                x[i] += dx[i] / length * step125                y[i] += dy[i] / length * step126            }127            temperature = max(0.002, temperature - cooling)128        }129130        // Normalise to the unit box, keeping the aspect ratio.131        let minX = x.min() ?? 0, maxX = x.max() ?? 0, minY = y.min() ?? 0, maxY = y.max() ?? 0132        let span = max(maxX - minX, maxY - minY, 1e-9)133        let cx = (minX + maxX) / 2, cy = (minY + maxY) / 2134        var result: [String: CGPoint] = [:]135        for i in 0 ..< count {136            let px = (x[i] - cx) / span * 2, py = (y[i] - cy) / span * 2137            result[ids[i]] = CGPoint(x: px.isFinite ? px : 0, y: py.isFinite ? py : 0)138        }139        return result140    }141142    /// The same computation away from the caller's actor.143    public static func layoutInBackground(nodes: [String], edges: [(String, String)], options: Options = Options()) async -> [String: CGPoint] {144        let pairs = edges.map { [$0.0, $0.1] }145        return await Task.detached(priority: .userInitiated) {146            layout(nodes: nodes, edges: pairs.map { ($0[0], $0[1]) }, options: options)147        }.value148    }149150    /// Mean edge length minus mean distance of all pairs: negative when linked nodes are closer than unlinked ones151    /// (what a converged layout must show). Exposed for tests.152    public static func cohesion(_ positions: [String: CGPoint], edges: [(String, String)]) -> Double {153        func distance(_ a: CGPoint, _ b: CGPoint) -> Double { Double(hypot(a.x - b.x, a.y - b.y)) }154        let linked = edges.compactMap { edge -> Double? in155            guard let a = positions[edge.0], let b = positions[edge.1] else { return nil }156            return distance(a, b)157        }158        let all = Array(positions.values)159        var total = 0.0, pairs = 0.0160        for i in 0 ..< all.count { for j in (i + 1) ..< all.count { total += distance(all[i], all[j]); pairs += 1 } }161        guard !linked.isEmpty, pairs > 0 else { return 0 }162        return linked.reduce(0, +) / Double(linked.count) - total / pairs163    }164}165166/// Pan and zoom of a unit-box layout inside a view. `scale` 1 = the layout fits the view with a margin.167public struct GraphViewport: Sendable, Equatable {168    public static let minScale: CGFloat = 0.4169    public static let maxScale: CGFloat = 6170171    /// Translation in view points.172    public var offset: CGSize173    public var scale: CGFloat174175    public init(offset: CGSize = .zero, scale: CGFloat = 1) {176        self.offset = offset177        self.scale = scale178    }179180    /// Half of the side of the square the unit box maps to at scale 1.181    public static func baseRadius(in size: CGSize, margin: CGFloat = 36) -> CGFloat {182        max(10, min(size.width, size.height) / 2 - margin)183    }184185    /// Unit-box point → view point.186    public func toView(_ point: CGPoint, in size: CGSize) -> CGPoint {187        let radius = Self.baseRadius(in: size) * scale188        return CGPoint(x: size.width / 2 + offset.width + point.x * radius, y: size.height / 2 + offset.height + point.y * radius)189    }190191    /// View point → unit-box point.192    public func toWorld(_ point: CGPoint, in size: CGSize) -> CGPoint {193        let radius = Self.baseRadius(in: size) * scale194        return CGPoint(x: (point.x - size.width / 2 - offset.width) / radius, y: (point.y - size.height / 2 - offset.height) / radius)195    }196197    public mutating func pan(by translation: CGSize) {198        offset.width += translation.width199        offset.height += translation.height200    }201202    /// Multiplies the zoom, keeping the world point under `anchor` (a view point) where it is.203    public mutating func zoom(by factor: CGFloat, anchor: CGPoint, in size: CGSize) {204        guard factor.isFinite, factor > 0 else { return }205        let world = toWorld(anchor, in: size)206        scale = min(Self.maxScale, max(Self.minScale, scale * factor))207        let moved = toView(world, in: size)208        offset.width += anchor.x - moved.x209        offset.height += anchor.y - moved.y210    }211212    public mutating func reset() { self = GraphViewport() }213214    /// Centres the view on a world point without changing the zoom.215    public mutating func center(on world: CGPoint, in size: CGSize) {216        let radius = Self.baseRadius(in: size) * scale217        offset = CGSize(width: -world.x * radius, height: -world.y * radius)218    }219220    /// The id of the nearest point within `tolerance` view points of `location`, nil when none.221    public func hitTest(_ location: CGPoint, positions: [String: CGPoint], in size: CGSize, tolerance: CGFloat = 22) -> String? {222        var best: (id: String, distance: CGFloat)?223        for (id, world) in positions {224            let p = toView(world, in: size)225            let distance = hypot(p.x - location.x, p.y - location.y)226            guard distance <= tolerance else { continue }227            if best == nil || distance < best!.distance || (distance == best!.distance && id < best!.id) { best = (id, distance) }228        }229        return best?.id230    }231}232
Files main
Menu

Theme