# Epic: First-party graph (drop D3, own the minimap + explorer)

**Status:** proposed (2026-06-16)
**Motivation:** D3 is overkill for the per-page minimap and *chokes* on the full
`/graph/` explorer even at the Bengal docs site's scale. D3 is currently an
opt-in `[capabilities] d3` vendor (Pridelands floor-clean #533/#550), which also
means the flagship per-page graph is **off by default**. Replacing it with a
hand-rolled, zero-dependency engine lets us (a) make the graph work by default
with no external assets, (b) scale the explorer past D3, and (c) own the feature.

---

## Design principle: push everything to build time; JS only where unavoidable

We already compute the graph **data** in Python (it's the source of truth). The
only thing the browser computes from scratch is the **x/y layout** — then it
re-derives colors, builds DOM, and wires interaction. Almost none of that needs
to be runtime JS:

| Concern | Where it belongs |
| --- | --- |
| Graph data (nodes/edges/metrics) | Build-time Python (already done) |
| **Layout (x/y positions)** | **Build-time Python, deterministic/seeded** (the key move) |
| Colors / theming | CSS custom properties (`fill: var(--graph-node-hub)`) |
| Node size | baked inline attr from the `size` we already compute |
| Current-page / hub state | CSS class baked at build |
| Click-to-navigate | `<a href>` wrapping the node (native) |
| Tooltip (label) | SVG `<title>` (native) |
| Hover highlight | CSS `:hover` + sibling selectors |
| Pan / zoom / search / filter | JS — **only** on the `/graph/` explorer page |

**Consequence: the per-page minimap becomes ZERO JavaScript.** With layout baked
at build, the minimap is a tiny inline `<svg>` rendered straight into the page
template — `<a>`-wrapped `<circle>`s with baked `cx/cy`, `<line>` edges,
`fill: var(...)` for theme-aware color, `<title>` tooltips, a CSS class for the
current page. We delete the `getComputedStyle` color resolution, the
`themechange` listeners, the `IntersectionObserver`, the runtime force sim, and
the d3-load polling entirely. Theming "just works" via the CSS cascade.

CSS cannot do graph *layout* (no force sim in CSS), so x/y must be computed —
but in Python at build, not JS in the browser. CSS owns the rest (color, size,
hover, state, transitions).

Why D3 couldn't do this: D3 is a client-side runtime library — it computes
layout in the browser by definition. Owning the feature is exactly what lets us
move layout to build time.

**Constraint:** build-time layout must be deterministic (seeded, no RNG) to keep
the warm==cold byte-parity contract. Same neighborhood in → same coordinates out.

## Diagnosis: what actually chokes

The simulation is **not** the bottleneck. D3 already uses a Barnes-Hut quadtree
for the charge force (`forceManyBody`), so layout is O(n log n). The bottleneck is
the **renderer**: `graph_visualizer.html` builds one `<circle>`/`<line>` SVG
element per node/edge and rewrites `cx/cy/x1/y1` on every tick. At thousands of
elements the browser's layout + paint per frame is what melts.

Conclusion: the leverage is **Canvas2D rendering**, not a faster sim. A single
`<canvas>` draws 10k+ nodes per frame with viewport culling; the same force math
that D3 runs becomes cheap once we stop touching the DOM per element.

---

## What we keep (no change needed)

The data pipeline is already clean and D3-agnostic:

- `GraphVisualizer.generate_graph_data()` (`bengal/analysis/graph/visualizer.py`)
  emits `nodes` (`{id,label,url,type,tags,incoming_refs,outgoing_refs,
  connectivity,reading_time,size,color}`) + `edges` (`{source,target,weight}`) +
  `stats`. Deterministic ids via `_get_page_id` (stable hash) — keep; it protects
  the byte-parity contract.
- Per-page `index.json` carries a pre-filtered neighborhood under `.graph`
  (`json_generator._get_page_connections`). The minimap reads this first, falls
  back to `/graph/graph.json`. Keep both paths.
- `graph.json` is emitted at `/graph/graph.json`; `/graph/` is generated by
  `special_pages._generate_graph` (default `enabled=True`).

Only one data tweak (optional, small): drop the `color: "var(--graph-node-…)"`
string from the payload and derive color from `type` in JS instead. Smaller JSON,
one less coupling. CSS custom properties still drive the actual palette (resolved
via `getComputedStyle`, exactly as today).

---

## Architecture: build-time layout, two very different mounts

The expensive thing (force layout) moves to **build-time Python**, shared by both
mounts. The two mounts then diverge sharply:

- **Minimap = static, zero JS.** Inline `<svg>` emitted into the page template
  from the per-page `.graph` neighborhood + baked x/y. No core JS at all.
- **Explorer = Canvas + JS, but no runtime sim.** Thousands of inline SVG DOM
  nodes is itself too heavy, so the explorer renders baked positions to a
  `<canvas>` and adds pan/zoom/search/filter. Because layout is pre-baked, there
  is no runtime force simulation to choke on.

New build-time module (Python): a small deterministic force-layout pass that
annotates nodes with `x`/`y`. Run it once over the full graph for the explorer
(positions ship in `graph.json`), and over each page's capped neighborhood for
the minimap (positions ship in `index.json`'s `.graph`). Seed deterministically.

Runtime JS shrinks to a single explorer module under
`bengal/themes/default/assets/js/`, **zero dependencies**:

```
bengal-graph-explorer.js   // Canvas2D renderer + pan/zoom + hit-test + search/filter
                           // (renders baked positions; NO force engine at runtime)
```

`graph-contextual.js` / `graph-minimap.js` are **deleted** — the minimap no
longer needs runtime code.

### Build-time layout (Python, shared)
A small force-directed layout pass that annotates each node with `x`/`y`:
- Semi-implicit Euler integration (mirror D3's feel: alpha/alphaDecay/alphaMin).
- **Charge** via a Barnes-Hut quadtree → O(n log n). The one piece worth doing
  carefully; everything else is trivial.
- **Springs** (links): Hooke along edges; **center + mild gravity**; collision
  for the minimap (≤15 nodes).
- **Deterministic:** fixed seed (or seed derived from the stable node ids) — no
  RNG — so the same neighborhood always yields the same coordinates. This is what
  lets positions ship in the output files without breaking byte parity.
- Run once over the full graph (positions → `graph.json`) and over each page's
  capped neighborhood (positions → `index.json` `.graph`). Normalize to a unit
  box so the client can scale into any viewport.

### Minimap render (zero JS — the per-page graph)
Emitted as inline `<svg>` directly into the page template from `.graph`:
- `<line>` edges + `<a href><circle></a>` nodes with baked `cx/cy` (from layout)
  and `r` (from the `size` we already compute).
- Color via `fill: var(--graph-node-hub|regular|orphan|generated)` → theme/palette
  switching is automatic through the CSS cascade. No `getComputedStyle`, no
  `themechange` listener.
- `<title>` per node for the native tooltip; a `graph-node-current` CSS class on
  the current page; hover highlight via CSS `:hover` + sibling selectors.
- Expand affordance is just `<a href="/graph/">`.
- Net deletion: force sim, color resolution, IntersectionObserver, d3-load
  polling, the whole `graph-contextual.js`/`graph-minimap.js` runtime.

### Explorer render (Canvas + JS — `bengal-graph-explorer.js`)
Renders **baked** positions; no runtime sim.
- Single `<canvas>`, `devicePixelRatio`-aware. Inline SVG is rejected here only
  because thousands of DOM nodes is too heavy — not because of layout.
- **Viewport culling + level-of-detail**: zoomed out → dots only; labels above a
  zoom threshold or for hubs. Batch draws by color.
- Pan/zoom via wheel + drag on the canvas transform (replaces `d3.zoom`).
- **Hit-testing**: nearest node within radius via a quadtree over the baked
  positions (replaces SVG `pointer-events`) → hover tooltip, highlight-neighbors,
  click-to-nav, search, filter.
- Colors resolved once via `getComputedStyle` (Canvas can't use per-element CSS),
  cached, redrawn on `themechange`/`palettechange`.

### Accessibility & fallback (new, do not skip)
- The minimap's `<a>`/`<title>` structure is already crawlable + keyboard-/AT-
  navigable — no extra work.
- The explorer's canvas is invisible to AT/crawlers: render an adjacent **real
  `<ul>` of `<a>` links** (from the same data), visually subordinate but in DOM.
- Respect `prefers-reduced-motion` (explorer): no entrance animation, static draw.

---

## Capability + wiring changes (the payoff)

Once nothing imports D3:

- Remove `d3` from `CAPABILITY_NAMES`/`VENDOR_FILES` (`capabilities/runtime.py`)
  and `VENDOR_SOURCES` (`capabilities/vendors.py`). Keep mermaid/katex/iconify.
- `base.html`: drop the `{% if bengal?.capabilities?.d3 %}` lazy-asset block. The
  minimap needs **no** script now (it's inline SVG in the template partial); the
  explorer JS loads only on `/graph/`.
- `enhancements/lazy-loaders.js`: remove the d3 loader branch.
- `graph_visualizer.html`: **delete the `https://d3js.org/d3.v7.min.js` CDN
  `<script>` (line ~39)** and mount `bengal-graph-explorer.js`. This also closes
  the standing #533 regression (default builds currently emit a page that calls a
  third-party CDN). Result: graph works **on by default, zero external requests**.

---

## Phases

- **P0 — Baseline.** Count nodes/edges on docs + bingo sites; record current D3
  explorer settle time + interaction fps as the "chokes" baseline to beat.
- **P1 — Build-time layout.** Python deterministic force-layout pass; annotate
  `graph.json` + per-page `.graph` with normalized `x`/`y`. Unit-test determinism
  (same input → identical coords) and the quadtree charge vs an O(n²) reference.
- **P2 — Static minimap.** Emit inline `<svg>` from `.graph`+positions in the
  sidebar partial; CSS theming/hover/current-page. **Delete** `graph-contextual.js`
  + `graph-minimap.js`. Visual + behavior parity, verified on a real page.
- **P3 — Explorer.** `bengal-graph-explorer.js`: Canvas render of baked positions,
  pan/zoom, hit-test, search/filter, a11y link list; remove the CDN script.
- **P4 — De-D3.** Remove the `d3` capability + vendor entries; update base.html,
  lazy-loaders.js; changelog (zero-dep default + #533 fix).
- **P5 — Acceptance.** Perf gate (below) + `prefers-reduced-motion` + a11y list +
  fast-check green; confirm byte-parity holds with positions now in the output.

## Acceptance criteria
- Explorer: pan/zoom interactive (~60fps) at docs-site node count **and** 5–10×
  it; no runtime sim, so first paint is bounded by draw, not settle.
- Minimap: zero JS; renders with the page (no separate paint/jank), visual parity
  with today; theme/palette switch with no flash.
- Zero external network requests for the graph in a default build (no CDN, no
  vendored `d3.min.js`).
- Build determinism preserved: warm==cold byte parity with positions now baked
  into `graph.json` / `index.json` (seeded layout, no RNG).

## Risks
- **Determinism (now load-bearing):** positions ship in output, so the layout
  pass MUST be seeded + reproducible across machines/runs — same contract as the
  existing `_get_page_id` stable hash. Verify in fast-check byte-parity tests.
- **Build cost:** layout adds CPU to the build. Bounded — minimap layouts are
  ≤15 nodes; the full-graph pass runs once. Measure in P1; cache/skip if unchanged.
- **CSS-only hover highlight:** sibling-selector highlighting has limits; if it
  can't express "highlight my neighbors," accept simpler hover (scale + label) for
  the minimap rather than reintroducing JS.
- **Visual parity:** target "as good or better," not pixel-identical to D3.

## Files (anchor list)
- New: `bengal/themes/default/assets/js/bengal-graph-explorer.js`;
  Python layout module under `bengal/analysis/graph/` (e.g. `layout.py`).
- New/rewrite: minimap SVG partial in `bengal/themes/default/templates/…`.
- Rewrite: `bengal/analysis/graph/templates/graph_visualizer.html`.
- **Delete:** `graph-contextual.js`, `graph-minimap.js`.
- Edit: `bengal/themes/default/templates/base.html`,
  `enhancements/lazy-loaders.js`, `bengal/capabilities/runtime.py`,
  `bengal/capabilities/vendors.py`, `bengal/analysis/graph/visualizer.py`
  (call layout pass), `bengal/postprocess/output_formats/json_generator.py`
  (carry positions in `.graph`).
- Reuse: `components/graph.css`, `components/graph-contextual.css`.
