Networks

src/lib/components/charts/network-graph/doc.ts

/**
 * NetworkGraph — things and the connections between them.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § CONTRACT — the oracle. Names no library, contains no code.              │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * # Shape
 *
 *     label         REQUIRED
 *     nodes         { id, label?, group?, size? }[]
 *     edges         { from, to, value? (signed −1–1), weight?, label? }[]
 *     layout?       "force" (default) | "radial" | "circular" | "tiered" |
 *                   "flow" | "grid"
 *     root?         the centre of a radial layout
 *     groups?       groups in a FIXED order: colour, shape, and tiers
 *     curved?, labels?, hulls? ({ key, label?, ids }[])
 *     onSelect?, selected?   selection
 *     aspect?, formatValue?, animation?  (default: nodes pop in)
 *
 * # Behaviour
 *
 * R1  The same input always gives the same picture, on the server and in
 *     every browser: layouts are deterministic.
 * R2  Position means what the layout says: force — nearness is a hint;
 *     radial — the ring is hops from the root; circular — nothing (so no
 *     node hides another); tiered — the group; flow — columns by longest
 *     path, every edge pointing forward; grid — nothing, in rows.
 * R3  Groups have a colour AND a shape. Size is drawn as area.
 * R4  A signed edge's hue is its sign and its opacity its strength; a
 *     weight is its width. An edge to a node that does not exist is ignored.
 * R5  Hover or focus lights a node and its neighbours and dims the rest.
 *     Selection is one tab stop: arrow keys move, Enter or Space selects,
 *     Escape clears.
 * R6  Changing the layout (or the data) moves nodes to their new places;
 *     a new node appears where it belongs.
 * R7  With hulls, the force layout gathers each group into its own region
 *     (up to five groups), so a hull outlines a place, not a scatter.
 * R8  Two tables list every node (with its connections) and every edge.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § MECHANICS — how this implementation meets the contract.                 │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * The force layout is d3-force, run synchronously for a fixed number of
 * ticks with hash-seeded starting positions and a seeded random source. A
 * force simulation is chaotic, and ECMAScript leaves cos, sin, hypot, exp,
 * and log to each engine, so none run inside it (d3's only trigonometry is
 * the starting spiral, which seeded positions replace); sqrt and arithmetic
 * are exactly specified by IEEE-754. Labels are HTML placed by percentage.
 */
export {};

src/lib/components/charts/network-graph/NetworkGraph.svelte

<script lang="ts">
	import { TBody, Td, Th, THead, Tr } from '$lib/components/display/table';
	import type { AnimationProp } from '$lib/motion';
	import { chartMotion, Tweened } from '$lib/motion/svelte.svelte';
	import { cn } from '$lib/utils/cn';
	import ChartLegend from '../chart-legend/ChartLegend.svelte';
	import { radiusFor, shapePath } from '../_kernel/encode';
	import { formatExact } from '../_kernel/format';
	import {
		edgePath,
		graphTarget,
		hullAround,
		liveEdges,
		neighbours,
		type GraphEdge,
		type GraphLayout,
		type GraphNode,
		type Point
	} from '../_kernel/graph';
	import { px } from '../_kernel/scale';
	import { categoryColor, seriesShape } from '../_kernel/scatter';
	import ChartData from '../_shared/ChartData.svelte';
	import chart from '../_shared/chart.module.css';
	import styles from './network-graph.module.css';

	/* Things and the connections between them. What position means depends on
	   the layout — a force layout's nearness is a hint, a radial ring is a hop
	   count — so choose the layout for the question. Hover or focus a node to
	   light its neighbours; the tables list every node and connection. */
	let {
		label,
		nodes,
		edges: rawEdges,
		layout = 'force',
		root,
		groups: groupOrder,
		curved = false,
		labels = true,
		hulls = [],
		onSelect,
		selected = null,
		aspect = 1.6,
		formatValue = formatExact,
		animation,
		class: className = ''
	}: {
		/** Names the chart. */
		label: string;
		nodes: readonly GraphNode[];
		edges: readonly GraphEdge[];
		/** How position is decided — and so what it means. */
		layout?: GraphLayout;
		/** The centre of a radial layout. */
		root?: string;
		/** Groups in a FIXED order: colour, shape, and tiers. */
		groups?: readonly string[];
		/** Bow edges into arcs, where straight chords would overlap. */
		curved?: boolean;
		/** Print node names; off for dense graphs. */
		labels?: boolean;
		/** Labelled regions drawn behind groups of nodes. */
		hulls?: readonly { key: string; label?: string; ids: readonly string[] }[];
		/** Makes nodes selectable: one tab stop, arrow keys move between nodes. */
		onSelect?: (id: string | null) => void;
		selected?: string | null;
		/** Width over height. */
		aspect?: number;
		formatValue?: (value: number) => string;
		/** Default: nodes pop in; changing the layout glides them to their new places. */
		animation?: AnimationProp;
		class?: string;
	} = $props();

	const motion = chartMotion(() => animation, { enter: 'pop', axis: 'y' });
	const edges = $derived(liveEdges(nodes, rawEdges));
	const groups = $derived(
		groupOrder ?? [...new Set(nodes.map((n) => n.group ?? ''))].filter(Boolean)
	);
	// The layout is computed once per input, not per hover or tween frame.
	const target = $derived(
		graphTarget(nodes, edges, layout, aspect, { root, groups, cluster: hulls.length > 0 })
	);
	const shown = new Tweened(
		() => target,
		() => motion.update,
		'target'
	);
	const near = $derived(neighbours(nodes, edges));

	let pointed = $state<string | null>(null);
	let active = $state(0);
	let svg = $state<SVGSVGElement>();
	const lit = $derived(pointed ?? selected);
	const stateOf = (id: string) =>
		lit === null ? undefined : id === lit ? 'lit' : near.get(lit)?.has(id) ? 'near' : 'dim';

	const at = (id: string): Point | null => {
		const x = shown.current[`${id}|x`];
		const y = shown.current[`${id}|y`];
		return x === undefined || y === undefined ? null : { x, y };
	};
	// The frame fits the laid-out nodes, with room for their labels.
	const bounds = $derived.by(() => {
		const finals = nodes.flatMap((n) => {
			const x = target[`${n.id}|x`];
			const y = target[`${n.id}|y`];
			return x === undefined ? [] : [{ x, y }];
		});
		const left = Math.min(0, ...finals.map((p) => p.x)) - 60;
		const right = Math.max(1000, ...finals.map((p) => p.x)) + 60;
		const top = Math.min(0, ...finals.map((p) => p.y)) - 50;
		const bottom = Math.max(1000 / aspect, ...finals.map((p) => p.y)) + 50;
		return { left, top, width: right - left, height: bottom - top };
	});
	const pct = (p: Point) =>
		`left:${((p.x - bounds.left) / bounds.width) * 100}%;top:${((p.y - bounds.top) / bounds.height) * 100}%`;

	const sizes = $derived(
		nodes.map((n) => n.size).filter((s): s is number => typeof s === 'number' && s > 0)
	);
	const range = $derived<[number, number]>(
		sizes.length ? [Math.min(...sizes), Math.max(...sizes)] : [1, 1]
	);
	const radius = (n: GraphNode) => (n.size && n.size > 0 ? radiusFor(n.size, range, [9, 26]) : 11);
	const maxWeight = $derived(Math.max(1, ...edges.map((e) => e.weight ?? 0)));
	const degree = (id: string) => near.get(id)?.size ?? 0;
	const name = (id: string) => nodes.find((n) => n.id === id)?.label ?? id;
	const hullColors = $derived(hulls.map((h) => h.key));

	const select = (id: string) => onSelect?.(selected === id ? null : id);
	function move(event: KeyboardEvent) {
		if (!onSelect) return;
		if (event.key === 'Escape') {
			onSelect(null);
			return;
		}
		const step = (
			{ ArrowRight: 1, ArrowDown: 1, ArrowLeft: -1, ArrowUp: -1 } as Record<string, number>
		)[event.key];
		if (step === undefined) return;
		event.preventDefault();
		const next = (active + step + nodes.length) % nodes.length;
		active = next;
		svg?.querySelector<SVGGElement>(`[data-index="${next}"]`)?.focus();
	}
</script>

{#if !nodes.length}
	<div class={cn(chart.root, className)}>
		<p class={chart.empty}>No data to display.</p>
	</div>
{:else}
	<div {...motion.pending} {@attach motion.attach} class={cn(chart.root, className)}>
		{#if groups.length > 1}
			<ChartLegend
				items={groups.map((group) => ({
					key: group,
					label: group,
					color: categoryColor(groups, group),
					shape: seriesShape(groups, group)
				}))}
			/>
		{/if}
		<div class={styles.frame} style:--aspect={bounds.width / bounds.height}>
			<svg
				bind:this={svg}
				class={styles.svg}
				viewBox="{px(bounds.left)} {px(bounds.top)} {px(bounds.width)} {px(bounds.height)}"
				role={onSelect ? 'group' : 'img'}
				aria-label="{label}. Every node and connection is in the data tables."
				data-lit={lit ? '' : undefined}
				onkeydown={onSelect ? move : undefined}
			>
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape}
						<ellipse
							class={styles.hull}
							style:--series={categoryColor(hullColors, hull.key)}
							cx={shape.cx}
							cy={shape.cy}
							rx={shape.rx}
							ry={shape.ry}
						/>
					{/if}
				{/each}
				{#each edges as edge, index (`${edge.from}-${edge.to}-${index}`)}
					{@const a = at(edge.from)}
					{@const b = at(edge.to)}
					{#if a && b}
						{@const signed = typeof edge.value === 'number'}
						<path
							class={styles.edge}
							d={edgePath(a, b, curved)}
							data-lit={lit !== null && (edge.from === lit || edge.to === lit) ? '' : undefined}
							data-sign={signed
								? (edge.value as number) < 0
									? 'negative'
									: 'positive'
								: undefined}
							style:--edge-w={1 + ((edge.weight ?? 0) / maxWeight) * 3}
							style:--edge-o={signed
								? 0.25 + Math.min(1, Math.abs(edge.value as number)) * 0.65
								: undefined}
						/>
					{/if}
				{/each}
				{#each nodes as node, index (node.id)}
					{@const p = at(node.id)}
					{#if p}
						{@const r = radius(node)}
						<g transform="translate({px(p.x)} {px(p.y)})">
							{#if onSelect}
								<g
									data-mark
									data-index={index}
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									role="button"
									tabindex={index === active ? 0 : -1}
									aria-label="{node.label ?? node.id}{node.group ? `, ${node.group}` : ''}, {degree(
										node.id
									)} connections"
									aria-pressed={selected === node.id}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
									onfocus={() => {
										pointed = node.id;
										active = index;
									}}
									onblur={() => (pointed = null)}
									onclick={() => select(node.id)}
									onkeydown={(event) => {
										if (event.key === 'Enter' || event.key === ' ') {
											event.preventDefault();
											select(node.id);
										}
									}}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{:else}
								<!-- svelte-ignore a11y_no_static_element_interactions -->
								<g
									data-mark
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{/if}
						</g>
					{/if}
				{/each}
			</svg>
			<div class={styles.labels} aria-hidden="true">
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape && hull.label}
						<span data-hull style={pct({ x: shape.cx, y: shape.cy - shape.ry })}>{hull.label}</span>
					{/if}
				{/each}
				{#if labels}
					{#each nodes as node (node.id)}
						{@const p = at(node.id)}
						{#if p}
							<span data-state={stateOf(node.id)} style={pct({ x: p.x, y: p.y + radius(node) })}
								>{node.label ?? node.id}</span
							>
						{/if}
					{/each}
				{/if}
			</div>
		</div>
		<ChartData {label} summary="View nodes">
			<THead>
				<Tr>
					<Th>Node</Th><Th>Group</Th><Th numeric>Connections</Th>
					{#if sizes.length}<Th numeric>Size</Th>{/if}
				</Tr>
			</THead>
			<TBody>
				{#each nodes as node (node.id)}
					<Tr>
						<Th scope="row">{node.label ?? node.id}</Th>
						<Td>{node.group ?? '—'}</Td>
						<Td numeric>{degree(node.id)}</Td>
						{#if sizes.length}
							<Td numeric>{typeof node.size === 'number' ? formatValue(node.size) : '—'}</Td>
						{/if}
					</Tr>
				{/each}
			</TBody>
		</ChartData>
		<ChartData {label} summary="View connections">
			<THead>
				<Tr><Th>From</Th><Th>To</Th><Th numeric>Value</Th></Tr>
			</THead>
			<TBody>
				{#each edges as edge, index (index)}
					{@const value = edge.value ?? edge.weight}
					<Tr>
						<Th scope="row">{name(edge.from)}</Th>
						<Td>{name(edge.to)}</Td>
						<Td numeric>{typeof value === 'number' ? formatValue(value) : '—'}</Td>
					</Tr>
				{/each}
			</TBody>
		</ChartData>
	</div>
{/if}

src/lib/components/charts/network-graph/network-graph.module.css

@layer primitive {
	.frame {
		position: relative;
		width: 100%;
		aspect-ratio: var(--aspect, 1.6);
	}
	.svg {
		position: absolute;
		inset: 0;
		width: 100%;
		height: 100%;
		overflow: visible;
	}
	.hull {
		fill: color-mix(in oklab, var(--series) 12%, transparent);
		stroke: color-mix(in oklab, var(--series) 45%, transparent);
		stroke-dasharray: 4 4;
		stroke-width: 1;
		vector-effect: non-scaling-stroke;
	}
	.edge {
		fill: none;
		stroke: var(--chart-axis, var(--line-strong));
		stroke-opacity: 0.7;
		stroke-width: var(--edge-w, 1.25);
		vector-effect: non-scaling-stroke;
		transition: stroke-opacity var(--dur-2) var(--ease);
	}
	.edge[data-sign='positive'] {
		stroke: var(--chart-pos);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.edge[data-sign='negative'] {
		stroke: var(--chart-neg);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.svg[data-lit] .edge:not([data-lit]) {
		stroke-opacity: 0.12;
	}
	.node {
		transform-origin: center;
		transition: opacity var(--dur-2) var(--ease);
	}
	.shape {
		fill: var(--series);
		stroke: var(--surface-panel);
		stroke-width: 1.5;
		vector-effect: non-scaling-stroke;
	}
	.svg[data-lit] .node[data-state='dim'] {
		opacity: 0.25;
	}
	.ring {
		fill: none;
		stroke: var(--accent);
		stroke-width: 2.5;
		vector-effect: non-scaling-stroke;
		opacity: 0;
	}
	.node[data-state='lit'] .ring,
	.node[aria-pressed='true'] .ring {
		opacity: 1;
	}
	.node[role='button'] {
		cursor: pointer;
		outline: none;
	}
	.node[role='button']:focus-visible .ring {
		stroke-dasharray: 3 2;
		opacity: 1;
	}
	.labels {
		position: absolute;
		inset: 0;
		pointer-events: none;
		font-size: var(--text-11);
	}
	.labels span {
		position: absolute;
		color: var(--ink-2);
		white-space: nowrap;
		transform: translate(-50%, 6px);
		transition: opacity var(--dur-2) var(--ease);
	}
	.labels span[data-state='dim'] {
		opacity: 0.25;
	}
	.labels span[data-hull] {
		color: var(--ink-3);
		font-weight: var(--weight-medium);
		transform: translate(-50%, -100%);
	}
}

src/lib/components/charts/_kernel/graph.ts

import {
	forceCollide,
	forceLink,
	forceManyBody,
	forceSimulation,
	forceX,
	forceY,
	type SimulationNodeDatum
} from 'd3-force';

import { px } from './scale';

/* NetworkGraph's maths: layouts and geometry, all deterministic, so the
   server and the browser draw the same picture.

   A force layout is chaotic: a one-bit difference in step one grows into a
   visibly different graph. ECMAScript leaves cos, sin, hypot, exp, and log
   to each engine, so none of them appear inside the simulation — starting
   positions come from a hash, the simulation's randomness from a seeded
   generator, and distances from sqrt, which IEEE-754 specifies exactly. */

export type GraphNode = {
	id: string;
	label?: string;
	/** A class: sets colour and shape (by `groups` order), and the tier in a
	 *  tiered layout. */
	group?: string;
	/** A magnitude drawn as the node's area. */
	size?: number;
};

export type GraphEdge = {
	from: string;
	to: string;
	/** Signed, −1 to 1: hue is the sign, opacity the strength. */
	value?: number;
	/** Unsigned strength: drawn as width. */
	weight?: number;
	label?: string;
};

export type GraphLayout = 'force' | 'radial' | 'circular' | 'tiered' | 'flow' | 'grid';
export type Point = { x: number; y: number };

/** The virtual canvas layouts place nodes on. */
export const GRAPH_W = 1000;

/** FNV-1a → 0–1: a repeatable number per string. */
export function seedOf(text: string) {
	let h = 2166136261;
	for (let i = 0; i < text.length; i++) {
		h ^= text.charCodeAt(i);
		h = Math.imul(h, 16777619);
	}
	return (h >>> 0) / 4294967296;
}

/** A seeded linear congruential generator for the simulation's jiggle. */
function lcg(seed: number) {
	let s = Math.floor(seed * 4294967296) >>> 0 || 1;
	return () => {
		s = (Math.imul(1664525, s) + 1013904223) >>> 0;
		return s / 4294967296;
	};
}

/** Edges whose ends both exist; a dangling edge is ignored, not guessed. */
export function liveEdges(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const ids = new Set(nodes.map((n) => n.id));
	return edges.filter((e) => ids.has(e.from) && ids.has(e.to) && e.from !== e.to);
}

export function neighbours(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const near = new Map<string, Set<string>>(nodes.map((n) => [n.id, new Set()]));
	for (const e of edges) {
		near.get(e.from)?.add(e.to);
		near.get(e.to)?.add(e.from);
	}
	return near;
}

/** Hops from a root, walking edges both ways; unreached nodes go one ring
 *  beyond the furthest. */
export function hopsFrom(nodes: readonly GraphNode[], edges: readonly GraphEdge[], root: string) {
	const near = neighbours(nodes, edges);
	const depth = new Map<string, number>([[root, 0]]);
	let frontier = [root];
	while (frontier.length) {
		const next: string[] = [];
		for (const id of frontier)
			for (const other of near.get(id) ?? []) {
				if (depth.has(other)) continue;
				depth.set(other, (depth.get(id) ?? 0) + 1);
				next.push(other);
			}
		frontier = next;
	}
	const beyond = Math.max(0, ...depth.values()) + 1;
	for (const n of nodes) if (!depth.has(n.id)) depth.set(n.id, beyond);
	return depth;
}

/** Split edges into those that keep the graph acyclic and the "back"
 *  edges that close a loop, by depth-first search in input order: a loop is
 *  broken at the edge that closes it (c → a in a → b → c → a), not wherever
 *  a walk happens to land. */
export function splitLoops<E extends { from: string; to: string }>(
	nodes: readonly { id: string }[],
	edges: readonly E[]
) {
	const outgoing = new Map<string, E[]>(nodes.map((n) => [n.id, []]));
	for (const e of edges) outgoing.get(e.from)?.push(e);
	const state = new Map<string, 1 | 2>();
	const back = new Set<E>();
	const visit = (id: string) => {
		state.set(id, 1);
		for (const e of outgoing.get(id) ?? []) {
			const s = state.get(e.to);
			if (s === 1) back.add(e);
			else if (s === undefined) visit(e.to);
		}
		state.set(id, 2);
	};
	for (const n of nodes) if (!state.has(n.id)) visit(n.id);
	return {
		forward: edges.filter((e) => !back.has(e)),
		loops: edges.filter((e) => back.has(e))
	};
}

/** Longest path from any source, for flow layouts; loops are broken first
 *  (see splitLoops). */
export function longestPath(
	nodes: readonly { id: string }[],
	edges: readonly { from: string; to: string }[]
) {
	const { forward } = splitLoops(nodes, edges);
	const incoming = new Map<string, string[]>(nodes.map((n) => [n.id, []]));
	for (const e of forward) incoming.get(e.to)?.push(e.from);
	const depth = new Map<string, number>();
	const walk = (id: string): number => {
		const known = depth.get(id);
		if (known !== undefined) return known;
		const from = incoming.get(id) ?? [];
		const d = from.length ? Math.max(...from.map((f) => walk(f) + 1)) : 0;
		depth.set(id, d);
		return d;
	};
	for (const n of nodes) walk(n.id);
	return depth;
}

type Options = { root?: string; groups: readonly string[]; cluster?: boolean };

type Layout = (
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	height: number,
	options: Options
) => Map<string, Point>;

/** Where each group gathers when a force layout is clustered, as fractions
 *  of the canvas. A fixed table, not points on a circle: anything that feeds
 *  the simulation must avoid engine-dependent maths. */
const ANCHORS: readonly (readonly [number, number])[][] = [
	[[0.5, 0.5]],
	[
		[0.28, 0.5],
		[0.72, 0.5]
	],
	[
		[0.5, 0.26],
		[0.26, 0.72],
		[0.74, 0.72]
	],
	[
		[0.28, 0.28],
		[0.72, 0.28],
		[0.28, 0.72],
		[0.72, 0.72]
	],
	[
		[0.5, 0.2],
		[0.2, 0.45],
		[0.8, 0.45],
		[0.32, 0.8],
		[0.68, 0.8]
	]
];

const force: Layout = (nodes, edges, height, { groups, cluster }) => {
	type Sim = SimulationNodeDatum & { id: string };
	const sim: Sim[] = nodes.map((n) => ({
		id: n.id,
		x: GRAPH_W * (0.25 + seedOf(`${n.id}:x`) * 0.5),
		y: height * (0.25 + seedOf(`${n.id}:y`) * 0.5)
	}));
	const spacing = Math.sqrt((GRAPH_W * height) / Math.max(1, nodes.length));
	const simulation = forceSimulation(sim)
		.randomSource(lcg(seedOf(nodes.map((n) => n.id).join('|'))))
		.force(
			'link',
			forceLink<Sim, { source: string; target: string }>(
				edges.map((e) => ({ source: e.from, target: e.to }))
			)
				.id((d) => d.id)
				.distance(spacing * 0.55)
		)
		.force('charge', forceManyBody().strength(-spacing * 2))
		.force('collide', forceCollide(24))
		.stop();
	// Clustered, each group is drawn toward its own region (up to five
	// groups); otherwise everything is drawn gently toward the centre.
	const table = ANCHORS[Math.min(groups.length, ANCHORS.length) - 1];
	const groupOf = new Map(nodes.map((n) => [n.id, n.group ?? '']));
	const anchor = (id: string) => {
		const index = groups.indexOf(groupOf.get(id) ?? '');
		return cluster && table && index >= 0 && index < table.length ? table[index] : [0.5, 0.5];
	};
	const pull = cluster ? 0.18 : 0.06;
	simulation
		.force('x', forceX<Sim>((d) => anchor(d.id)[0] * GRAPH_W).strength(pull))
		.force('y', forceY<Sim>((d) => anchor(d.id)[1] * height).strength(pull * (GRAPH_W / height)));
	simulation.tick(300);
	return fit(new Map(sim.map((n) => [n.id, { x: n.x ?? 0, y: n.y ?? 0 }])), height);
};

/** Scale positions uniformly (so shapes keep their proportions) to fill the
 *  canvas, less a margin for labels. */
function fit(points: Map<string, Point>, height: number, margin = 70) {
	if (points.size < 2)
		return new Map([...points].map(([id]) => [id, { x: GRAPH_W / 2, y: height / 2 }]));
	const xs = [...points.values()].map((p) => p.x);
	const ys = [...points.values()].map((p) => p.y);
	const [x0, x1, y0, y1] = [Math.min(...xs), Math.max(...xs), Math.min(...ys), Math.max(...ys)];
	const scale = Math.min(
		(GRAPH_W - 2 * margin) / Math.max(1, x1 - x0),
		(height - 2 * margin) / Math.max(1, y1 - y0)
	);
	const ox = (GRAPH_W - (x1 - x0) * scale) / 2;
	const oy = (height - (y1 - y0) * scale) / 2;
	return new Map(
		[...points].map(([id, p]) => [
			id,
			{ x: px(ox + (p.x - x0) * scale), y: px(oy + (p.y - y0) * scale) }
		])
	);
}

const circle = (count: number, index: number, cx: number, cy: number, r: number, turn = 0) => {
	const angle = (index / Math.max(1, count)) * 2 * Math.PI - Math.PI / 2 + turn;
	return { x: px(cx + r * Math.cos(angle)), y: px(cy + r * Math.sin(angle)) };
};

const radial: Layout = (nodes, edges, height, { root }) => {
	const centre = root ?? nodes[0]?.id ?? '';
	const depth = hopsFrom(nodes, edges, centre);
	const near = neighbours(nodes, edges);
	const rings = new Map<number, string[]>();
	for (const n of nodes) {
		if (n.id === centre) continue;
		const d = depth.get(n.id) ?? 1;
		rings.set(d, [...(rings.get(d) ?? []), n.id]);
	}
	const out = new Map<string, Point>([[centre, { x: GRAPH_W / 2, y: height / 2 }]]);
	// Turns around the centre, per node, so a ring can follow the one inside.
	const turn = new Map<string, number>([[centre, 0]]);
	const count = Math.max(1, rings.size);
	const outer = Math.min(GRAPH_W, height) / 2 - 50;
	for (const [ring, ids] of [...rings].sort((a, b) => a[0] - b[0])) {
		// Order a ring by where its parent sits, so children stay beside their
		// parent and edges do not cross the middle.
		const parentTurn = (id: string) => {
			const parents = [...(near.get(id) ?? [])].filter(
				(p) => turn.has(p) && (depth.get(p) ?? 0) < ring
			);
			return parents.length ? Math.min(...parents.map((p) => turn.get(p)!)) : 1;
		};
		const ordered = [...ids].sort((a, b) => parentTurn(a) - parentTurn(b) || a.localeCompare(b));
		const r = (outer * ring) / count;
		ordered.forEach((id, i) => {
			const t = (i + 0.5) / ordered.length;
			turn.set(id, t);
			out.set(id, circle(1, 0, GRAPH_W / 2, height / 2, r, t * 2 * Math.PI));
		});
	}
	return out;
};

const circular: Layout = (nodes, _edges, height) => {
	const r = Math.min(GRAPH_W, height) / 2 - 40;
	return new Map(nodes.map((n, i) => [n.id, circle(nodes.length, i, GRAPH_W / 2, height / 2, r)]));
};

const tiered: Layout = (nodes, _edges, height, { groups }) => {
	const order = [...new Set([...groups, ...nodes.map((n) => n.group ?? '')])].filter((g) =>
		nodes.some((n) => (n.group ?? '') === g)
	);
	const out = new Map<string, Point>();
	order.forEach((group, column) => {
		const ids = nodes.filter((n) => (n.group ?? '') === group).map((n) => n.id);
		const x =
			order.length === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (order.length - 1);
		ids.forEach((id, i) => out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) }));
	});
	return out;
};

const flow: Layout = (nodes, edges, height) => {
	const depth = longestPath(nodes, edges);
	const columns = new Map<number, string[]>();
	for (const n of nodes) {
		const d = depth.get(n.id) ?? 0;
		columns.set(d, [...(columns.get(d) ?? []), n.id]);
	}
	const count = Math.max(1, columns.size);
	const out = new Map<string, Point>();
	[...columns]
		.sort((a, b) => a[0] - b[0])
		.forEach(([, ids], column) => {
			const x = count === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (count - 1);
			ids.forEach((id, i) =>
				out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) })
			);
		});
	return out;
};

const grid: Layout = (nodes, _edges, height) => {
	const cols = Math.max(1, Math.ceil(Math.sqrt(nodes.length * (GRAPH_W / height))));
	const rows = Math.max(1, Math.ceil(nodes.length / cols));
	return new Map(
		nodes.map((n, i) => [
			n.id,
			{
				x: px((((i % cols) + 1) * GRAPH_W) / (cols + 1)),
				y: px(((Math.floor(i / cols) + 1) * height) / (rows + 1))
			}
		])
	);
};

const LAYOUTS: Record<GraphLayout, Layout> = {
	force,
	radial,
	circular,
	tiered,
	flow,
	grid
};

/** Every node's position, as a record for tweening: `${id}|x`, `${id}|y`. */
export function graphTarget(
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	layout: GraphLayout,
	aspect: number,
	options: Options
) {
	const height = GRAPH_W / aspect;
	const placed = nodes.length ? LAYOUTS[layout](nodes, edges, height, options) : new Map();
	const target: Record<string, number> = {};
	for (const [id, p] of placed) {
		target[`${id}|x`] = p.x;
		target[`${id}|y`] = p.y;
	}
	return target;
}

/** A straight edge, or a shallow arc that bows with length — straight for
 *  radial layouts, arcs where chords would overlap into a disc. */
export function edgePath(a: Point, b: Point, curved: boolean) {
	if (!curved) return `M${px(a.x)},${px(a.y)}L${px(b.x)},${px(b.y)}`;
	const dx = b.x - a.x;
	const dy = b.y - a.y;
	const distance = Math.sqrt(dx * dx + dy * dy) || 1;
	const bow = Math.min(distance * 0.18, 60);
	const mx = (a.x + b.x) / 2 - (dy / distance) * bow;
	const my = (a.y + b.y) / 2 + (dx / distance) * bow;
	return `M${px(a.x)},${px(a.y)}Q${px(mx)},${px(my)} ${px(b.x)},${px(b.y)}`;
}

/** An ellipse around a set of positions, for a labelled group (a hull). */
export function hullAround(points: readonly Point[]) {
	if (!points.length) return null;
	const cx = points.reduce((sum, p) => sum + p.x, 0) / points.length;
	const cy = points.reduce((sum, p) => sum + p.y, 0) / points.length;
	const r =
		Math.max(
			34,
			...points.map((p) => {
				const dx = p.x - cx;
				const dy = p.y - cy;
				return Math.sqrt(dx * dx + dy * dy);
			})
		) + 30;
	return { cx: px(cx), cy: px(cy), rx: px(r * 1.12), ry: px(r) };
}

src/lib/components/charts/network-graph/doc.ts

/**
 * NetworkGraph — things and the connections between them.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § CONTRACT — the oracle. Names no library, contains no code.              │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * # Shape
 *
 *     label         REQUIRED
 *     nodes         { id, label?, group?, size? }[]
 *     edges         { from, to, value? (signed −1–1), weight?, label? }[]
 *     layout?       "force" (default) | "radial" | "circular" | "tiered" |
 *                   "flow" | "grid"
 *     root?         the centre of a radial layout
 *     groups?       groups in a FIXED order: colour, shape, and tiers
 *     curved?, labels?, hulls? ({ key, label?, ids }[])
 *     onSelect?, selected?   selection
 *     aspect?, formatValue?, animation?  (default: nodes pop in)
 *
 * # Behaviour
 *
 * R1  The same input always gives the same picture, on the server and in
 *     every browser: layouts are deterministic.
 * R2  Position means what the layout says: force — nearness is a hint;
 *     radial — the ring is hops from the root; circular — nothing (so no
 *     node hides another); tiered — the group; flow — columns by longest
 *     path, every edge pointing forward; grid — nothing, in rows.
 * R3  Groups have a colour AND a shape. Size is drawn as area.
 * R4  A signed edge's hue is its sign and its opacity its strength; a
 *     weight is its width. An edge to a node that does not exist is ignored.
 * R5  Hover or focus lights a node and its neighbours and dims the rest.
 *     Selection is one tab stop: arrow keys move, Enter or Space selects,
 *     Escape clears.
 * R6  Changing the layout (or the data) moves nodes to their new places;
 *     a new node appears where it belongs.
 * R7  With hulls, the force layout gathers each group into its own region
 *     (up to five groups), so a hull outlines a place, not a scatter.
 * R8  Two tables list every node (with its connections) and every edge.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § MECHANICS — how this implementation meets the contract.                 │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * The force layout is d3-force, run synchronously for a fixed number of
 * ticks with hash-seeded starting positions and a seeded random source. A
 * force simulation is chaotic, and ECMAScript leaves cos, sin, hypot, exp,
 * and log to each engine, so none run inside it (d3's only trigonometry is
 * the starting spiral, which seeded positions replace); sqrt and arithmetic
 * are exactly specified by IEEE-754. Labels are HTML placed by percentage.
 */
export {};

src/lib/components/charts/network-graph/NetworkGraph.svelte

<script lang="ts">
	import { TBody, Td, Th, THead, Tr } from '$lib/components/display/table';
	import type { AnimationProp } from '$lib/motion';
	import { chartMotion, Tweened } from '$lib/motion/svelte.svelte';
	import { cn } from '$lib/utils/cn';
	import ChartLegend from '../chart-legend/ChartLegend.svelte';
	import { radiusFor, shapePath } from '../_kernel/encode';
	import { formatExact } from '../_kernel/format';
	import {
		edgePath,
		graphTarget,
		hullAround,
		liveEdges,
		neighbours,
		type GraphEdge,
		type GraphLayout,
		type GraphNode,
		type Point
	} from '../_kernel/graph';
	import { px } from '../_kernel/scale';
	import { categoryColor, seriesShape } from '../_kernel/scatter';
	import ChartData from '../_shared/ChartData.svelte';
	import chart from '../_shared/chart.module.css';
	import styles from './network-graph.module.css';

	/* Things and the connections between them. What position means depends on
	   the layout — a force layout's nearness is a hint, a radial ring is a hop
	   count — so choose the layout for the question. Hover or focus a node to
	   light its neighbours; the tables list every node and connection. */
	let {
		label,
		nodes,
		edges: rawEdges,
		layout = 'force',
		root,
		groups: groupOrder,
		curved = false,
		labels = true,
		hulls = [],
		onSelect,
		selected = null,
		aspect = 1.6,
		formatValue = formatExact,
		animation,
		class: className = ''
	}: {
		/** Names the chart. */
		label: string;
		nodes: readonly GraphNode[];
		edges: readonly GraphEdge[];
		/** How position is decided — and so what it means. */
		layout?: GraphLayout;
		/** The centre of a radial layout. */
		root?: string;
		/** Groups in a FIXED order: colour, shape, and tiers. */
		groups?: readonly string[];
		/** Bow edges into arcs, where straight chords would overlap. */
		curved?: boolean;
		/** Print node names; off for dense graphs. */
		labels?: boolean;
		/** Labelled regions drawn behind groups of nodes. */
		hulls?: readonly { key: string; label?: string; ids: readonly string[] }[];
		/** Makes nodes selectable: one tab stop, arrow keys move between nodes. */
		onSelect?: (id: string | null) => void;
		selected?: string | null;
		/** Width over height. */
		aspect?: number;
		formatValue?: (value: number) => string;
		/** Default: nodes pop in; changing the layout glides them to their new places. */
		animation?: AnimationProp;
		class?: string;
	} = $props();

	const motion = chartMotion(() => animation, { enter: 'pop', axis: 'y' });
	const edges = $derived(liveEdges(nodes, rawEdges));
	const groups = $derived(
		groupOrder ?? [...new Set(nodes.map((n) => n.group ?? ''))].filter(Boolean)
	);
	// The layout is computed once per input, not per hover or tween frame.
	const target = $derived(
		graphTarget(nodes, edges, layout, aspect, { root, groups, cluster: hulls.length > 0 })
	);
	const shown = new Tweened(
		() => target,
		() => motion.update,
		'target'
	);
	const near = $derived(neighbours(nodes, edges));

	let pointed = $state<string | null>(null);
	let active = $state(0);
	let svg = $state<SVGSVGElement>();
	const lit = $derived(pointed ?? selected);
	const stateOf = (id: string) =>
		lit === null ? undefined : id === lit ? 'lit' : near.get(lit)?.has(id) ? 'near' : 'dim';

	const at = (id: string): Point | null => {
		const x = shown.current[`${id}|x`];
		const y = shown.current[`${id}|y`];
		return x === undefined || y === undefined ? null : { x, y };
	};
	// The frame fits the laid-out nodes, with room for their labels.
	const bounds = $derived.by(() => {
		const finals = nodes.flatMap((n) => {
			const x = target[`${n.id}|x`];
			const y = target[`${n.id}|y`];
			return x === undefined ? [] : [{ x, y }];
		});
		const left = Math.min(0, ...finals.map((p) => p.x)) - 60;
		const right = Math.max(1000, ...finals.map((p) => p.x)) + 60;
		const top = Math.min(0, ...finals.map((p) => p.y)) - 50;
		const bottom = Math.max(1000 / aspect, ...finals.map((p) => p.y)) + 50;
		return { left, top, width: right - left, height: bottom - top };
	});
	const pct = (p: Point) =>
		`left:${((p.x - bounds.left) / bounds.width) * 100}%;top:${((p.y - bounds.top) / bounds.height) * 100}%`;

	const sizes = $derived(
		nodes.map((n) => n.size).filter((s): s is number => typeof s === 'number' && s > 0)
	);
	const range = $derived<[number, number]>(
		sizes.length ? [Math.min(...sizes), Math.max(...sizes)] : [1, 1]
	);
	const radius = (n: GraphNode) => (n.size && n.size > 0 ? radiusFor(n.size, range, [9, 26]) : 11);
	const maxWeight = $derived(Math.max(1, ...edges.map((e) => e.weight ?? 0)));
	const degree = (id: string) => near.get(id)?.size ?? 0;
	const name = (id: string) => nodes.find((n) => n.id === id)?.label ?? id;
	const hullColors = $derived(hulls.map((h) => h.key));

	const select = (id: string) => onSelect?.(selected === id ? null : id);
	function move(event: KeyboardEvent) {
		if (!onSelect) return;
		if (event.key === 'Escape') {
			onSelect(null);
			return;
		}
		const step = (
			{ ArrowRight: 1, ArrowDown: 1, ArrowLeft: -1, ArrowUp: -1 } as Record<string, number>
		)[event.key];
		if (step === undefined) return;
		event.preventDefault();
		const next = (active + step + nodes.length) % nodes.length;
		active = next;
		svg?.querySelector<SVGGElement>(`[data-index="${next}"]`)?.focus();
	}
</script>

{#if !nodes.length}
	<div class={cn(chart.root, className)}>
		<p class={chart.empty}>No data to display.</p>
	</div>
{:else}
	<div {...motion.pending} {@attach motion.attach} class={cn(chart.root, className)}>
		{#if groups.length > 1}
			<ChartLegend
				items={groups.map((group) => ({
					key: group,
					label: group,
					color: categoryColor(groups, group),
					shape: seriesShape(groups, group)
				}))}
			/>
		{/if}
		<div class={styles.frame} style:--aspect={bounds.width / bounds.height}>
			<svg
				bind:this={svg}
				class={styles.svg}
				viewBox="{px(bounds.left)} {px(bounds.top)} {px(bounds.width)} {px(bounds.height)}"
				role={onSelect ? 'group' : 'img'}
				aria-label="{label}. Every node and connection is in the data tables."
				data-lit={lit ? '' : undefined}
				onkeydown={onSelect ? move : undefined}
			>
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape}
						<ellipse
							class={styles.hull}
							style:--series={categoryColor(hullColors, hull.key)}
							cx={shape.cx}
							cy={shape.cy}
							rx={shape.rx}
							ry={shape.ry}
						/>
					{/if}
				{/each}
				{#each edges as edge, index (`${edge.from}-${edge.to}-${index}`)}
					{@const a = at(edge.from)}
					{@const b = at(edge.to)}
					{#if a && b}
						{@const signed = typeof edge.value === 'number'}
						<path
							class={styles.edge}
							d={edgePath(a, b, curved)}
							data-lit={lit !== null && (edge.from === lit || edge.to === lit) ? '' : undefined}
							data-sign={signed
								? (edge.value as number) < 0
									? 'negative'
									: 'positive'
								: undefined}
							style:--edge-w={1 + ((edge.weight ?? 0) / maxWeight) * 3}
							style:--edge-o={signed
								? 0.25 + Math.min(1, Math.abs(edge.value as number)) * 0.65
								: undefined}
						/>
					{/if}
				{/each}
				{#each nodes as node, index (node.id)}
					{@const p = at(node.id)}
					{#if p}
						{@const r = radius(node)}
						<g transform="translate({px(p.x)} {px(p.y)})">
							{#if onSelect}
								<g
									data-mark
									data-index={index}
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									role="button"
									tabindex={index === active ? 0 : -1}
									aria-label="{node.label ?? node.id}{node.group ? `, ${node.group}` : ''}, {degree(
										node.id
									)} connections"
									aria-pressed={selected === node.id}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
									onfocus={() => {
										pointed = node.id;
										active = index;
									}}
									onblur={() => (pointed = null)}
									onclick={() => select(node.id)}
									onkeydown={(event) => {
										if (event.key === 'Enter' || event.key === ' ') {
											event.preventDefault();
											select(node.id);
										}
									}}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{:else}
								<!-- svelte-ignore a11y_no_static_element_interactions -->
								<g
									data-mark
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{/if}
						</g>
					{/if}
				{/each}
			</svg>
			<div class={styles.labels} aria-hidden="true">
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape && hull.label}
						<span data-hull style={pct({ x: shape.cx, y: shape.cy - shape.ry })}>{hull.label}</span>
					{/if}
				{/each}
				{#if labels}
					{#each nodes as node (node.id)}
						{@const p = at(node.id)}
						{#if p}
							<span data-state={stateOf(node.id)} style={pct({ x: p.x, y: p.y + radius(node) })}
								>{node.label ?? node.id}</span
							>
						{/if}
					{/each}
				{/if}
			</div>
		</div>
		<ChartData {label} summary="View nodes">
			<THead>
				<Tr>
					<Th>Node</Th><Th>Group</Th><Th numeric>Connections</Th>
					{#if sizes.length}<Th numeric>Size</Th>{/if}
				</Tr>
			</THead>
			<TBody>
				{#each nodes as node (node.id)}
					<Tr>
						<Th scope="row">{node.label ?? node.id}</Th>
						<Td>{node.group ?? '—'}</Td>
						<Td numeric>{degree(node.id)}</Td>
						{#if sizes.length}
							<Td numeric>{typeof node.size === 'number' ? formatValue(node.size) : '—'}</Td>
						{/if}
					</Tr>
				{/each}
			</TBody>
		</ChartData>
		<ChartData {label} summary="View connections">
			<THead>
				<Tr><Th>From</Th><Th>To</Th><Th numeric>Value</Th></Tr>
			</THead>
			<TBody>
				{#each edges as edge, index (index)}
					{@const value = edge.value ?? edge.weight}
					<Tr>
						<Th scope="row">{name(edge.from)}</Th>
						<Td>{name(edge.to)}</Td>
						<Td numeric>{typeof value === 'number' ? formatValue(value) : '—'}</Td>
					</Tr>
				{/each}
			</TBody>
		</ChartData>
	</div>
{/if}

src/lib/components/charts/network-graph/network-graph.module.css

@layer primitive {
	.frame {
		position: relative;
		width: 100%;
		aspect-ratio: var(--aspect, 1.6);
	}
	.svg {
		position: absolute;
		inset: 0;
		width: 100%;
		height: 100%;
		overflow: visible;
	}
	.hull {
		fill: color-mix(in oklab, var(--series) 12%, transparent);
		stroke: color-mix(in oklab, var(--series) 45%, transparent);
		stroke-dasharray: 4 4;
		stroke-width: 1;
		vector-effect: non-scaling-stroke;
	}
	.edge {
		fill: none;
		stroke: var(--chart-axis, var(--line-strong));
		stroke-opacity: 0.7;
		stroke-width: var(--edge-w, 1.25);
		vector-effect: non-scaling-stroke;
		transition: stroke-opacity var(--dur-2) var(--ease);
	}
	.edge[data-sign='positive'] {
		stroke: var(--chart-pos);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.edge[data-sign='negative'] {
		stroke: var(--chart-neg);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.svg[data-lit] .edge:not([data-lit]) {
		stroke-opacity: 0.12;
	}
	.node {
		transform-origin: center;
		transition: opacity var(--dur-2) var(--ease);
	}
	.shape {
		fill: var(--series);
		stroke: var(--surface-panel);
		stroke-width: 1.5;
		vector-effect: non-scaling-stroke;
	}
	.svg[data-lit] .node[data-state='dim'] {
		opacity: 0.25;
	}
	.ring {
		fill: none;
		stroke: var(--accent);
		stroke-width: 2.5;
		vector-effect: non-scaling-stroke;
		opacity: 0;
	}
	.node[data-state='lit'] .ring,
	.node[aria-pressed='true'] .ring {
		opacity: 1;
	}
	.node[role='button'] {
		cursor: pointer;
		outline: none;
	}
	.node[role='button']:focus-visible .ring {
		stroke-dasharray: 3 2;
		opacity: 1;
	}
	.labels {
		position: absolute;
		inset: 0;
		pointer-events: none;
		font-size: var(--text-11);
	}
	.labels span {
		position: absolute;
		color: var(--ink-2);
		white-space: nowrap;
		transform: translate(-50%, 6px);
		transition: opacity var(--dur-2) var(--ease);
	}
	.labels span[data-state='dim'] {
		opacity: 0.25;
	}
	.labels span[data-hull] {
		color: var(--ink-3);
		font-weight: var(--weight-medium);
		transform: translate(-50%, -100%);
	}
}

src/lib/components/charts/_kernel/graph.ts

import {
	forceCollide,
	forceLink,
	forceManyBody,
	forceSimulation,
	forceX,
	forceY,
	type SimulationNodeDatum
} from 'd3-force';

import { px } from './scale';

/* NetworkGraph's maths: layouts and geometry, all deterministic, so the
   server and the browser draw the same picture.

   A force layout is chaotic: a one-bit difference in step one grows into a
   visibly different graph. ECMAScript leaves cos, sin, hypot, exp, and log
   to each engine, so none of them appear inside the simulation — starting
   positions come from a hash, the simulation's randomness from a seeded
   generator, and distances from sqrt, which IEEE-754 specifies exactly. */

export type GraphNode = {
	id: string;
	label?: string;
	/** A class: sets colour and shape (by `groups` order), and the tier in a
	 *  tiered layout. */
	group?: string;
	/** A magnitude drawn as the node's area. */
	size?: number;
};

export type GraphEdge = {
	from: string;
	to: string;
	/** Signed, −1 to 1: hue is the sign, opacity the strength. */
	value?: number;
	/** Unsigned strength: drawn as width. */
	weight?: number;
	label?: string;
};

export type GraphLayout = 'force' | 'radial' | 'circular' | 'tiered' | 'flow' | 'grid';
export type Point = { x: number; y: number };

/** The virtual canvas layouts place nodes on. */
export const GRAPH_W = 1000;

/** FNV-1a → 0–1: a repeatable number per string. */
export function seedOf(text: string) {
	let h = 2166136261;
	for (let i = 0; i < text.length; i++) {
		h ^= text.charCodeAt(i);
		h = Math.imul(h, 16777619);
	}
	return (h >>> 0) / 4294967296;
}

/** A seeded linear congruential generator for the simulation's jiggle. */
function lcg(seed: number) {
	let s = Math.floor(seed * 4294967296) >>> 0 || 1;
	return () => {
		s = (Math.imul(1664525, s) + 1013904223) >>> 0;
		return s / 4294967296;
	};
}

/** Edges whose ends both exist; a dangling edge is ignored, not guessed. */
export function liveEdges(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const ids = new Set(nodes.map((n) => n.id));
	return edges.filter((e) => ids.has(e.from) && ids.has(e.to) && e.from !== e.to);
}

export function neighbours(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const near = new Map<string, Set<string>>(nodes.map((n) => [n.id, new Set()]));
	for (const e of edges) {
		near.get(e.from)?.add(e.to);
		near.get(e.to)?.add(e.from);
	}
	return near;
}

/** Hops from a root, walking edges both ways; unreached nodes go one ring
 *  beyond the furthest. */
export function hopsFrom(nodes: readonly GraphNode[], edges: readonly GraphEdge[], root: string) {
	const near = neighbours(nodes, edges);
	const depth = new Map<string, number>([[root, 0]]);
	let frontier = [root];
	while (frontier.length) {
		const next: string[] = [];
		for (const id of frontier)
			for (const other of near.get(id) ?? []) {
				if (depth.has(other)) continue;
				depth.set(other, (depth.get(id) ?? 0) + 1);
				next.push(other);
			}
		frontier = next;
	}
	const beyond = Math.max(0, ...depth.values()) + 1;
	for (const n of nodes) if (!depth.has(n.id)) depth.set(n.id, beyond);
	return depth;
}

/** Split edges into those that keep the graph acyclic and the "back"
 *  edges that close a loop, by depth-first search in input order: a loop is
 *  broken at the edge that closes it (c → a in a → b → c → a), not wherever
 *  a walk happens to land. */
export function splitLoops<E extends { from: string; to: string }>(
	nodes: readonly { id: string }[],
	edges: readonly E[]
) {
	const outgoing = new Map<string, E[]>(nodes.map((n) => [n.id, []]));
	for (const e of edges) outgoing.get(e.from)?.push(e);
	const state = new Map<string, 1 | 2>();
	const back = new Set<E>();
	const visit = (id: string) => {
		state.set(id, 1);
		for (const e of outgoing.get(id) ?? []) {
			const s = state.get(e.to);
			if (s === 1) back.add(e);
			else if (s === undefined) visit(e.to);
		}
		state.set(id, 2);
	};
	for (const n of nodes) if (!state.has(n.id)) visit(n.id);
	return {
		forward: edges.filter((e) => !back.has(e)),
		loops: edges.filter((e) => back.has(e))
	};
}

/** Longest path from any source, for flow layouts; loops are broken first
 *  (see splitLoops). */
export function longestPath(
	nodes: readonly { id: string }[],
	edges: readonly { from: string; to: string }[]
) {
	const { forward } = splitLoops(nodes, edges);
	const incoming = new Map<string, string[]>(nodes.map((n) => [n.id, []]));
	for (const e of forward) incoming.get(e.to)?.push(e.from);
	const depth = new Map<string, number>();
	const walk = (id: string): number => {
		const known = depth.get(id);
		if (known !== undefined) return known;
		const from = incoming.get(id) ?? [];
		const d = from.length ? Math.max(...from.map((f) => walk(f) + 1)) : 0;
		depth.set(id, d);
		return d;
	};
	for (const n of nodes) walk(n.id);
	return depth;
}

type Options = { root?: string; groups: readonly string[]; cluster?: boolean };

type Layout = (
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	height: number,
	options: Options
) => Map<string, Point>;

/** Where each group gathers when a force layout is clustered, as fractions
 *  of the canvas. A fixed table, not points on a circle: anything that feeds
 *  the simulation must avoid engine-dependent maths. */
const ANCHORS: readonly (readonly [number, number])[][] = [
	[[0.5, 0.5]],
	[
		[0.28, 0.5],
		[0.72, 0.5]
	],
	[
		[0.5, 0.26],
		[0.26, 0.72],
		[0.74, 0.72]
	],
	[
		[0.28, 0.28],
		[0.72, 0.28],
		[0.28, 0.72],
		[0.72, 0.72]
	],
	[
		[0.5, 0.2],
		[0.2, 0.45],
		[0.8, 0.45],
		[0.32, 0.8],
		[0.68, 0.8]
	]
];

const force: Layout = (nodes, edges, height, { groups, cluster }) => {
	type Sim = SimulationNodeDatum & { id: string };
	const sim: Sim[] = nodes.map((n) => ({
		id: n.id,
		x: GRAPH_W * (0.25 + seedOf(`${n.id}:x`) * 0.5),
		y: height * (0.25 + seedOf(`${n.id}:y`) * 0.5)
	}));
	const spacing = Math.sqrt((GRAPH_W * height) / Math.max(1, nodes.length));
	const simulation = forceSimulation(sim)
		.randomSource(lcg(seedOf(nodes.map((n) => n.id).join('|'))))
		.force(
			'link',
			forceLink<Sim, { source: string; target: string }>(
				edges.map((e) => ({ source: e.from, target: e.to }))
			)
				.id((d) => d.id)
				.distance(spacing * 0.55)
		)
		.force('charge', forceManyBody().strength(-spacing * 2))
		.force('collide', forceCollide(24))
		.stop();
	// Clustered, each group is drawn toward its own region (up to five
	// groups); otherwise everything is drawn gently toward the centre.
	const table = ANCHORS[Math.min(groups.length, ANCHORS.length) - 1];
	const groupOf = new Map(nodes.map((n) => [n.id, n.group ?? '']));
	const anchor = (id: string) => {
		const index = groups.indexOf(groupOf.get(id) ?? '');
		return cluster && table && index >= 0 && index < table.length ? table[index] : [0.5, 0.5];
	};
	const pull = cluster ? 0.18 : 0.06;
	simulation
		.force('x', forceX<Sim>((d) => anchor(d.id)[0] * GRAPH_W).strength(pull))
		.force('y', forceY<Sim>((d) => anchor(d.id)[1] * height).strength(pull * (GRAPH_W / height)));
	simulation.tick(300);
	return fit(new Map(sim.map((n) => [n.id, { x: n.x ?? 0, y: n.y ?? 0 }])), height);
};

/** Scale positions uniformly (so shapes keep their proportions) to fill the
 *  canvas, less a margin for labels. */
function fit(points: Map<string, Point>, height: number, margin = 70) {
	if (points.size < 2)
		return new Map([...points].map(([id]) => [id, { x: GRAPH_W / 2, y: height / 2 }]));
	const xs = [...points.values()].map((p) => p.x);
	const ys = [...points.values()].map((p) => p.y);
	const [x0, x1, y0, y1] = [Math.min(...xs), Math.max(...xs), Math.min(...ys), Math.max(...ys)];
	const scale = Math.min(
		(GRAPH_W - 2 * margin) / Math.max(1, x1 - x0),
		(height - 2 * margin) / Math.max(1, y1 - y0)
	);
	const ox = (GRAPH_W - (x1 - x0) * scale) / 2;
	const oy = (height - (y1 - y0) * scale) / 2;
	return new Map(
		[...points].map(([id, p]) => [
			id,
			{ x: px(ox + (p.x - x0) * scale), y: px(oy + (p.y - y0) * scale) }
		])
	);
}

const circle = (count: number, index: number, cx: number, cy: number, r: number, turn = 0) => {
	const angle = (index / Math.max(1, count)) * 2 * Math.PI - Math.PI / 2 + turn;
	return { x: px(cx + r * Math.cos(angle)), y: px(cy + r * Math.sin(angle)) };
};

const radial: Layout = (nodes, edges, height, { root }) => {
	const centre = root ?? nodes[0]?.id ?? '';
	const depth = hopsFrom(nodes, edges, centre);
	const near = neighbours(nodes, edges);
	const rings = new Map<number, string[]>();
	for (const n of nodes) {
		if (n.id === centre) continue;
		const d = depth.get(n.id) ?? 1;
		rings.set(d, [...(rings.get(d) ?? []), n.id]);
	}
	const out = new Map<string, Point>([[centre, { x: GRAPH_W / 2, y: height / 2 }]]);
	// Turns around the centre, per node, so a ring can follow the one inside.
	const turn = new Map<string, number>([[centre, 0]]);
	const count = Math.max(1, rings.size);
	const outer = Math.min(GRAPH_W, height) / 2 - 50;
	for (const [ring, ids] of [...rings].sort((a, b) => a[0] - b[0])) {
		// Order a ring by where its parent sits, so children stay beside their
		// parent and edges do not cross the middle.
		const parentTurn = (id: string) => {
			const parents = [...(near.get(id) ?? [])].filter(
				(p) => turn.has(p) && (depth.get(p) ?? 0) < ring
			);
			return parents.length ? Math.min(...parents.map((p) => turn.get(p)!)) : 1;
		};
		const ordered = [...ids].sort((a, b) => parentTurn(a) - parentTurn(b) || a.localeCompare(b));
		const r = (outer * ring) / count;
		ordered.forEach((id, i) => {
			const t = (i + 0.5) / ordered.length;
			turn.set(id, t);
			out.set(id, circle(1, 0, GRAPH_W / 2, height / 2, r, t * 2 * Math.PI));
		});
	}
	return out;
};

const circular: Layout = (nodes, _edges, height) => {
	const r = Math.min(GRAPH_W, height) / 2 - 40;
	return new Map(nodes.map((n, i) => [n.id, circle(nodes.length, i, GRAPH_W / 2, height / 2, r)]));
};

const tiered: Layout = (nodes, _edges, height, { groups }) => {
	const order = [...new Set([...groups, ...nodes.map((n) => n.group ?? '')])].filter((g) =>
		nodes.some((n) => (n.group ?? '') === g)
	);
	const out = new Map<string, Point>();
	order.forEach((group, column) => {
		const ids = nodes.filter((n) => (n.group ?? '') === group).map((n) => n.id);
		const x =
			order.length === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (order.length - 1);
		ids.forEach((id, i) => out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) }));
	});
	return out;
};

const flow: Layout = (nodes, edges, height) => {
	const depth = longestPath(nodes, edges);
	const columns = new Map<number, string[]>();
	for (const n of nodes) {
		const d = depth.get(n.id) ?? 0;
		columns.set(d, [...(columns.get(d) ?? []), n.id]);
	}
	const count = Math.max(1, columns.size);
	const out = new Map<string, Point>();
	[...columns]
		.sort((a, b) => a[0] - b[0])
		.forEach(([, ids], column) => {
			const x = count === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (count - 1);
			ids.forEach((id, i) =>
				out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) })
			);
		});
	return out;
};

const grid: Layout = (nodes, _edges, height) => {
	const cols = Math.max(1, Math.ceil(Math.sqrt(nodes.length * (GRAPH_W / height))));
	const rows = Math.max(1, Math.ceil(nodes.length / cols));
	return new Map(
		nodes.map((n, i) => [
			n.id,
			{
				x: px((((i % cols) + 1) * GRAPH_W) / (cols + 1)),
				y: px(((Math.floor(i / cols) + 1) * height) / (rows + 1))
			}
		])
	);
};

const LAYOUTS: Record<GraphLayout, Layout> = {
	force,
	radial,
	circular,
	tiered,
	flow,
	grid
};

/** Every node's position, as a record for tweening: `${id}|x`, `${id}|y`. */
export function graphTarget(
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	layout: GraphLayout,
	aspect: number,
	options: Options
) {
	const height = GRAPH_W / aspect;
	const placed = nodes.length ? LAYOUTS[layout](nodes, edges, height, options) : new Map();
	const target: Record<string, number> = {};
	for (const [id, p] of placed) {
		target[`${id}|x`] = p.x;
		target[`${id}|y`] = p.y;
	}
	return target;
}

/** A straight edge, or a shallow arc that bows with length — straight for
 *  radial layouts, arcs where chords would overlap into a disc. */
export function edgePath(a: Point, b: Point, curved: boolean) {
	if (!curved) return `M${px(a.x)},${px(a.y)}L${px(b.x)},${px(b.y)}`;
	const dx = b.x - a.x;
	const dy = b.y - a.y;
	const distance = Math.sqrt(dx * dx + dy * dy) || 1;
	const bow = Math.min(distance * 0.18, 60);
	const mx = (a.x + b.x) / 2 - (dy / distance) * bow;
	const my = (a.y + b.y) / 2 + (dx / distance) * bow;
	return `M${px(a.x)},${px(a.y)}Q${px(mx)},${px(my)} ${px(b.x)},${px(b.y)}`;
}

/** An ellipse around a set of positions, for a labelled group (a hull). */
export function hullAround(points: readonly Point[]) {
	if (!points.length) return null;
	const cx = points.reduce((sum, p) => sum + p.x, 0) / points.length;
	const cy = points.reduce((sum, p) => sum + p.y, 0) / points.length;
	const r =
		Math.max(
			34,
			...points.map((p) => {
				const dx = p.x - cx;
				const dy = p.y - cy;
				return Math.sqrt(dx * dx + dy * dy);
			})
		) + 30;
	return { cx: px(cx), cy: px(cy), rx: px(r * 1.12), ry: px(r) };
}

src/lib/components/charts/network-graph/doc.ts

/**
 * NetworkGraph — things and the connections between them.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § CONTRACT — the oracle. Names no library, contains no code.              │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * # Shape
 *
 *     label         REQUIRED
 *     nodes         { id, label?, group?, size? }[]
 *     edges         { from, to, value? (signed −1–1), weight?, label? }[]
 *     layout?       "force" (default) | "radial" | "circular" | "tiered" |
 *                   "flow" | "grid"
 *     root?         the centre of a radial layout
 *     groups?       groups in a FIXED order: colour, shape, and tiers
 *     curved?, labels?, hulls? ({ key, label?, ids }[])
 *     onSelect?, selected?   selection
 *     aspect?, formatValue?, animation?  (default: nodes pop in)
 *
 * # Behaviour
 *
 * R1  The same input always gives the same picture, on the server and in
 *     every browser: layouts are deterministic.
 * R2  Position means what the layout says: force — nearness is a hint;
 *     radial — the ring is hops from the root; circular — nothing (so no
 *     node hides another); tiered — the group; flow — columns by longest
 *     path, every edge pointing forward; grid — nothing, in rows.
 * R3  Groups have a colour AND a shape. Size is drawn as area.
 * R4  A signed edge's hue is its sign and its opacity its strength; a
 *     weight is its width. An edge to a node that does not exist is ignored.
 * R5  Hover or focus lights a node and its neighbours and dims the rest.
 *     Selection is one tab stop: arrow keys move, Enter or Space selects,
 *     Escape clears.
 * R6  Changing the layout (or the data) moves nodes to their new places;
 *     a new node appears where it belongs.
 * R7  With hulls, the force layout gathers each group into its own region
 *     (up to five groups), so a hull outlines a place, not a scatter.
 * R8  Two tables list every node (with its connections) and every edge.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § MECHANICS — how this implementation meets the contract.                 │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * The force layout is d3-force, run synchronously for a fixed number of
 * ticks with hash-seeded starting positions and a seeded random source. A
 * force simulation is chaotic, and ECMAScript leaves cos, sin, hypot, exp,
 * and log to each engine, so none run inside it (d3's only trigonometry is
 * the starting spiral, which seeded positions replace); sqrt and arithmetic
 * are exactly specified by IEEE-754. Labels are HTML placed by percentage.
 */
export {};

src/lib/components/charts/network-graph/NetworkGraph.svelte

<script lang="ts">
	import { TBody, Td, Th, THead, Tr } from '$lib/components/display/table';
	import type { AnimationProp } from '$lib/motion';
	import { chartMotion, Tweened } from '$lib/motion/svelte.svelte';
	import { cn } from '$lib/utils/cn';
	import ChartLegend from '../chart-legend/ChartLegend.svelte';
	import { radiusFor, shapePath } from '../_kernel/encode';
	import { formatExact } from '../_kernel/format';
	import {
		edgePath,
		graphTarget,
		hullAround,
		liveEdges,
		neighbours,
		type GraphEdge,
		type GraphLayout,
		type GraphNode,
		type Point
	} from '../_kernel/graph';
	import { px } from '../_kernel/scale';
	import { categoryColor, seriesShape } from '../_kernel/scatter';
	import ChartData from '../_shared/ChartData.svelte';
	import chart from '../_shared/chart.module.css';
	import styles from './network-graph.module.css';

	/* Things and the connections between them. What position means depends on
	   the layout — a force layout's nearness is a hint, a radial ring is a hop
	   count — so choose the layout for the question. Hover or focus a node to
	   light its neighbours; the tables list every node and connection. */
	let {
		label,
		nodes,
		edges: rawEdges,
		layout = 'force',
		root,
		groups: groupOrder,
		curved = false,
		labels = true,
		hulls = [],
		onSelect,
		selected = null,
		aspect = 1.6,
		formatValue = formatExact,
		animation,
		class: className = ''
	}: {
		/** Names the chart. */
		label: string;
		nodes: readonly GraphNode[];
		edges: readonly GraphEdge[];
		/** How position is decided — and so what it means. */
		layout?: GraphLayout;
		/** The centre of a radial layout. */
		root?: string;
		/** Groups in a FIXED order: colour, shape, and tiers. */
		groups?: readonly string[];
		/** Bow edges into arcs, where straight chords would overlap. */
		curved?: boolean;
		/** Print node names; off for dense graphs. */
		labels?: boolean;
		/** Labelled regions drawn behind groups of nodes. */
		hulls?: readonly { key: string; label?: string; ids: readonly string[] }[];
		/** Makes nodes selectable: one tab stop, arrow keys move between nodes. */
		onSelect?: (id: string | null) => void;
		selected?: string | null;
		/** Width over height. */
		aspect?: number;
		formatValue?: (value: number) => string;
		/** Default: nodes pop in; changing the layout glides them to their new places. */
		animation?: AnimationProp;
		class?: string;
	} = $props();

	const motion = chartMotion(() => animation, { enter: 'pop', axis: 'y' });
	const edges = $derived(liveEdges(nodes, rawEdges));
	const groups = $derived(
		groupOrder ?? [...new Set(nodes.map((n) => n.group ?? ''))].filter(Boolean)
	);
	// The layout is computed once per input, not per hover or tween frame.
	const target = $derived(
		graphTarget(nodes, edges, layout, aspect, { root, groups, cluster: hulls.length > 0 })
	);
	const shown = new Tweened(
		() => target,
		() => motion.update,
		'target'
	);
	const near = $derived(neighbours(nodes, edges));

	let pointed = $state<string | null>(null);
	let active = $state(0);
	let svg = $state<SVGSVGElement>();
	const lit = $derived(pointed ?? selected);
	const stateOf = (id: string) =>
		lit === null ? undefined : id === lit ? 'lit' : near.get(lit)?.has(id) ? 'near' : 'dim';

	const at = (id: string): Point | null => {
		const x = shown.current[`${id}|x`];
		const y = shown.current[`${id}|y`];
		return x === undefined || y === undefined ? null : { x, y };
	};
	// The frame fits the laid-out nodes, with room for their labels.
	const bounds = $derived.by(() => {
		const finals = nodes.flatMap((n) => {
			const x = target[`${n.id}|x`];
			const y = target[`${n.id}|y`];
			return x === undefined ? [] : [{ x, y }];
		});
		const left = Math.min(0, ...finals.map((p) => p.x)) - 60;
		const right = Math.max(1000, ...finals.map((p) => p.x)) + 60;
		const top = Math.min(0, ...finals.map((p) => p.y)) - 50;
		const bottom = Math.max(1000 / aspect, ...finals.map((p) => p.y)) + 50;
		return { left, top, width: right - left, height: bottom - top };
	});
	const pct = (p: Point) =>
		`left:${((p.x - bounds.left) / bounds.width) * 100}%;top:${((p.y - bounds.top) / bounds.height) * 100}%`;

	const sizes = $derived(
		nodes.map((n) => n.size).filter((s): s is number => typeof s === 'number' && s > 0)
	);
	const range = $derived<[number, number]>(
		sizes.length ? [Math.min(...sizes), Math.max(...sizes)] : [1, 1]
	);
	const radius = (n: GraphNode) => (n.size && n.size > 0 ? radiusFor(n.size, range, [9, 26]) : 11);
	const maxWeight = $derived(Math.max(1, ...edges.map((e) => e.weight ?? 0)));
	const degree = (id: string) => near.get(id)?.size ?? 0;
	const name = (id: string) => nodes.find((n) => n.id === id)?.label ?? id;
	const hullColors = $derived(hulls.map((h) => h.key));

	const select = (id: string) => onSelect?.(selected === id ? null : id);
	function move(event: KeyboardEvent) {
		if (!onSelect) return;
		if (event.key === 'Escape') {
			onSelect(null);
			return;
		}
		const step = (
			{ ArrowRight: 1, ArrowDown: 1, ArrowLeft: -1, ArrowUp: -1 } as Record<string, number>
		)[event.key];
		if (step === undefined) return;
		event.preventDefault();
		const next = (active + step + nodes.length) % nodes.length;
		active = next;
		svg?.querySelector<SVGGElement>(`[data-index="${next}"]`)?.focus();
	}
</script>

{#if !nodes.length}
	<div class={cn(chart.root, className)}>
		<p class={chart.empty}>No data to display.</p>
	</div>
{:else}
	<div {...motion.pending} {@attach motion.attach} class={cn(chart.root, className)}>
		{#if groups.length > 1}
			<ChartLegend
				items={groups.map((group) => ({
					key: group,
					label: group,
					color: categoryColor(groups, group),
					shape: seriesShape(groups, group)
				}))}
			/>
		{/if}
		<div class={styles.frame} style:--aspect={bounds.width / bounds.height}>
			<svg
				bind:this={svg}
				class={styles.svg}
				viewBox="{px(bounds.left)} {px(bounds.top)} {px(bounds.width)} {px(bounds.height)}"
				role={onSelect ? 'group' : 'img'}
				aria-label="{label}. Every node and connection is in the data tables."
				data-lit={lit ? '' : undefined}
				onkeydown={onSelect ? move : undefined}
			>
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape}
						<ellipse
							class={styles.hull}
							style:--series={categoryColor(hullColors, hull.key)}
							cx={shape.cx}
							cy={shape.cy}
							rx={shape.rx}
							ry={shape.ry}
						/>
					{/if}
				{/each}
				{#each edges as edge, index (`${edge.from}-${edge.to}-${index}`)}
					{@const a = at(edge.from)}
					{@const b = at(edge.to)}
					{#if a && b}
						{@const signed = typeof edge.value === 'number'}
						<path
							class={styles.edge}
							d={edgePath(a, b, curved)}
							data-lit={lit !== null && (edge.from === lit || edge.to === lit) ? '' : undefined}
							data-sign={signed
								? (edge.value as number) < 0
									? 'negative'
									: 'positive'
								: undefined}
							style:--edge-w={1 + ((edge.weight ?? 0) / maxWeight) * 3}
							style:--edge-o={signed
								? 0.25 + Math.min(1, Math.abs(edge.value as number)) * 0.65
								: undefined}
						/>
					{/if}
				{/each}
				{#each nodes as node, index (node.id)}
					{@const p = at(node.id)}
					{#if p}
						{@const r = radius(node)}
						<g transform="translate({px(p.x)} {px(p.y)})">
							{#if onSelect}
								<g
									data-mark
									data-index={index}
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									role="button"
									tabindex={index === active ? 0 : -1}
									aria-label="{node.label ?? node.id}{node.group ? `, ${node.group}` : ''}, {degree(
										node.id
									)} connections"
									aria-pressed={selected === node.id}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
									onfocus={() => {
										pointed = node.id;
										active = index;
									}}
									onblur={() => (pointed = null)}
									onclick={() => select(node.id)}
									onkeydown={(event) => {
										if (event.key === 'Enter' || event.key === ' ') {
											event.preventDefault();
											select(node.id);
										}
									}}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{:else}
								<!-- svelte-ignore a11y_no_static_element_interactions -->
								<g
									data-mark
									data-state={stateOf(node.id)}
									class={styles.node}
									style:--series={categoryColor(groups, node.group)}
									onpointerenter={() => (pointed = node.id)}
									onpointerleave={() => (pointed = null)}
								>
									<circle class={styles.ring} r={r + 5} />
									<path class={styles.shape} d={shapePath(seriesShape(groups, node.group), r)} />
								</g>
							{/if}
						</g>
					{/if}
				{/each}
			</svg>
			<div class={styles.labels} aria-hidden="true">
				{#each hulls as hull (hull.key)}
					{@const shape = hullAround(hull.ids.flatMap((id) => at(id) ?? []))}
					{#if shape && hull.label}
						<span data-hull style={pct({ x: shape.cx, y: shape.cy - shape.ry })}>{hull.label}</span>
					{/if}
				{/each}
				{#if labels}
					{#each nodes as node (node.id)}
						{@const p = at(node.id)}
						{#if p}
							<span data-state={stateOf(node.id)} style={pct({ x: p.x, y: p.y + radius(node) })}
								>{node.label ?? node.id}</span
							>
						{/if}
					{/each}
				{/if}
			</div>
		</div>
		<ChartData {label} summary="View nodes">
			<THead>
				<Tr>
					<Th>Node</Th><Th>Group</Th><Th numeric>Connections</Th>
					{#if sizes.length}<Th numeric>Size</Th>{/if}
				</Tr>
			</THead>
			<TBody>
				{#each nodes as node (node.id)}
					<Tr>
						<Th scope="row">{node.label ?? node.id}</Th>
						<Td>{node.group ?? '—'}</Td>
						<Td numeric>{degree(node.id)}</Td>
						{#if sizes.length}
							<Td numeric>{typeof node.size === 'number' ? formatValue(node.size) : '—'}</Td>
						{/if}
					</Tr>
				{/each}
			</TBody>
		</ChartData>
		<ChartData {label} summary="View connections">
			<THead>
				<Tr><Th>From</Th><Th>To</Th><Th numeric>Value</Th></Tr>
			</THead>
			<TBody>
				{#each edges as edge, index (index)}
					{@const value = edge.value ?? edge.weight}
					<Tr>
						<Th scope="row">{name(edge.from)}</Th>
						<Td>{name(edge.to)}</Td>
						<Td numeric>{typeof value === 'number' ? formatValue(value) : '—'}</Td>
					</Tr>
				{/each}
			</TBody>
		</ChartData>
	</div>
{/if}

src/lib/components/charts/network-graph/network-graph.module.css

@layer primitive {
	.frame {
		position: relative;
		width: 100%;
		aspect-ratio: var(--aspect, 1.6);
	}
	.svg {
		position: absolute;
		inset: 0;
		width: 100%;
		height: 100%;
		overflow: visible;
	}
	.hull {
		fill: color-mix(in oklab, var(--series) 12%, transparent);
		stroke: color-mix(in oklab, var(--series) 45%, transparent);
		stroke-dasharray: 4 4;
		stroke-width: 1;
		vector-effect: non-scaling-stroke;
	}
	.edge {
		fill: none;
		stroke: var(--chart-axis, var(--line-strong));
		stroke-opacity: 0.7;
		stroke-width: var(--edge-w, 1.25);
		vector-effect: non-scaling-stroke;
		transition: stroke-opacity var(--dur-2) var(--ease);
	}
	.edge[data-sign='positive'] {
		stroke: var(--chart-pos);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.edge[data-sign='negative'] {
		stroke: var(--chart-neg);
		stroke-opacity: var(--edge-o, 0.7);
	}
	.svg[data-lit] .edge:not([data-lit]) {
		stroke-opacity: 0.12;
	}
	.node {
		transform-origin: center;
		transition: opacity var(--dur-2) var(--ease);
	}
	.shape {
		fill: var(--series);
		stroke: var(--surface-panel);
		stroke-width: 1.5;
		vector-effect: non-scaling-stroke;
	}
	.svg[data-lit] .node[data-state='dim'] {
		opacity: 0.25;
	}
	.ring {
		fill: none;
		stroke: var(--accent);
		stroke-width: 2.5;
		vector-effect: non-scaling-stroke;
		opacity: 0;
	}
	.node[data-state='lit'] .ring,
	.node[aria-pressed='true'] .ring {
		opacity: 1;
	}
	.node[role='button'] {
		cursor: pointer;
		outline: none;
	}
	.node[role='button']:focus-visible .ring {
		stroke-dasharray: 3 2;
		opacity: 1;
	}
	.labels {
		position: absolute;
		inset: 0;
		pointer-events: none;
		font-size: var(--text-11);
	}
	.labels span {
		position: absolute;
		color: var(--ink-2);
		white-space: nowrap;
		transform: translate(-50%, 6px);
		transition: opacity var(--dur-2) var(--ease);
	}
	.labels span[data-state='dim'] {
		opacity: 0.25;
	}
	.labels span[data-hull] {
		color: var(--ink-3);
		font-weight: var(--weight-medium);
		transform: translate(-50%, -100%);
	}
}

src/lib/components/charts/_kernel/graph.ts

import {
	forceCollide,
	forceLink,
	forceManyBody,
	forceSimulation,
	forceX,
	forceY,
	type SimulationNodeDatum
} from 'd3-force';

import { px } from './scale';

/* NetworkGraph's maths: layouts and geometry, all deterministic, so the
   server and the browser draw the same picture.

   A force layout is chaotic: a one-bit difference in step one grows into a
   visibly different graph. ECMAScript leaves cos, sin, hypot, exp, and log
   to each engine, so none of them appear inside the simulation — starting
   positions come from a hash, the simulation's randomness from a seeded
   generator, and distances from sqrt, which IEEE-754 specifies exactly. */

export type GraphNode = {
	id: string;
	label?: string;
	/** A class: sets colour and shape (by `groups` order), and the tier in a
	 *  tiered layout. */
	group?: string;
	/** A magnitude drawn as the node's area. */
	size?: number;
};

export type GraphEdge = {
	from: string;
	to: string;
	/** Signed, −1 to 1: hue is the sign, opacity the strength. */
	value?: number;
	/** Unsigned strength: drawn as width. */
	weight?: number;
	label?: string;
};

export type GraphLayout = 'force' | 'radial' | 'circular' | 'tiered' | 'flow' | 'grid';
export type Point = { x: number; y: number };

/** The virtual canvas layouts place nodes on. */
export const GRAPH_W = 1000;

/** FNV-1a → 0–1: a repeatable number per string. */
export function seedOf(text: string) {
	let h = 2166136261;
	for (let i = 0; i < text.length; i++) {
		h ^= text.charCodeAt(i);
		h = Math.imul(h, 16777619);
	}
	return (h >>> 0) / 4294967296;
}

/** A seeded linear congruential generator for the simulation's jiggle. */
function lcg(seed: number) {
	let s = Math.floor(seed * 4294967296) >>> 0 || 1;
	return () => {
		s = (Math.imul(1664525, s) + 1013904223) >>> 0;
		return s / 4294967296;
	};
}

/** Edges whose ends both exist; a dangling edge is ignored, not guessed. */
export function liveEdges(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const ids = new Set(nodes.map((n) => n.id));
	return edges.filter((e) => ids.has(e.from) && ids.has(e.to) && e.from !== e.to);
}

export function neighbours(nodes: readonly GraphNode[], edges: readonly GraphEdge[]) {
	const near = new Map<string, Set<string>>(nodes.map((n) => [n.id, new Set()]));
	for (const e of edges) {
		near.get(e.from)?.add(e.to);
		near.get(e.to)?.add(e.from);
	}
	return near;
}

/** Hops from a root, walking edges both ways; unreached nodes go one ring
 *  beyond the furthest. */
export function hopsFrom(nodes: readonly GraphNode[], edges: readonly GraphEdge[], root: string) {
	const near = neighbours(nodes, edges);
	const depth = new Map<string, number>([[root, 0]]);
	let frontier = [root];
	while (frontier.length) {
		const next: string[] = [];
		for (const id of frontier)
			for (const other of near.get(id) ?? []) {
				if (depth.has(other)) continue;
				depth.set(other, (depth.get(id) ?? 0) + 1);
				next.push(other);
			}
		frontier = next;
	}
	const beyond = Math.max(0, ...depth.values()) + 1;
	for (const n of nodes) if (!depth.has(n.id)) depth.set(n.id, beyond);
	return depth;
}

/** Split edges into those that keep the graph acyclic and the "back"
 *  edges that close a loop, by depth-first search in input order: a loop is
 *  broken at the edge that closes it (c → a in a → b → c → a), not wherever
 *  a walk happens to land. */
export function splitLoops<E extends { from: string; to: string }>(
	nodes: readonly { id: string }[],
	edges: readonly E[]
) {
	const outgoing = new Map<string, E[]>(nodes.map((n) => [n.id, []]));
	for (const e of edges) outgoing.get(e.from)?.push(e);
	const state = new Map<string, 1 | 2>();
	const back = new Set<E>();
	const visit = (id: string) => {
		state.set(id, 1);
		for (const e of outgoing.get(id) ?? []) {
			const s = state.get(e.to);
			if (s === 1) back.add(e);
			else if (s === undefined) visit(e.to);
		}
		state.set(id, 2);
	};
	for (const n of nodes) if (!state.has(n.id)) visit(n.id);
	return {
		forward: edges.filter((e) => !back.has(e)),
		loops: edges.filter((e) => back.has(e))
	};
}

/** Longest path from any source, for flow layouts; loops are broken first
 *  (see splitLoops). */
export function longestPath(
	nodes: readonly { id: string }[],
	edges: readonly { from: string; to: string }[]
) {
	const { forward } = splitLoops(nodes, edges);
	const incoming = new Map<string, string[]>(nodes.map((n) => [n.id, []]));
	for (const e of forward) incoming.get(e.to)?.push(e.from);
	const depth = new Map<string, number>();
	const walk = (id: string): number => {
		const known = depth.get(id);
		if (known !== undefined) return known;
		const from = incoming.get(id) ?? [];
		const d = from.length ? Math.max(...from.map((f) => walk(f) + 1)) : 0;
		depth.set(id, d);
		return d;
	};
	for (const n of nodes) walk(n.id);
	return depth;
}

type Options = { root?: string; groups: readonly string[]; cluster?: boolean };

type Layout = (
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	height: number,
	options: Options
) => Map<string, Point>;

/** Where each group gathers when a force layout is clustered, as fractions
 *  of the canvas. A fixed table, not points on a circle: anything that feeds
 *  the simulation must avoid engine-dependent maths. */
const ANCHORS: readonly (readonly [number, number])[][] = [
	[[0.5, 0.5]],
	[
		[0.28, 0.5],
		[0.72, 0.5]
	],
	[
		[0.5, 0.26],
		[0.26, 0.72],
		[0.74, 0.72]
	],
	[
		[0.28, 0.28],
		[0.72, 0.28],
		[0.28, 0.72],
		[0.72, 0.72]
	],
	[
		[0.5, 0.2],
		[0.2, 0.45],
		[0.8, 0.45],
		[0.32, 0.8],
		[0.68, 0.8]
	]
];

const force: Layout = (nodes, edges, height, { groups, cluster }) => {
	type Sim = SimulationNodeDatum & { id: string };
	const sim: Sim[] = nodes.map((n) => ({
		id: n.id,
		x: GRAPH_W * (0.25 + seedOf(`${n.id}:x`) * 0.5),
		y: height * (0.25 + seedOf(`${n.id}:y`) * 0.5)
	}));
	const spacing = Math.sqrt((GRAPH_W * height) / Math.max(1, nodes.length));
	const simulation = forceSimulation(sim)
		.randomSource(lcg(seedOf(nodes.map((n) => n.id).join('|'))))
		.force(
			'link',
			forceLink<Sim, { source: string; target: string }>(
				edges.map((e) => ({ source: e.from, target: e.to }))
			)
				.id((d) => d.id)
				.distance(spacing * 0.55)
		)
		.force('charge', forceManyBody().strength(-spacing * 2))
		.force('collide', forceCollide(24))
		.stop();
	// Clustered, each group is drawn toward its own region (up to five
	// groups); otherwise everything is drawn gently toward the centre.
	const table = ANCHORS[Math.min(groups.length, ANCHORS.length) - 1];
	const groupOf = new Map(nodes.map((n) => [n.id, n.group ?? '']));
	const anchor = (id: string) => {
		const index = groups.indexOf(groupOf.get(id) ?? '');
		return cluster && table && index >= 0 && index < table.length ? table[index] : [0.5, 0.5];
	};
	const pull = cluster ? 0.18 : 0.06;
	simulation
		.force('x', forceX<Sim>((d) => anchor(d.id)[0] * GRAPH_W).strength(pull))
		.force('y', forceY<Sim>((d) => anchor(d.id)[1] * height).strength(pull * (GRAPH_W / height)));
	simulation.tick(300);
	return fit(new Map(sim.map((n) => [n.id, { x: n.x ?? 0, y: n.y ?? 0 }])), height);
};

/** Scale positions uniformly (so shapes keep their proportions) to fill the
 *  canvas, less a margin for labels. */
function fit(points: Map<string, Point>, height: number, margin = 70) {
	if (points.size < 2)
		return new Map([...points].map(([id]) => [id, { x: GRAPH_W / 2, y: height / 2 }]));
	const xs = [...points.values()].map((p) => p.x);
	const ys = [...points.values()].map((p) => p.y);
	const [x0, x1, y0, y1] = [Math.min(...xs), Math.max(...xs), Math.min(...ys), Math.max(...ys)];
	const scale = Math.min(
		(GRAPH_W - 2 * margin) / Math.max(1, x1 - x0),
		(height - 2 * margin) / Math.max(1, y1 - y0)
	);
	const ox = (GRAPH_W - (x1 - x0) * scale) / 2;
	const oy = (height - (y1 - y0) * scale) / 2;
	return new Map(
		[...points].map(([id, p]) => [
			id,
			{ x: px(ox + (p.x - x0) * scale), y: px(oy + (p.y - y0) * scale) }
		])
	);
}

const circle = (count: number, index: number, cx: number, cy: number, r: number, turn = 0) => {
	const angle = (index / Math.max(1, count)) * 2 * Math.PI - Math.PI / 2 + turn;
	return { x: px(cx + r * Math.cos(angle)), y: px(cy + r * Math.sin(angle)) };
};

const radial: Layout = (nodes, edges, height, { root }) => {
	const centre = root ?? nodes[0]?.id ?? '';
	const depth = hopsFrom(nodes, edges, centre);
	const near = neighbours(nodes, edges);
	const rings = new Map<number, string[]>();
	for (const n of nodes) {
		if (n.id === centre) continue;
		const d = depth.get(n.id) ?? 1;
		rings.set(d, [...(rings.get(d) ?? []), n.id]);
	}
	const out = new Map<string, Point>([[centre, { x: GRAPH_W / 2, y: height / 2 }]]);
	// Turns around the centre, per node, so a ring can follow the one inside.
	const turn = new Map<string, number>([[centre, 0]]);
	const count = Math.max(1, rings.size);
	const outer = Math.min(GRAPH_W, height) / 2 - 50;
	for (const [ring, ids] of [...rings].sort((a, b) => a[0] - b[0])) {
		// Order a ring by where its parent sits, so children stay beside their
		// parent and edges do not cross the middle.
		const parentTurn = (id: string) => {
			const parents = [...(near.get(id) ?? [])].filter(
				(p) => turn.has(p) && (depth.get(p) ?? 0) < ring
			);
			return parents.length ? Math.min(...parents.map((p) => turn.get(p)!)) : 1;
		};
		const ordered = [...ids].sort((a, b) => parentTurn(a) - parentTurn(b) || a.localeCompare(b));
		const r = (outer * ring) / count;
		ordered.forEach((id, i) => {
			const t = (i + 0.5) / ordered.length;
			turn.set(id, t);
			out.set(id, circle(1, 0, GRAPH_W / 2, height / 2, r, t * 2 * Math.PI));
		});
	}
	return out;
};

const circular: Layout = (nodes, _edges, height) => {
	const r = Math.min(GRAPH_W, height) / 2 - 40;
	return new Map(nodes.map((n, i) => [n.id, circle(nodes.length, i, GRAPH_W / 2, height / 2, r)]));
};

const tiered: Layout = (nodes, _edges, height, { groups }) => {
	const order = [...new Set([...groups, ...nodes.map((n) => n.group ?? '')])].filter((g) =>
		nodes.some((n) => (n.group ?? '') === g)
	);
	const out = new Map<string, Point>();
	order.forEach((group, column) => {
		const ids = nodes.filter((n) => (n.group ?? '') === group).map((n) => n.id);
		const x =
			order.length === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (order.length - 1);
		ids.forEach((id, i) => out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) }));
	});
	return out;
};

const flow: Layout = (nodes, edges, height) => {
	const depth = longestPath(nodes, edges);
	const columns = new Map<number, string[]>();
	for (const n of nodes) {
		const d = depth.get(n.id) ?? 0;
		columns.set(d, [...(columns.get(d) ?? []), n.id]);
	}
	const count = Math.max(1, columns.size);
	const out = new Map<string, Point>();
	[...columns]
		.sort((a, b) => a[0] - b[0])
		.forEach(([, ids], column) => {
			const x = count === 1 ? GRAPH_W / 2 : 60 + (column * (GRAPH_W - 120)) / (count - 1);
			ids.forEach((id, i) =>
				out.set(id, { x: px(x), y: px(((i + 1) * height) / (ids.length + 1)) })
			);
		});
	return out;
};

const grid: Layout = (nodes, _edges, height) => {
	const cols = Math.max(1, Math.ceil(Math.sqrt(nodes.length * (GRAPH_W / height))));
	const rows = Math.max(1, Math.ceil(nodes.length / cols));
	return new Map(
		nodes.map((n, i) => [
			n.id,
			{
				x: px((((i % cols) + 1) * GRAPH_W) / (cols + 1)),
				y: px(((Math.floor(i / cols) + 1) * height) / (rows + 1))
			}
		])
	);
};

const LAYOUTS: Record<GraphLayout, Layout> = {
	force,
	radial,
	circular,
	tiered,
	flow,
	grid
};

/** Every node's position, as a record for tweening: `${id}|x`, `${id}|y`. */
export function graphTarget(
	nodes: readonly GraphNode[],
	edges: readonly GraphEdge[],
	layout: GraphLayout,
	aspect: number,
	options: Options
) {
	const height = GRAPH_W / aspect;
	const placed = nodes.length ? LAYOUTS[layout](nodes, edges, height, options) : new Map();
	const target: Record<string, number> = {};
	for (const [id, p] of placed) {
		target[`${id}|x`] = p.x;
		target[`${id}|y`] = p.y;
	}
	return target;
}

/** A straight edge, or a shallow arc that bows with length — straight for
 *  radial layouts, arcs where chords would overlap into a disc. */
export function edgePath(a: Point, b: Point, curved: boolean) {
	if (!curved) return `M${px(a.x)},${px(a.y)}L${px(b.x)},${px(b.y)}`;
	const dx = b.x - a.x;
	const dy = b.y - a.y;
	const distance = Math.sqrt(dx * dx + dy * dy) || 1;
	const bow = Math.min(distance * 0.18, 60);
	const mx = (a.x + b.x) / 2 - (dy / distance) * bow;
	const my = (a.y + b.y) / 2 + (dx / distance) * bow;
	return `M${px(a.x)},${px(a.y)}Q${px(mx)},${px(my)} ${px(b.x)},${px(b.y)}`;
}

/** An ellipse around a set of positions, for a labelled group (a hull). */
export function hullAround(points: readonly Point[]) {
	if (!points.length) return null;
	const cx = points.reduce((sum, p) => sum + p.x, 0) / points.length;
	const cy = points.reduce((sum, p) => sum + p.y, 0) / points.length;
	const r =
		Math.max(
			34,
			...points.map((p) => {
				const dx = p.x - cx;
				const dy = p.y - cy;
				return Math.sqrt(dx * dx + dy * dy);
			})
		) + 30;
	return { cx: px(cx), cy: px(cy), rx: px(r * 1.12), ry: px(r) };
}

src/lib/components/charts/sankey-chart/doc.ts

/**
 * SankeyChart — quantities flowing through stages.
 *
 * ┌───────────────────────────────────────────────────────────────────────────┐
 * │ § CONTRACT — the oracle. Names no library, contains no code.              │
 * └───────────────────────────────────────────────────────────────────────────┘
 *
 * # Shape
 *
 *     label         REQUIRED
 *     nodes         { id, label }[]
 *     links         { from, to, value: number | null }[]
 *     aspect?, formatValue?, animation?  (default: flows wipe in)
 *
 * # Behaviour
 *
 * R1  Stages come from the links: a node sits one column after the furthest
 *     node that feeds it.
 * R2  Ribbon width is the quantity, on one scale for the whole chart; a
 *     node is as tall as the larger of what enters and what leaves it.
 * R3  A downstream node takes the colour of its largest source, so a flow
 *     keeps its colour across the chart.
 * R4  A link that would close a loop is not drawn (never backwards); the
 *     table reports it. A null, zero, or negative link is not drawn.
 * R5  Every node is labelled with its throughput; the table lists every
 *     link.
 */
export {};

src/lib/components/charts/sankey-chart/SankeyChart.svelte

<script lang="ts">
	import { TBody, Td, Th, THead, Tr } from '$lib/components/display/table';
	import type { AnimationProp } from '$lib/motion';
	import { chartMotion, Tweened } from '$lib/motion/svelte.svelte';
	import { cn } from '$lib/utils/cn';
	import { formatExact } from '../_kernel/format';
	import {
		sankeyLayout,
		sankeyLinks,
		sankeyTarget,
		type SankeyLink,
		type SankeyNode
	} from '../_kernel/sankey';
	import { isValue, px } from '../_kernel/scale';
	import ChartData from '../_shared/ChartData.svelte';
	import chart from '../_shared/chart.module.css';
	import styles from './sankey-chart.module.css';

	/* Quantities flowing through stages: where signups come from, which plan
	   they pick, whether they stay. Ribbon width is the quantity, on one scale
	   for the whole chart. Hover a node to light its flows. */
	let {
		label,
		nodes,
		links,
		aspect = 2,
		formatValue = formatExact,
		animation,
		class: className = ''
	}: {
		/** Names the chart. */
		label: string;
		nodes: readonly SankeyNode[];
		/** Quantities from one node to another; stages are worked out from them. */
		links: readonly SankeyLink[];
		/** Width over height. */
		aspect?: number;
		formatValue?: (value: number) => string;
		/** Default: flows wipe in from the left, when scrolled into view. */
		animation?: AnimationProp;
		class?: string;
	} = $props();

	const W = 1000;
	const H = $derived(W / aspect);
	const motion = chartMotion(() => animation, { enter: 'wipe', axis: 'x' });
	const shown = new Tweened(
		() => sankeyTarget(links),
		() => motion.update
	);
	let lit = $state<string | null>(null);
	const layout = $derived(sankeyLayout(nodes, links, shown.current, W, H));
	const loops = $derived(sankeyLinks(nodes, links).loops);
	const name = (id: string) => nodes.find((n) => n.id === id)?.label ?? id;
	const pct = (x: number, y: number) => `left:${(x / W) * 100}%;top:${(y / H) * 100}%`;
</script>

{#if !nodes.length || !layout.links.length}
	<div class={cn(chart.root, className)}>
		<p class={chart.empty}>{nodes.length ? 'Measurements unavailable.' : 'No data to display.'}</p>
	</div>
{:else}
	<div {...motion.pending} {@attach motion.attach} class={cn(chart.root, className)}>
		<div class={styles.frame} style:--aspect={aspect}>
			<svg
				class={styles.svg}
				viewBox="0 0 {W} {px(H)}"
				preserveAspectRatio="none"
				role="img"
				aria-label="{label}. Every flow is in the data table."
				data-lit={lit ? '' : undefined}
			>
				{#each layout.links as link (link.key)}
					<path
						data-mark
						data-lit={lit !== null && (link.from === lit || link.to === lit) ? '' : undefined}
						class={styles.link}
						d={link.path}
						stroke-width={Math.max(1, link.width)}
						style:--series={link.color}
					/>
				{/each}
				{#each layout.nodes as node (node.id)}
					{#if node.value > 0}
						<!-- svelte-ignore a11y_no_static_element_interactions -->
						<rect
							data-mark
							class={styles.node}
							x={px(node.x)}
							y={px(node.y)}
							width={layout.nodeWidth}
							height={px(Math.max(1, node.height))}
							style:--series={node.color}
							onpointerenter={() => (lit = node.id)}
							onpointerleave={() => (lit = null)}
						/>
					{/if}
				{/each}
			</svg>
			<div class={styles.labels} aria-hidden="true">
				{#each layout.nodes as node (node.id)}
					{#if node.value > 0}
						{@const last = node.column === layout.columns - 1 && layout.columns > 1}
						<span
							data-side={last ? 'left' : 'right'}
							style={pct(last ? node.x : node.x + layout.nodeWidth, node.y + node.height / 2)}
							>{node.label}<b>{formatValue(node.value)}</b></span
						>
					{/if}
				{/each}
			</div>
		</div>
		<ChartData {label}>
			<THead>
				<Tr><Th>From</Th><Th>To</Th><Th numeric>Value</Th></Tr>
			</THead>
			<TBody>
				{#each links as link, index (index)}
					<Tr>
						<Th scope="row">{name(link.from)}</Th>
						<Td>{name(link.to)}</Td>
						<Td numeric
							>{isValue(link.value)
								? `${formatValue(link.value)}${loops.includes(link) ? ' (not drawn: it forms a loop)' : ''}`
								: 'Unavailable'}</Td
						>
					</Tr>
				{/each}
			</TBody>
		</ChartData>
	</div>
{/if}

src/lib/components/charts/_kernel/sankey.ts

import { colorVar, type ChartColor } from './encode';
import { longestPath, splitLoops } from './graph';
import { isValue, px } from './scale';

/* SankeyChart: quantities flowing through stages. */

export type SankeyNode = { id: string; label: string };
export type SankeyLink = { from: string; to: string; value: number | null };

export type SankeyLayoutNode = SankeyNode & {
	column: number;
	x: number;
	y: number;
	height: number;
	value: number;
	inflow: number;
	outflow: number;
	color: string;
};

export type SankeyLayoutLink = {
	key: string;
	from: string;
	to: string;
	value: number;
	width: number;
	path: string;
	color: string;
};

const linkKey = (l: { from: string; to: string }) => `${l.from}>${l.to}`;

/** The links that can be drawn: both ends exist, the value is finite and
 *  positive, and it runs forward. A link that would close a loop is kept
 *  out of the picture (and reported), never drawn backwards. */
export function sankeyLinks(nodes: readonly SankeyNode[], links: readonly SankeyLink[]) {
	const ids = new Set(nodes.map((n) => n.id));
	const candidate = links.filter(
		(l) => ids.has(l.from) && ids.has(l.to) && l.from !== l.to && isValue(l.value) && l.value > 0
	);
	const { forward, loops } = splitLoops(nodes, candidate);
	const depth = longestPath(nodes, forward);
	return { forward, loops, depth };
}

export function sankeyTarget(links: readonly SankeyLink[]) {
	const target: Record<string, number> = {};
	for (const l of links) if (isValue(l.value) && l.value > 0) target[linkKey(l)] = l.value;
	return target;
}

/** Positions for the tweened link values, in a `width` × `height` space. */
export function sankeyLayout(
	nodes: readonly SankeyNode[],
	links: readonly SankeyLink[],
	shown: Readonly<Record<string, number>>,
	width: number,
	height: number,
	{ nodeWidth = 14, gap = 14 } = {}
) {
	const { forward, depth } = sankeyLinks(nodes, links);
	const flows = forward.map((l) => ({ ...l, value: shown[linkKey(l)] ?? 0 }));
	const columns = Math.max(0, ...nodes.map((n) => depth.get(n.id) ?? 0)) + 1;

	const placed = new Map<string, SankeyLayoutNode>();
	nodes.forEach((node, index) => {
		const inflow = flows.filter((l) => l.to === node.id).reduce((s, l) => s + l.value, 0);
		const outflow = flows.filter((l) => l.from === node.id).reduce((s, l) => s + l.value, 0);
		const column = depth.get(node.id) ?? 0;
		placed.set(node.id, {
			...node,
			column,
			x: columns === 1 ? width / 2 : (column * (width - nodeWidth)) / (columns - 1),
			y: 0,
			height: 0,
			value: Math.max(inflow, outflow),
			inflow,
			outflow,
			color: colorVar(((index % 4) + 1) as ChartColor)
		});
	});

	// One vertical scale for every column: the fullest column fills the height.
	const byColumn = Array.from({ length: columns }, (_, c) =>
		[...placed.values()].filter((n) => n.column === c && n.value > 0)
	);
	const scale = Math.min(
		...byColumn
			.filter((c) => c.length)
			.map((c) => (height - gap * (c.length - 1)) / c.reduce((s, n) => s + n.value, 0))
	);
	for (const column of byColumn) {
		const used = column.reduce((s, n) => s + n.value * scale, 0) + gap * (column.length - 1);
		let y = (height - used) / 2;
		for (const n of column) {
			n.y = y;
			n.height = n.value * scale;
			y += n.height + gap;
		}
	}

	// First-column nodes keep their hue; everything downstream takes the hue of
	// its largest source, so a flow keeps its colour across the chart.
	for (let c = 1; c < columns; c++)
		for (const n of byColumn[c]) {
			const main = flows.filter((l) => l.to === n.id).sort((a, b) => b.value - a.value)[0];
			if (main) n.color = placed.get(main.from)!.color;
		}

	// Links leave a node ordered by where they arrive, and arrive ordered by
	// where they left, so ribbons cross as little as they can.
	const outOffset = new Map<string, number>();
	const inOffset = new Map<string, number>();
	const sorted = [...flows].sort(
		(a, b) =>
			placed.get(a.from)!.y - placed.get(b.from)!.y || placed.get(a.to)!.y - placed.get(b.to)!.y
	);
	const out: SankeyLayoutLink[] = [];
	const bySource = [...sorted].sort((a, b) => placed.get(a.to)!.y - placed.get(b.to)!.y);
	const sourceY = new Map<string, number>();
	for (const l of bySource) {
		const o = outOffset.get(l.from) ?? 0;
		sourceY.set(linkKey(l), placed.get(l.from)!.y + o);
		outOffset.set(l.from, o + l.value * scale);
	}
	for (const l of sorted) {
		const a = placed.get(l.from)!;
		const b = placed.get(l.to)!;
		const w = l.value * scale;
		const y0 = sourceY.get(linkKey(l))! + w / 2;
		const i = inOffset.get(l.to) ?? 0;
		const y1 = b.y + i + w / 2;
		inOffset.set(l.to, i + w);
		const x0 = a.x + nodeWidth;
		const x1 = b.x;
		const mid = (x0 + x1) / 2;
		out.push({
			key: linkKey(l),
			from: l.from,
			to: l.to,
			value: l.value,
			width: w,
			path: `M${px(x0)},${px(y0)}C${px(mid)},${px(y0)} ${px(mid)},${px(y1)} ${px(x1)},${px(y1)}`,
			color: a.color
		});
	}
	return { nodes: [...placed.values()], links: out, nodeWidth, columns };
}