Skip to content

Open-source LLM knowledge platform: turn raw documents into a queryable RAG, an autonomous reasoning agent, and a self-maintaining Wiki.

28.2 KB
Raw Blame
// Geometry is independent of SVG so dense and disconnected graphs can be
// exercised without a browser. Coordinates are world units, not screen pixels.
export interface GraphPoint { x: number; y: number }
export interface GraphLink { source: string; target: string }
export interface LayoutInput { slug: string; link_count: number; page_type?: string; title?: string }
export interface GraphBounds { left: number; top: number; right: number; bottom: number }
export interface LayoutPlacement extends GraphPoint {
  center: GraphPoint
  stationary?: boolean
  degree?: number
}
export interface GraphCluster extends GraphPoint, GraphBounds {
  slugs: string[]
  representative: string
  anchors: string[]
}
export interface GraphSection extends GraphBounds {
  kind: 'unlinked' | 'offscreen'
  count: number
}

export function graphNodeRadius(linkCount: number): number {
  // Square-root scaling keeps leaves small so hubs read as landmarks.
  return Math.max(5, Math.min(20, 4 + Math.sqrt(Math.max(0, linkCount)) * 1.8))
}

/** Deterministic multi-level Louvain over an undirected, unweighted graph.
 * Returns a community index per node; callers must pass nodes in a stable
 * order because ties are resolved by index.
 */
export function graphCommunities(neighbors: readonly (readonly number[])[]): number[] {
  const n = neighbors.length
  let membership = Array.from({ length: n }, (_, i) => i)
  // Level graph: weighted adjacency between super-nodes plus the weight of
  // edges already collapsed inside each super-node.
  let weights: Map<number, number>[] = neighbors.map(list => {
    const row = new Map<number, number>()
    for (const j of list) row.set(j, (row.get(j) ?? 0) + 1)
    return row
  })
  let inner = new Array<number>(n).fill(0)
  for (;;) {
    const size = weights.length
    const degree = weights.map((row, i) => [...row.values()].reduce((sum, w) => sum + w, 0) + 2 * inner[i]!)
    const total = degree.reduce((sum, d) => sum + d, 0)
    if (!total) break
    const community = Array.from({ length: size }, (_, i) => i)
    const tot = [...degree]
    let movedAny = false
    for (let pass = 0; pass < 32; pass++) {
      let moved = false
      for (let i = 0; i < size; i++) {
        const own = community[i]!
        const links = new Map<number, number>()
        for (const [j, w] of weights[i]!) links.set(community[j]!, (links.get(community[j]!) ?? 0) + w)
        tot[own] -= degree[i]!
        let best = own, bestGain = (links.get(own) ?? 0) - tot[own]! * degree[i]! / total
        for (const c of [...links.keys()].sort((a, b) => a - b)) {
          const gain = links.get(c)! - tot[c]! * degree[i]! / total
          if (gain > bestGain + 1e-9) { best = c; bestGain = gain }
        }
        tot[best] += degree[i]!
        if (best !== own) { community[i] = best; moved = true; movedAny = true }
      }
      if (!moved) break
    }
    if (!movedAny) break
    const renumber = new Map<number, number>()
    for (const c of community) if (!renumber.has(c)) renumber.set(c, renumber.size)
    const next = Array.from({ length: renumber.size }, () => new Map<number, number>())
    const nextInner = new Array<number>(renumber.size).fill(0)
    for (let i = 0; i < size; i++) {
      const ci = renumber.get(community[i]!)!
      nextInner[ci] += inner[i]!
      for (const [j, w] of weights[i]!) {
        const cj = renumber.get(community[j]!)!
        // Each undirected edge appears in both rows; count it once inside.
        if (ci === cj) nextInner[ci] += w / 2
        else next[ci]!.set(cj, (next[ci]!.get(cj) ?? 0) + w)
      }
    }
    membership = membership.map(c => renumber.get(community[c]!)!)
    weights = next; inner = nextInner
    if (renumber.size === size) break
  }
  return membership
}

/** Landmark caption text: summary pages carry their source file name. */
export function graphLandmarkTitle(title: string): string {
  const name = title.replace(/\s*-\s*Summary$/i, '')
    .replace(/\.(pdf|docx?|pptx?|xlsx?|csv|md|txt|html?|json|ya?ml|xml|png|jpe?g)$/i, '')
    .replace(/\s*[((]\d+[))]$/, '').trim()
  return name || title
}

// A summary is named after its source file, which usually names the document
// well, so it only yields near-ties to entities and concepts. Index pages are
// navigation and a poor name for a region even when they link to all of it.
const anchorTypeQuality: Record<string, number> = {
  entity: 1.15, concept: 1, synthesis: 0.8, comparison: 0.8, summary: 0.9, index: 0.2,
}

/** Name a connected component and its distinct themes.
 * The first landmark is the component's most prominent readable page, even
 * when it bridges every theme. Communities are the themes; each contributes
 * at most one landmark, chosen by its links inside the theme and how well its
 * title reads as a name. Themes mostly linked to an existing landmark, and
 * pages that repeat one, get no extra name. Later picks favor larger themes
 * far from earlier labels so names spread instead of stacking up. A component
 * built from several documents also names the page most of them share.
 */
export function selectGraphAnchors(
  slugs: string[], adjacency: ReadonlyMap<string, ReadonlySet<string>>,
  pages: ReadonlyMap<string, Pick<LayoutInput, 'page_type' | 'title'>> = new Map(),
): string[] {
  if (!slugs.length) return []
  const order = [...new Set(slugs)].sort()
  const index = new Map(order.map((slug, i) => [slug, i]))
  const neighbors = order.map(slug => [...(adjacency.get(slug) ?? [])]
    .flatMap(n => index.has(n) && n !== slug ? [index.get(n)!] : []).sort((a, b) => a - b))
  const membership = graphCommunities(neighbors)
  const groups = new Map<number, number[]>()
  membership.forEach((c, i) => { const group = groups.get(c) ?? []; group.push(i); groups.set(c, group) })

  const quality = (i: number) => {
    const page = pages.get(order[i]!)
    const title = graphLandmarkTitle(page?.title ?? '')
    // An identifier such as an arXiv file name ("2412.18925v1") has no word to read.
    const readable = /[\u4e00-\u9fff]{2}|[a-z]{3}/i.test(title) ? 1 : 0.3
    return (anchorTypeQuality[page?.page_type ?? ''] ?? 1) * (title.length > 18 ? 0.6 : 1) * readable
  }
  const best = (group: number[], score: (i: number) => number) => group.reduce((top, i) => {
    const a = score(i), b = score(top)
    return a > b + 1e-9 || (Math.abs(a - b) <= 1e-9 && neighbors[i]!.length > neighbors[top]!.length) ? i : top
  })
  // A theme is named by a page that lives in it; links elsewhere still count
  // for some prominence.
  const themes = [...groups.values()].map(group => {
    const inside = new Set(group)
    const score = (i: number) => {
      const internal = neighbors[i]!.filter(j => inside.has(j)).length
      return (internal + 0.5 * (neighbors[i]!.length - internal) + 1) * quality(i)
    }
    const ranked = [...group].sort((a, b) => score(b) - score(a) || neighbors[b]!.length - neighbors[a]!.length || a - b)
    return { size: group.length, ranked, members: inside }
  }).sort((a, b) => b.size - a.size || a.ranked[0]! - b.ranked[0]!)

  const name = best(order.map((_, i) => i), i => (neighbors[i]!.length + 1) * quality(i))
  const home = themes.find(theme => theme.members.has(name))!
  // Fragments of a theme are not themes of their own.
  const minimum = Math.max(3, themes[0]!.size * 0.3)
  const candidates = themes.filter(theme => theme !== home && theme.size >= minimum)
  // A second name for something already labeled: nearly the same
  // neighborhood (an author next to their paper) or a title that contains
  // the other ("北京市第三代社保卡" next to "第三代社保卡").
  const closed = (i: number) => new Set([i, ...neighbors[i]!])
  const normalized = (i: number) => graphLandmarkTitle(pages.get(order[i]!)?.title ?? '')
    .toLowerCase().replace(/[\s《》“”"'‘’()()·・]/g, '')
  const redundant = (i: number, chosen: number[]) => chosen.some(s => {
    const a = closed(i), b = closed(s)
    const shared = [...a].filter(x => b.has(x)).length
    if (shared / (a.size + b.size - shared) >= 0.5) return true
    const x = normalized(i), y = normalized(s)
    return !!x && !!y && (x.includes(y) || y.includes(x))
  })
  const budget = order.length < 16 ? 1 : order.length < 50 ? 2 : order.length < 100 ? 3 : order.length < 200 ? 4 : 5
  const bfs = (start: number) => {
    const distance = new Array<number>(order.length).fill(Infinity)
    distance[start] = 0
    const queue = [start]
    for (let q = 0; q < queue.length; q++) {
      for (const j of neighbors[queue[q]!]!) {
        if (distance[j] !== Infinity) continue
        distance[j] = distance[queue[q]!]! + 1; queue.push(j)
      }
    }
    return distance
  }
  // Labels count as fully separated once they are a fair share of the
  // component's diameter apart; closer than that, a larger theme still wins.
  const nearest = bfs(name)
  const far = nearest.reduce((top, d, i) => d !== Infinity && d > nearest[top]! ? i : top, name)
  const diameter = Math.max(...bfs(far).filter(Number.isFinite))
  const reach = Math.max(2, diameter / budget)
  const selected = [name]
  const open = new Set(candidates)
  while (selected.length < budget && open.size) {
    let pick: { theme: typeof candidates[number]; label: number } | undefined, bestScore = -1
    for (const theme of open) {
      // Most of the theme already hangs off an existing label (one document
      // around its subject): another name would only be a detail page.
      const covered = selected.some(s => neighbors[s]!.filter(j => theme.members.has(j)).length * 2 >= theme.size)
      const label = covered ? undefined : theme.ranked.find(i => !redundant(i, selected))
      if (label === undefined) { open.delete(theme); continue }
      const score = Math.sqrt(theme.size) * Math.min(nearest[label]!, reach) / reach
      if (score > bestScore + 1e-9 || (Math.abs(score - bestScore) <= 1e-9 && pick && nearest[label]! > nearest[pick.label]!)) {
        pick = { theme, label }; bestScore = score
      }
    }
    if (!pick) break
    open.delete(pick.theme)
    selected.push(pick.label)
    bfs(pick.label).forEach((d, i) => { nearest[i] = Math.min(nearest[i]!, d) })
  }

  // Themes mostly follow documents, so their names say which documents are
  // here but not why they belong together. A page shared by most of them
  // says that; it is added unless a label already is one.
  const documents = new Set(order.flatMap((slug, i) => pages.get(slug)?.page_type === 'summary' ? [i] : []))
  if (documents.size >= 2) {
    const spans = (i: number) => documents.has(i) ? 0 : neighbors[i]!.filter(j => documents.has(j)).length
    const needed = Math.max(2, Math.ceil(documents.size * 2 / 3))
    if (!selected.some(s => spans(s) >= needed)) {
      const weakest = Math.min(...selected.map(s => neighbors[s]!.length))
      const prominence = (i: number) => (neighbors[i]!.length + 1) * quality(i)
      const bridge = order.map((_, i) => i)
        .filter(i => spans(i) >= needed && neighbors[i]!.length >= weakest * 0.6 && !redundant(i, selected))
        .reduce<number | undefined>((top, i) => top === undefined || spans(i) > spans(top)
          || (spans(i) === spans(top) && prominence(i) > prominence(top) + 1e-9) ? i : top, undefined)
      if (bridge !== undefined) selected.push(bridge)
    }
  }
  return selected.map(i => order[i]!)
}

/** Pack connected components separately; singletons get two explicit shelves.
 * A missing visible edge is not evidence that the page has no links in the KB.
 */
export function buildGraphLayout(
  nodes: LayoutInput[], edges: GraphLink[], width: number, height: number,
  prior: ReadonlyMap<string, GraphPoint> = new Map(),
) {
  const nodeBySlug = new Map(nodes.map(n => [n.slug, n]))
  const adjacency = new Map(nodes.map(n => [n.slug, new Set<string>()]))
  for (const e of edges) {
    if (e.source === e.target || !nodeBySlug.has(e.source) || !nodeBySlug.has(e.target)) continue
    adjacency.get(e.source)!.add(e.target)
    adjacency.get(e.target)!.add(e.source)
  }
  const components: string[][] = []
  const unlinked: string[] = []
  const offscreen: string[] = []
  const visited = new Set<string>()
  for (const slug of [...nodeBySlug.keys()].sort()) {
    if (visited.has(slug)) continue
    visited.add(slug)
    if (!adjacency.get(slug)!.size) {
      ;(nodeBySlug.get(slug)!.link_count > 0 ? offscreen : unlinked).push(slug)
      continue
    }
    const component = [slug]
    for (let i = 0; i < component.length; i++) {
      for (const neighbor of adjacency.get(component[i]!)!) {
        if (visited.has(neighbor)) continue
        visited.add(neighbor)
        component.push(neighbor)
      }
    }
    components.push(component.sort())
  }
  components.sort((a, b) => b.length - a.length || (a[0]! < b[0]! ? -1 : 1))

  // Reserve space from each component's topology, not a circular boundary.
  // These envelopes only place groups initially; the simulation never clips
  // nodes to them or pulls individual nodes towards a common center.
  const aspect = Math.min(1.8, Math.max(0.8, width / Math.max(height, 1)))
  const stretch = Math.sqrt(aspect)
  const goldenAngle = Math.PI * (3 - Math.sqrt(5))
  const clusters: GraphCluster[] = []
  const seeds = new Map<string, GraphPoint>()
  const cellSize = 500
  const cells = new Map<string, GraphCluster[]>()
  const keysFor = (bounds: GraphBounds) => {
    const keys: string[] = []
    for (let gx = Math.floor(bounds.left / cellSize); gx <= Math.floor(bounds.right / cellSize); gx++) {
      for (let gy = Math.floor(bounds.top / cellSize); gy <= Math.floor(bounds.bottom / cellSize); gy++) keys.push(`${gx},${gy}`)
    }
    return keys
  }
  for (const slugs of components) {
    const representative = [...slugs].sort((a, b) => adjacency.get(b)!.size - adjacency.get(a)!.size || (a < b ? -1 : 1))[0]!
    // Seed a spanning tree from the best-connected page. Branches follow
    // their parent direction, so chains and trees are not born as disks.
    const local = new Map<string, GraphPoint & { heading: number }>()
    local.set(representative, { x: 0, y: 0, heading: 0 })
    const queue = [representative]
    for (let cursor = 0; cursor < queue.length; cursor++) {
      const parentSlug = queue[cursor]!
      const parent = local.get(parentSlug)!
      const children = [...adjacency.get(parentSlug)!].filter(slug => !local.has(slug)).sort()
      children.forEach((slug, i) => {
        const heading = parent.heading + (cursor === 0 ? i * goldenAngle : ((i + 0.5) / children.length - 0.5) * Math.PI * 0.8)
        const distance = 150 + (children.length > 6 ? Math.sqrt(i) * 30 : (i % 3) * 12)
        local.set(slug, { x: parent.x + Math.cos(heading) * distance, y: parent.y + Math.sin(heading) * distance, heading })
        queue.push(slug)
      })
    }
    const mean = { x: 0, y: 0 }
    for (const point of local.values()) { mean.x += point.x / local.size; mean.y += point.y / local.size }
    for (const [slug, point] of local) seeds.set(slug, { x: point.x - mean.x, y: point.y - mean.y })
    const extent = graphPointBounds(slugs.map(slug => seeds.get(slug)!))
    // Room for repulsion and the caption; this is spacing, not a force limit.
    const padding = 160
    let x = 0, y = 0, bounds: GraphBounds
    for (let attempt = 0; ; attempt++) {
      const distance = Math.sqrt(attempt) * 48
      x = Math.cos(attempt * goldenAngle) * distance * stretch
      y = Math.sin(attempt * goldenAngle) * distance / stretch
      bounds = { left: x + extent.left - padding, right: x + extent.right + padding,
        top: y + extent.top - padding, bottom: y + extent.bottom + padding }
      const neighbors = new Set(keysFor(bounds).flatMap(key => cells.get(key) ?? []))
      if ([...neighbors].every(c => bounds.right <= c.left || bounds.left >= c.right || bounds.bottom <= c.top || bounds.top >= c.bottom)) break
    }
    const cluster = { x, y, ...bounds, slugs, representative, anchors: selectGraphAnchors(slugs, adjacency, nodeBySlug) }
    clusters.push(cluster)
    for (const key of keysFor(bounds)) {
      const bucket = cells.get(key) ?? []
      bucket.push(cluster); cells.set(key, bucket)
    }
  }
  const left = Math.min(0, ...clusters.map(c => c.left))
  const top = Math.min(0, ...clusters.map(c => c.top))
  const placements = new Map<string, LayoutPlacement>()
  const sections: GraphSection[] = []
  let right = 0, bottom = 0
  for (const cluster of clusters) {
    cluster.x -= left; cluster.y -= top
    cluster.left -= left; cluster.right -= left; cluster.top -= top; cluster.bottom -= top
    const center = { x: cluster.x, y: cluster.y }
    for (const slug of cluster.slugs) {
      const point = seeds.get(slug)!
      placements.set(slug, { x: center.x + point.x, y: center.y + point.y,
        center, degree: adjacency.get(slug)!.size })
    }
    right = Math.max(right, cluster.right)
    bottom = Math.max(bottom, cluster.bottom)
  }
  const gap = 80
  // Independent pages stay on a readable grid rather than accumulating at a
  // shared force center. The shelves are not semantic clusters.
  for (const [kind, slugs] of [['offscreen', offscreen], ['unlinked', unlinked]] as const) {
    if (!slugs.length) continue
    const shelfWidth = right || Math.sqrt(slugs.length * 180 * 100 * aspect)
    const columns = Math.min(slugs.length, Math.max(3, Math.floor(shelfWidth / 180)))
    const top = bottom ? bottom + gap : 0
    const sectionWidth = columns * 180
    const sectionHeight = Math.ceil(slugs.length / columns) * 100 + 50
    const left = Math.max(0, (right - sectionWidth) / 2)
    slugs.forEach((slug, i) => {
      const point = { x: left + (i % columns) * 180 + 90, y: top + 70 + Math.floor(i / columns) * 100 }
      placements.set(slug, { ...point, center: point, stationary: true })
    })
    sections.push({ kind, count: slugs.length, left, top, right: left + sectionWidth, bottom: top + sectionHeight })
    bottom = top + sectionHeight
    right = Math.max(right, left + sectionWidth)
  }

  const dx = (width - right) / 2, dy = (height - bottom) / 2
  for (const placement of placements.values()) {
    placement.x += dx; placement.y += dy
    // Centers are shared by a component; translate them only once below.
  }
  for (const center of new Set([...placements.values()].map(p => p.center))) { center.x += dx; center.y += dy }
  for (const cluster of clusters) {
    cluster.x += dx; cluster.y += dy
    cluster.left += dx; cluster.right += dx; cluster.top += dy; cluster.bottom += dy
  }
  for (const section of sections) {
    section.left += dx; section.right += dx; section.top += dy; section.bottom += dy
  }

  // During expansion, keep the existing mental map. New nodes start near an
  // already visible neighbor; old nodes are held still by the simulation.
  if (prior.size) {
    for (const slugs of components) {
      const existing = slugs.flatMap(slug => prior.has(slug) ? [prior.get(slug)!] : [])
      if (!existing.length) continue
      const center = { x: existing.reduce((sum, p) => sum + p.x, 0) / existing.length, y: existing.reduce((sum, p) => sum + p.y, 0) / existing.length }
      slugs.forEach((slug, i) => {
        const neighbor = [...adjacency.get(slug)!].find(nb => prior.has(nb))
        const anchor = prior.get(slug) ?? (neighbor ? prior.get(neighbor)! : center)
        const angle = i * Math.PI * (3 - Math.sqrt(5))
        const point = prior.has(slug) ? anchor : { x: anchor.x + Math.cos(angle) * 90, y: anchor.y + Math.sin(angle) * 90 }
        placements.set(slug, { ...point, center, degree: adjacency.get(slug)!.size })
      })
    }
    for (const [slug, point] of prior) {
      const placement = placements.get(slug)
      if (placement) { placement.x = point.x; placement.y = point.y }
    }
  }
  return { placements, sections: prior.size ? [] : sections, clusters: prior.size ? [] : clusters }
}

export interface ForceNode extends GraphPoint {
  slug: string; vx: number; vy: number; linkCount: number; pinned: boolean
}

/** Local repulsion uses a 2D spatial grid; collision includes outer rings. */
export function stepGraphLayout(
  nodes: ForceNode[], edges: GraphLink[], placements: ReadonlyMap<string, LayoutPlacement>,
  alpha: number, retained: ReadonlySet<string> = new Set(),
) {
  const fixed = (n: ForceNode) => n.pinned || retained.has(n.slug) || !!placements.get(n.slug)?.stationary
  if (nodes.every(fixed)) return
  const reach = 300
  const buckets = new Map<string, ForceNode[]>()
  const nodeMap = new Map(nodes.map(n => [n.slug, n]))
  for (const n of nodes) {
    const cx = Math.floor(n.x / reach), cy = Math.floor(n.y / reach)
    for (let gx = cx - 1; gx <= cx + 1; gx++) for (let gy = cy - 1; gy <= cy + 1; gy++) {
      for (const other of buckets.get(`${gx},${gy}`) ?? []) {
        let dx = n.x - other.x, dy = n.y - other.y
        let distance = Math.hypot(dx, dy)
        if (distance > reach) continue
        if (distance < 0.001) { dx = 1; dy = 0; distance = 1 }
        const force = 12000 * alpha / Math.max(distance * distance, 100)
        const fx = dx / distance * force, fy = dy / distance * force
        if (!fixed(n)) { n.vx += fx; n.vy += fy }
        if (!fixed(other)) { other.vx -= fx; other.vy -= fy }
      }
    }
    const key = `${cx},${cy}`
    const bucket = buckets.get(key) ?? []
    bucket.push(n); buckets.set(key, bucket)
  }
  // A reciprocal Wiki link is one visual spring, not double attraction.
  const pairs = new Set<string>()
  for (const edge of edges) {
    const s = nodeMap.get(edge.source), t = nodeMap.get(edge.target)
    if (!s || !t || s === t) continue
    const key = JSON.stringify([s.slug, t.slug].sort())
    if (pairs.has(key)) continue
    pairs.add(key)
    const dx = t.x - s.x, dy = t.y - s.y, distance = Math.hypot(dx, dy) || 1
    // Dense pages should not pull a whole group into a solid ball. Normalize
    // attraction by the visible degrees rather than the KB-wide link count.
    const degree = Math.min(placements.get(s.slug)?.degree ?? 1, placements.get(t.slug)?.degree ?? 1)
    const force = (distance - 140) * 0.003 * alpha / Math.sqrt(Math.max(1, degree))
    if (!fixed(s)) { s.vx += dx / distance * force; s.vy += dy / distance * force }
    if (!fixed(t)) { t.vx -= dx / distance * force; t.vy -= dy / distance * force }
  }
  for (const n of nodes) {
    if (fixed(n)) continue
    n.vx *= 0.6
    n.vy *= 0.6
    const speed = Math.hypot(n.vx, n.vy)
    if (speed > 20) { n.vx *= 20 / speed; n.vy *= 20 / speed }
    n.x += n.vx; n.y += n.vy
  }
  // Resolve overlaps after integration, even when the force has cooled. Use
  // X pruning here since the collision radius is small (at most 64 units).
  for (let pass = 0; pass < 3; pass++) {
    const sorted = [...nodes].sort((a, b) => a.x - b.x)
    for (let i = 0; i < sorted.length; i++) {
      const a = sorted[i]!
      for (let j = i + 1; j < sorted.length; j++) {
        const b = sorted[j]!
        if (b.x - a.x > 64) break
        let dx = b.x - a.x, dy = b.y - a.y
        let distance = Math.hypot(dx, dy)
        const minimum = graphNodeRadius(a.linkCount) + graphNodeRadius(b.linkCount) + 16
        if (distance >= minimum || (fixed(a) && fixed(b))) continue
        if (distance < 0.001) { dx = 1; dy = 0; distance = 1 }
        const shift = (minimum - distance) / (fixed(a) || fixed(b) ? 1 : 2)
        if (!fixed(a)) { a.x -= dx / distance * shift; a.y -= dy / distance * shift }
        if (!fixed(b)) { b.x += dx / distance * shift; b.y += dy / distance * shift }
      }
    }
  }
  // Correct only whole-component drift. The same translation is applied to
  // every member; no node is attracted to a shared center or clipped to a
  // circle. Pinned/retained components keep their user's coordinates intact.
  const groups = new Map<GraphPoint, ForceNode[]>()
  for (const node of nodes) {
    const center = placements.get(node.slug)?.center
    if (!center) continue
    const group = groups.get(center) ?? []
    group.push(node); groups.set(center, group)
  }
  for (const [center, group] of groups) {
    if (group.some(fixed)) continue
    const dx = (center.x - group.reduce((sum, n) => sum + n.x, 0) / group.length) * 0.03 * alpha
    const dy = (center.y - group.reduce((sum, n) => sum + n.y, 0) / group.length) * 0.03 * alpha
    for (const n of group) { n.x += dx; n.y += dy }
  }
}

export interface GraphLabel extends GraphBounds { slug: string; priority: number; required?: boolean }
/** Greedy screen-space label placement. Focused labels are never suppressed. */
export function visibleGraphLabels(labels: GraphLabel[]): Set<string> {
  const visible = new Set<string>()
  const occupied = new Map<string, GraphLabel[]>()
  const cells = (label: GraphLabel) => {
    const keys: string[] = []
    for (let x = Math.floor(label.left / 160); x <= Math.floor(label.right / 160); x++) {
      for (let y = Math.floor(label.top / 32); y <= Math.floor(label.bottom / 32); y++) keys.push(`${x},${y}`)
    }
    return keys
  }
  for (const label of [...labels].sort((a, b) => Number(!!b.required) - Number(!!a.required) || b.priority - a.priority)) {
    const keys = cells(label)
    const overlaps = keys.some(key => (occupied.get(key) ?? []).some(other => label.left < other.right && label.right > other.left && label.top < other.bottom && label.bottom > other.top))
    if (overlaps && !label.required) continue
    visible.add(label.slug)
    for (const key of keys) {
      const bucket = occupied.get(key) ?? []
      bucket.push(label); occupied.set(key, bucket)
    }
  }
  return visible
}


export function graphPointBounds(points: GraphPoint[]): GraphBounds {
  if (!points.length) return { left: 0, top: 0, right: 0, bottom: 0 }
  return {
    left: Math.min(...points.map(p => p.x)), right: Math.max(...points.map(p => p.x)),
    top: Math.min(...points.map(p => p.y)), bottom: Math.max(...points.map(p => p.y)),
  }
}

/** Start at a readable scale. Fitting the entire graph is an explicit action. */
export function initialGraphViewport(points: GraphPoint[], width: number, height: number, focus?: GraphPoint) {
  const bounds = graphPointBounds(points)
  const fit = Math.min(Math.max(100, width - 120) / Math.max(100, bounds.right - bounds.left),
    Math.max(100, height - 120) / Math.max(100, bounds.bottom - bounds.top))
  const scale = Math.max(0.4, Math.min(0.85, fit))
  const center = fit < 0.4 && focus ? focus : { x: (bounds.left + bounds.right) / 2, y: (bounds.top + bounds.bottom) / 2 }
  return { scale, x: width / 2 - center.x * scale, y: height / 2 - center.y * scale }
}


/** Smooth envelope of the node disks with a stable screen-space gutter.
 * The hull is taken over disks already grown by the gutter, then traced with
 * a closed spline whose tangents are limited by the adjacent segment length,
 * so it bows outwards from the hull without loops or cusps.
 */
export function graphClusterOutline(points: (GraphPoint & { radius?: number })[], scale = 1): string {
  if (!points.length) return ''
  const zoom = Number.isFinite(scale) && scale > 0 ? scale : 1
  // Capped in world units so far-out zoom levels do not merge separate groups.
  const padding = Math.min(22 / zoom, 60)
  const samples = 24
  const expanded = points.flatMap(p => {
    const radius = Math.max(0, p.radius ?? 0) + padding
    return Array.from({ length: samples }, (_, i) => ({
      x: p.x + Math.cos(i * 2 * Math.PI / samples) * radius,
      y: p.y + Math.sin(i * 2 * Math.PI / samples) * radius,
    }))
  }).sort((a, b) => a.x - b.x || a.y - b.y)
  const unique = expanded.filter((p, i) => !i || p.x !== expanded[i - 1]!.x || p.y !== expanded[i - 1]!.y)
  const cross = (o: GraphPoint, a: GraphPoint, b: GraphPoint) => (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
  const half = (list: GraphPoint[]) => {
    const hull: GraphPoint[] = []
    for (const point of list) {
      while (hull.length > 1 && cross(hull[hull.length - 2]!, hull[hull.length - 1]!, point) <= 0) hull.pop()
      hull.push(point)
    }
    hull.pop()
    return hull
  }
  const hull = [...half(unique), ...half([...unique].reverse())]
  const at = (i: number) => hull[(i + hull.length) % hull.length]!
  const fmt = (p: GraphPoint) => `${Math.round(p.x * 10) / 10},${Math.round(p.y * 10) / 10}`
  const tangent = (from: GraphPoint, to: GraphPoint, length: number) => {
    const dx = to.x - from.x, dy = to.y - from.y, norm = Math.hypot(dx, dy) || 1
    return { x: dx / norm * length, y: dy / norm * length }
  }
  const path = [`M${fmt(hull[0]!)}`]
  hull.forEach((p, i) => {
    const next = at(i + 1)
    const reach = Math.hypot(next.x - p.x, next.y - p.y) * 0.36
    const out = tangent(at(i - 1), next, reach), into = tangent(p, at(i + 2), reach)
    path.push(`C${fmt({ x: p.x + out.x, y: p.y + out.y })} ${fmt({ x: next.x - into.x, y: next.y - into.y })} ${fmt(next)}`)
  })
  return path.join(' ') + ' Z'
}