Repository Public
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