# PLAN — Brief 01: Graph Explorer

A force-directed graph explorer for **5,000 nodes / ~10,000 edges** that sustains ≥30 fps
(target 60). Vanilla **Vite + TypeScript + Vitest**, **zero runtime dependencies**, rendered to
Canvas 2D. Hand-rolled Barnes–Hut layout over typed arrays.

## Why zero runtime dependencies

The rubric pays directly for small footprint: gzipped bundle `60 KB → 10`, build time `≤10 s → 10`,
heap `60 MB → 10`. A library like `d3-force` (Barnes–Hut layout) or `pixi.js` (WebGL) would balloon
all three for capabilities I can implement tightly in a few hundred lines. So I build:

- the **layout** (Barnes–Hut quadtree force approximation) myself, over `Float32Array`s with a
  **pooled** tree (no per-frame allocation → flat heap, good GC behaviour = F11);
- the **renderer** on Canvas 2D with **batched draw calls** (one `Path2D` per group colour, one
  `stroke()` for all edges) so it stays cheap even under headless software rendering.

The only dev-time deps are the toolchain the contract mandates (vite, typescript, vitest, eslint +
the shared config's two plugins, prettier).

## Architecture — strict sim / render / UI separation (A3)

```
index.html              # canvas + UI shell
src/
  style.css
  main.ts               # composition root: wire modules, RAF loop, expose window.__buildoff
  lib/
    graph-core.ts       # REQUIRED contract (pure): types, neighbors, searchNodes,
                         #   filterByGroup, QuadTree (range-query spatial index). No DOM.
    graph-generator.ts  # pure: synthesize a clustered/community graph (seeded LCG)
  sim/
    barnes-hut.ts       # pooled Barnes–Hut quadtree → O(n log n) repulsion (typed arrays)
    simulation.ts       # force model: repulsion(BH) + spring + centering; Verlet + alpha decay
  render/
    camera.ts           # world<->screen transform (pure, unit-tested), pan + zoom math
    renderer.ts         # Canvas 2D batched draw (nodes by colour, edges in one path)
  ui/
    interaction.ts      # pointer: pan(drag), zoom(wheel), hover/click pick (uses QuadTree)
    controls.ts         # search box, group filter, live sim sliders, stats readout
tests/                  # own Vitest suite (mirrors + extends the contract)
```

No file exceeds ~400 LOC. `graph-core.ts` is import-free of the DOM so it runs in node/jsdom.

## The acceptance contract (`src/lib/graph-core.ts`) — F9

Implemented exactly as specified:

- `neighbors(graph, id)` — build undirected adjacency, return **sorted, de-duplicated** neighbor
  ids; `[]` for unknown/isolated. (Edges are deduped; self-loops ignored.)
- `searchNodes(graph, query)` — case-insensitive substring over `label` **or** `id`; `[]` on no match.
- `filterByGroup(graph, group)` — strict `===` on `group`.
- `class QuadTree` — region quadtree with **inclusive** range queries, `capacity` default 4,
  `insert` rejects out-of-bounds (returns false), `size()` counts accepted points. Built to match a
  brute-force scan exactly (the hidden test cross-checks 2000 random points). This same structure is
  the basis for Barnes–Hut (F3).

## Force model (F2)

Per tick, over typed arrays:
1. **Repulsion** — Barnes–Hut (θ≈0.85) charge force, O(n log n) not O(n²) (F3, A4/A5).
2. **Spring** — each edge pulls its endpoints toward a target link distance (Hooke).
3. **Centering / gravity** — weak pull to canvas centre keeps the graph framed.
4. **Integrate** — velocity Verlet with velocity decay; global `alpha` cools `1 → alphaMin`
   (d3-style) so the layout visibly settles then rests.

Sliders (F12) expose repulsion strength, link distance, gravity, velocity decay live.

## Rendering & interaction (F4, F5, F8, F13)

- Canvas 2D, devicePixelRatio-aware. **Pan** = pointer drag (screen delta → world via camera),
  **zoom** = wheel anchored at cursor (correct world↔screen, round-trip unit-tested).
- Edges drawn as a single batched stroke; nodes batched into one filled path per group colour
  (community colouring = F13). Hover/click uses the QuadTree to pick the nearest node, then
  highlights it + its `neighbors()` and dims the rest (F8). Search highlights matches (F6); group
  filter dims non-matching groups (F7).

## Perf hook (F14) + honesty

`window.__buildoff = { warmup, workload }`: `warmup` builds the 5k graph and starts the layout;
`workload` runs a fixed 120 sim+render frames and returns `{nodes, edges, framesRun, avgFrameMs}`
measured with `performance.now()` — real numbers on the real workload.

## Testing (A1)

Own Vitest covers: adjacency/search/filter edge cases, QuadTree vs brute force, Barnes–Hut force
≈ brute-force O(n²) within tolerance, generator invariants (≥5000 nodes, ~10000 edges, valid
endpoints), simulation energy decreasing/convergence, and camera world↔screen round-trip.

## Risks & mitigations

- **Headless software rendering may cap FPS** → batch draw calls, keep per-frame allocation at zero,
  cool the layout so steady-state is cheap.
- **QuadTree boundary bugs** (points on shared edges) → inclusive contains + visit all intersecting
  quads; cross-checked against brute force in tests.
- **Barnes–Hut GC churn** → pooled tree nodes reset each frame (F11), `Float32Array` everywhere.
- **`any`/lint creep** (A2/A3) → strict TS, no `any`, run eslint + prettier locally against the
  shared config before finishing.