2b:null 2c:["$","title",null,{"children":"Minimize Crossings: Spectral Circular Graph for Layout | Tom Larkworthy | Observable"}] 31:T762,# Minimize Crossings: Spectral Circular Graph for Layout This notebook implements a small, **in-browser graph layout heuristic** for reducing edge crossings when drawing an undirected graph in *1D* as a **circular ordering**: place vertices around a circle and draw each edge as a straight chord. The objective is to choose a cyclic vertex order that makes chords intersect as little as possible. Because **crossing minimization over permutations is NP-hard**, we don’t solve it exactly. Instead we use a fast, deterministic pipeline: 1. **Build / edit a graph** as an undirected edge list (with an interactive adjacency-grid editor and optional random graph generation). 2. **Clean the edge list**: remove self-loops, clamp to \`[0, n)\`, de-duplicate, and normalize \`(a,b)\` with \`a v.toExponential ? v.toExponential(0).replace("+", "") : String(v) }), passesOrtho: Inputs.range([1, 4], { step: 1, value: 2, label: "orthonorm passes" }), siftPasses: Inputs.select([0, 1, 2, 3], { value: 1, label: "sifting passes (post)" }), randomR: Inputs.range([0, 100], { step: 1, value: 20, label: "random baseline R" }), density: Inputs.range([0, 1], { step: 0.02, value: 0.18, label: "random edge density" }) }, { label: "Graph + layout parameters" } )33:Tc4b,dashboard = { const n = params.n; const cleanEdges = []; const seen = new Set(); for (const e of viewof edges.value) { const a0 = e[0] | 0, b0 = e[1] | 0; if (a0 === b0) continue; if (a0 < 0 || b0 < 0 || a0 >= n || b0 >= n) continue; const a = Math.min(a0, b0), b = Math.max(a0, b0); const k = edgeKey(a, b); if (seen.has(k)) continue; seen.add(k); cleanEdges.push([a, b]); } const csr = buildCSR(n, cleanEdges); const spectral = spectralCircleOrder(csr, { alpha: params.alpha, maxIters: params.maxIters, tol: params.tol, seed: params.seed, passesOrtho: params.passesOrtho }); const natural = Int32Array.from(d3.range(n)); const crossingsNatural = crossingsCount(n, cleanEdges, natural); const crossingsSpectral = crossingsCount(n, cleanEdges, spectral.order); const sifted = improveOrderSifting(n, cleanEdges, spectral.order, { passes: params.siftPasses, vertexSequence: "id" }); const crossingsSifted = sifted.crossings; const randomBest = bestOfRandomOrders(n, cleanEdges, { R: params.randomR, seed: (params.seed | 0) ^ 2654435769 }); const plotA = chordPlot(n, cleanEdges, natural, { title: `Natural (crossings: ${crossingsNatural})` }); const plotB = chordPlot(n, cleanEdges, spectral.order, { title: `Spectral init (crossings: ${crossingsSpectral})` }); const plotC = chordPlot(n, cleanEdges, sifted.order, { title: `Spectral + sift (${params.siftPasses} pass${ params.siftPasses === 1 ? "" : "es" }) (crossings: ${crossingsSifted})` }); const beatRandSpectral = crossingsSpectral <= randomBest.crossings; const beatRandSifted = crossingsSifted <= randomBest.crossings; return htl.html`

Click to toggle edges (adjacency grid)

${viewof plot_editor}

edges: ${cleanEdges.length} spectral: ${ spectral.converged ? "converged" : "not converged" }, iters: ${spectral.iters}, lastDelta: ${spectral.lastDelta.toExponential(2)}

baseline best-of-${randomBest.R}-random: ${ randomBest.crossings } spectral beats random? ${ beatRandSpectral ? "yes" : "no" } sifted beats random? ${ beatRandSifted ? "yes" : "no" }

${plotA}

${plotB}

${plotC}

`; }34:T489,crossingsCount = (n, edges, order) => { const pos = new Int32Array(n); for (let i = 0; i < n; i++) pos[order[i]] = i; const intervals = []; for (const e of edges) { const a = e[0] | 0, b = e[1] | 0; if (a === b) continue; const i = pos[a], j = pos[b]; const s = Math.min(i, j), t = Math.max(i, j); if (s === t) continue; intervals.push([s, t]); } intervals.sort((p, q) => p[0] - q[0] || p[1] - q[1]); const bit = new Int32Array(n + 1); const add = (i) => { for (let x = i + 1; x <= n; x += x & -x) bit[x]++; }; const sum = (i) => { let s = 0; for (let x = i + 1; x > 0; x -= x & -x) s += bit[x]; return s; }; const range = (l, r) => (r < l ? 0 : sum(r) - (l > 0 ? sum(l - 1) : 0)); let crossings = 0; let k = 0; while (k < intervals.length) { const s = intervals[k][0]; let k2 = k; while (k2 < intervals.length && intervals[k2][0] === s) k2++; for (let t = k; t < k2; t++) { const end = intervals[t][1]; crossings += range(s + 1, end - 1); } for (let t = k; t < k2; t++) add(intervals[t][1]); k = k2; } return crossings; }35:T5d2,chordPlot = (n, edges, order, { title } = {}) => { const idx = new Int32Array(n); for (let i = 0; i < n; i++) idx[order[i]] = i; const nodes = []; const nodeXY = Array.from({ length: n }); for (let v = 0; v < n; v++) { const a = 2 * Math.PI * (idx[v] / n); const x = Math.cos(a), y = Math.sin(a); nodeXY[v] = { x, y }; nodes.push({ id: v, x, y }); } const links = []; for (const e of edges) { const a = e[0] | 0, b = e[1] | 0; if (a === b) continue; const p = nodeXY[a], q = nodeXY[b]; if (!p || !q) continue; links.push({ x1: p.x, y1: p.y, x2: q.x, y2: q.y }); } return Plot.plot({ width: 420, height: 420, aspectRatio: 1, x: { domain: [-1.25, 1.25], axis: null }, y: { domain: [-1.25, 1.25], axis: null }, marks: [ Plot.frame(), Plot.link(links, { x1: "x1", y1: "y1", x2: "x2", y2: "y2", stroke: "rgba(0,0,0,0.25)", strokeWidth: 1 }), Plot.dot(nodes, { x: "x", y: "y", r: 8, fill: "white", stroke: "black" }), Plot.text(nodes, { x: "x", y: "y", text: (d) => String(d.id), dy: 0, fontSize: 10 }), ...(title ? [ Plot.text([{ x: 0, y: 1.17, t: title }], { x: "x", y: "y", text: "t", fontSize: 14, fontWeight: "bold" }) ] : []) ] }); }36:T6aa,viewof plot_editor = { const n = params.n; const edgeSet = new Set(); for (const e of edges) { const a = e[0] | 0, b = e[1] | 0; if (a === b) continue; if (a < 0 || b < 0 || a >= n || b >= n) continue; edgeSet.add(edgeKey(a, b)); } const plot = Plot.plot({ width: 420, height: 420, margin: 40, x: { type: "point", domain: d3.range(n), label: "a" }, y: { type: "point", domain: d3.range(n), label: "b" }, style: { fontSize: "11px" }, marks: [ Plot.frame(), Plot.dot(edgeDomainFull, { x: "a", y: "b", r: 5, fill: (d) => (edgeSet.has(edgeKey(d.a, d.b)) ? "black" : "#0000"), stroke: (d) => (edgeSet.has(edgeKey(d.a, d.b)) ? "#0000" : "#ddd") }), Plot.dot( edgeDomainFull, Plot.pointer({ x: "a", y: "b", r: 11, fill: "#0000", stroke: (d) => edgeSet.has(edgeKey(d.a, d.b)) ? "#d62728" : "#1f77b4", strokeWidth: 2, maxRadius: 30 }) ) ] }); const onClick = () => { const d = plot.value; if (!d) return; const a0 = d.a | 0, b0 = d.b | 0; if (a0 === b0) return; const a = Math.min(a0, b0); const b = Math.max(a0, b0); if (a < 0 || b < 0 || a >= n || b >= n) return; const arr = viewof edges.value; const idx = arr.findIndex((e) => (e[0] | 0) === a && (e[1] | 0) === b); if (idx >= 0) arr.splice(idx, 1); else arr.push([a, b]); viewof edges.dispatchEvent(new Event("input")); }; plot.addEventListener("click", onClick); invalidation.then(() => plot.removeEventListener("click", onClick)); return plot; }37:T470,buildCSR = (n, edges) => { assert(Number.isInteger(n) && n > 0, "n must be a positive integer"); const adj = Array.from({ length: n }, () => []); for (const e of edges) { const a0 = e[0], b0 = e[1]; const a = a0 | 0, b = b0 | 0; if (a === b) continue; assert(a >= 0 && a < n && b >= 0 && b < n, "edge endpoint out of range"); adj[a].push(b); adj[b].push(a); } const deg = new Float64Array(n); let nnz = 0; for (let i = 0; i < n; i++) { const row = adj[i]; row.sort((x, y) => x - y); let w = 0; for (let j = 0; j < row.length; j++) { if (w === 0 || row[j] !== row[w - 1]) row[w++] = row[j]; } row.length = w; deg[i] = w; nnz += w; } const rowPtr = new Int32Array(n + 1); const colIdx = new Int32Array(nnz); const val = new Float64Array(nnz); let p = 0; for (let i = 0; i < n; i++) { rowPtr[i] = p; const row = adj[i]; for (let j = 0; j < row.length; j++) { colIdx[p] = row[j]; val[p] = 1.0; p++; } } rowPtr[n] = p; assert(p === nnz, "nnz mismatch"); return { n, rowPtr, colIdx, val, deg }; }38:T457,blockPower2 = (n, applyM, opts) => { const maxIters = opts.maxIters ?? 200; const tol = opts.tol ?? 1e-6; const seed = opts.seed ?? 12345; const passesOrtho = opts.passesOrtho ?? 2; const rng = makeRng(seed); const u = new Float64Array(n); const v = new Float64Array(n); for (let i = 0; i < n; i++) { u[i] = rng() - 0.5; v[i] = rng() - 0.5; } ortho2(u, v, rng, passesOrtho); const Mu = new Float64Array(n); const Mv = new Float64Array(n); const uPrev = new Float64Array(n); const vPrev = new Float64Array(n); let lastDelta = Infinity; let converged = false; for (let it = 1; it <= maxIters; it++) { copyInto(uPrev, u); copyInto(vPrev, v); applyM(u, Mu); applyM(v, Mv); copyInto(u, Mu); copyInto(v, Mv); ortho2(u, v, rng, passesOrtho); const cu = Math.abs(dot(u, uPrev)); const cv = Math.abs(dot(v, vPrev)); lastDelta = 1.0 - 0.5 * (cu + cv); if (lastDelta < tol) { converged = true; return { u, v, iters: it, converged, lastDelta }; } } return { u, v, iters: maxIters, converged, lastDelta }; }39:T774,sift_docs = md`## What “sifting” does (and why it helps) After we get an initial circular order (e.g. from the spectral angles), we optionally run a **local improvement** step called **sifting** (a.k.a. *reinsertion*). ### Move being optimized For a chosen vertex **v**: 1. **Remove** v from the current cyclic order (cut it out of the circle). 2. Try **re-inserting** v at every possible position in the remaining order (all $n$ slots around the circle). 3. Pick the position that yields the **fewest chord crossings** (ties broken deterministically). This is a *1-vertex move* neighborhood search: it never changes which pairs are connected; it only changes where one vertex sits on the circle. ### Geometric intuition (circle + chords) Fix an order of all vertices except v. As you slide v around the circle: - each incident edge $(v, u)$ becomes a chord whose endpoints “sweep” past other endpoints, - chord intersections change only when v passes another vertex (i.e. when the circular order changes discretely), - so the crossing count is **piecewise constant** across slots, and we can search all slots exactly by brute force. Heuristically, sifting tends to: - pull a vertex closer (in angular terms) to the block of vertices it connects to, - reduce “long” interleavings where v’s incident chords cut across many unrelated chords. ### Passes and vertex order A **sift pass** runs the reinsertion step for a sequence of vertices, updating the order after each vertex move. - \`passes\`: how many full rounds to do (often 1–2 is plenty). - \`vertexSequence: "id"\`: visit vertices in numeric id order (fully deterministic). - \`vertexSequence: "order"\`: visit in the current circular order (sometimes slightly better as a post-process after another heuristic). Note: sifting is a greedy local search—fast and often effective, but not guaranteed to find a global minimum.`3a:T919,bestOfRandomOrders = ( n, edges, { R = 20, seed = 1, postSiftPasses = 0 } = {} ) => { const adj = Array.from({ length: n }, () => []); for (const e of edges) { const a0 = e[0] | 0, b0 = e[1] | 0; if (a0 === b0) continue; if (a0 < 0 || b0 < 0 || a0 >= n || b0 >= n) continue; adj[a0].push(b0); adj[b0].push(a0); } const deg = new Int32Array(n); for (let i = 0; i < n; i++) deg[i] = adj[i].length; const starts = Array.from({ length: n }, (_, i) => i); starts.sort((i, j) => deg[j] - deg[i] || i - j); const K = Math.min(n, Math.max(0, R | 0)); if (K === 0) { const order = Int32Array.from({ length: n }, (_, i) => i); const crossings = crossingsCount(n, edges, order); return { order, crossings, R: 0, seed: seed | 0, method: "natural" }; } const greedyFromStart = (s) => { const placed = new Uint8Array(n); const score = new Int32Array(n); const order = new Int32Array(n); placed[s] = 1; order[0] = s; for (const nb of adj[s]) score[nb]++; for (let k = 1; k < n; k++) { let best = -1; let bestScore = -2147483648; let bestDeg = -2147483648; for (let v = 0; v < n; v++) { if (placed[v]) continue; const sv = score[v]; const dv = deg[v]; if ( sv > bestScore || (sv === bestScore && (dv > bestDeg || (dv === bestDeg && v < best))) ) { best = v; bestScore = sv; bestDeg = dv; } } order[k] = best; placed[best] = 1; for (const nb of adj[best]) if (!placed[nb]) score[nb]++; } return order; }; let bestCross = Infinity; let bestOrder = null; for (let t = 0; t < K; t++) { const s = starts[t]; const order = greedyFromStart(s); const c = crossingsCount(n, edges, order); if (c < bestCross) { bestCross = c; bestOrder = order; } } const passes = Math.max(0, postSiftPasses | 0); if (passes > 0) { const sifted = improveOrderSifting(n, edges, bestOrder, { passes, vertexSequence: "order" }); bestOrder = sifted.order; bestCross = sifted.crossings; } return { order: bestOrder, crossings: bestCross, R: K, seed: seed | 0, method: "greedy-starts", postSiftPasses: passes }; }3b:[] 2f:{"id":"b316487cf25bf2ee","slug":"spectral-layout","title":"Minimize Crossings: Spectral Circular Graph for Layout","thumbnail":"c507a6cc06df14c9ebd286f36a529083376ff362f9a3599439c903c2c0dd4796","access_level":"public","create_time":"$D2026-01-09T19:14:30.787Z","update_time":"$D2026-01-10T11:31:14.093Z","view_time":null,"first_public_time":"$D2026-01-10T10:49:09.182Z","fork":false,"stars":8,"starred":false,"owner":{"type":"team","id":"7db5ed2b0697d645","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":"starter_2024"},"version":290,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"5215f6ec4a999d40","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":null}],"members":[{"type":"individual","id":"5215f6ec4a999d40","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":null,"role":"editor"},{"type":"team","id":"7db5ed2b0697d645","login":"tomlarkworthy","name":"Tom Larkworthy","avatar_url":"https://avatars-next.observableusercontent.com/47327a8bc1966f2186dcb3ebf4b7ee6e4e7ab9a5c2a07405aff57200ea778f71","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Minimize Crossings: Spectral Circular Graph for Layout","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":255,"value":"### Motivation\n\nThe motivation was to enable better visualisation of code dependancies by reducing the tangles","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":264,"value":"import { visualizeModules } from \"@tomlarkworthy/module-map\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":258,"value":"viewof useSpectral = Inputs.toggle({ label: \"use Spectral layout\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":268,"value":"visualizeModules({ useSpectral })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":277,"value":"## Playground","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":135,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":138,"value":"viewof actions = Inputs.form(\n {\n randomize: Inputs.button(\"Random graph\", {\n value: 0,\n reduce: (v) => v + 1\n }),\n clear: Inputs.button(\"Clear edges\", { value: 0, reduce: (v) => v + 1 })\n },\n { label: \"Actions\" }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":208,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":131,"value":"edgeKey = (a, b) => (a < b ? `${a},${b}` : `${b},${a}`);\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":133,"value":"normalizeEdge = (a, b) => (a < b ? [a, b] : [b, a])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":141,"value":"viewof edges = Inputs.input([])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":143,"value":"edgesController = {\n const state = this ?? { randomize: 0, clear: 0 };\n\n if (actions.clear !== state.clear) {\n viewof edges.value.length = 0;\n viewof edges.dispatchEvent(new Event(\"input\"));\n }\n\n if (actions.randomize !== state.randomize) {\n const n = params.n;\n const density = params.density;\n const rng = makeRng((params.seed | 0) + 1000003 * (actions.randomize | 0));\n\n viewof edges.value.length = 0;\n for (let a = 0; a < n; a++) {\n for (let b = a + 1; b < n; b++) {\n if (rng() < density) viewof edges.value.push([a, b]);\n }\n }\n viewof edges.dispatchEvent(new Event(\"input\"));\n }\n\n state.randomize = actions.randomize;\n state.clear = actions.clear;\n return state;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":145,"value":"edgeDomainFull = {\n const n = params.n;\n const dom = [];\n for (let a = 0; a < n; a++) {\n for (let b = 0; b < n; b++) {\n if (a === b) continue;\n dom.push({ a, b });\n }\n }\n return dom;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":156,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":153,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":148,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":32,"value":"md`# Spectral circular ordering\n\nGoal: given an undirected graph, produce a **circular order** of vertices that often (not always) reduces edge crossings when drawn as straight chords on a circle.\n\nApproach (high-level):\n1. Build a **CSR** (compressed sparse row) representation of the graph.\n2. Define a symmetric smoothing operator **M** based on the normalized adjacency.\n3. Use **block power iteration** to find a stable 2D invariant subspace (two orthonormal vectors).\n4. Map each vertex to an angle \\`θ = atan2(v[i], u[i])\\` and sort by \\`θ\\` to get a circular order.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":36,"value":"assert = (cond, msg) => {\n if (!cond) throw new Error(msg);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":39,"value":"md`## 1) Graph representation: CSR (Compressed Sparse Row)\n\nWe want fast repeated multiplication by a sparse operator. CSR stores:\n\n- \\`rowPtr\\` of length \\`n+1\\`: where each vertex's neighbor list starts/ends in \\`colIdx\\`\n- \\`colIdx\\` of length \\`nnz\\`: all neighbor vertex ids concatenated\n- \\`val\\` of length \\`nnz\\`: edge weights (we use all 1.0)\n- \\`deg\\` of length \\`n\\`: degree per vertex\n\nThis builder:\n- treats edges as **undirected**\n- removes **self-loops**\n- **de-dupes** parallel edges\n- sorts neighbors for determinism`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":42,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":47,"value":"md`## 2) The operator we iterate: normalized adjacency smoothing\n\nWe choose a symmetric operator:\n\n\\`\\`\\`\nM = (1 - α) I + α D^{-1/2} A D^{-1/2}\n\\`\\`\\`\n\n- \\`A\\` is the adjacency matrix\n- \\`D\\` is the diagonal matrix of degrees\n- \\`α ∈ (0,1)\\` controls how strongly we smooth/mix\n\nWhy this choice?\n- It is **symmetric** for undirected graphs, so it behaves well numerically.\n- It is a \"lazy\" smoothing operator: \\`(1-α)I\\` prevents oscillations and helps convergence.\n- Iterating it tends to reveal large-scale structure that is often useful for ordering.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":50,"value":"applyM_normAdj = (csr, x, y, alpha) => {\n const { n, rowPtr, colIdx, val, deg } = csr;\n assert(x.length === n && y.length === n, \"vector length mismatch\");\n assert(alpha > 0 && alpha < 1, \"alpha must be in (0,1)\");\n\n const oneMinus = 1.0 - alpha;\n\n for (let i = 0; i < n; i++) y[i] = oneMinus * x[i];\n\n for (let i = 0; i < n; i++) {\n const di = deg[i];\n if (di === 0) continue;\n const invSqrtDi = 1.0 / Math.sqrt(di);\n let acc = 0.0;\n const p0 = rowPtr[i],\n p1 = rowPtr[i + 1];\n for (let p = p0; p < p1; p++) {\n const j = colIdx[p];\n const dj = deg[j];\n if (dj === 0) continue;\n const invSqrtDj = 1.0 / Math.sqrt(dj);\n acc += val[p] * invSqrtDj * x[j];\n }\n y[i] += alpha * invSqrtDi * acc;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":53,"value":"\n\n\nmd`## 3) Deterministic numerics helpers\n\nWe need:\n- a deterministic RNG (for stable initialization and reinitialization)\n- dot products and norms\n- stable argsort (deterministic tie-breaking)\n\nDeterminism is important for notebook reproducibility: same graph + same seed → same order.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":57,"value":"makeRng = (seed) => {\n let x = seed | 0 || 0x12345678;\n return () => {\n x ^= x << 13;\n x |= 0;\n x ^= x >>> 17;\n x |= 0;\n x ^= x << 5;\n x |= 0;\n return (x >>> 0) / 4294967296;\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":61,"value":"dot = (a, b) => {\n let s = 0;\n for (let i = 0; i < a.length; i++) s += a[i] * b[i];\n return s;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":64,"value":"norm2 = (a) => Math.sqrt(dot(a, a))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":67,"value":"scaleInPlace = (a, c) => {\n for (let i = 0; i < a.length; i++) a[i] *= c;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":70,"value":"copyInto = (dst, src) => {\n dst.set(src);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":73,"value":"stableArgsortByKey = (keys) => {\n const idx = Array.from({ length: keys.length }, (_, i) => i);\n idx.sort((i, j) => {\n const di = keys[i],\n dj = keys[j];\n if (di < dj) return -1;\n if (di > dj) return 1;\n return i - j;\n });\n return Int32Array.from(idx);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":76,"value":"\n\nmd`## 4) Orthonormalizing 2 vectors (modified Gram–Schmidt)\n\nBlock power iteration evolves **two vectors at once**. Each iteration we apply \\`M\\` to both vectors, then we need to re-orthonormalize them to:\n- prevent collapse onto the same dominant eigenvector\n- keep \\`u\\` and \\`v\\` numerically stable\n\nIf a vector becomes nearly zero (rare but possible), we deterministically reinitialize it using the RNG.`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":80,"value":"ortho2 = (q1, q2, rng, passes) => {\n const n = q1.length;\n\n const renorm = (q) => {\n const nrm = norm2(q);\n if (nrm < 1e-12) {\n for (let i = 0; i < n; i++) q[i] = rng() - 0.5;\n const nrm2 = norm2(q);\n scaleInPlace(q, 1.0 / (nrm2 || 1.0));\n return;\n }\n scaleInPlace(q, 1.0 / nrm);\n };\n\n for (let pass = 0; pass < passes; pass++) {\n renorm(q1);\n\n const a = dot(q1, q2);\n for (let i = 0; i < n; i++) q2[i] -= a * q1[i];\n\n renorm(q2);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":83,"value":"md`## 5) Block power iteration (2 vectors)\n\nPower iteration typically finds the dominant eigenvector. For circular ordering we want a **2D embedding**, so we do \"block power iteration\":\n\n- start with two random vectors \\`u, v\\`\n- repeatedly compute \\`Mu, Mv\\`\n- orthonormalize\n- stop when the basis stops changing much\n\nWe use a simple convergence proxy:\n\n\\`\\`\\`\ndelta = 1 - (|u·u_prev| + |v·v_prev|)/2\n\\`\\`\\`\n\nSmall \\`delta\\` means the subspace is stable.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":87,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":93,"value":"md`## 6) From (u, v) to a circular order\n\nOnce each vertex \\`i\\` has coordinates \\`(u[i], v[i])\\`, we assign it an angle:\n\n\\`\\`\\`\nθ[i] = atan2(v[i], u[i])\n\\`\\`\\`\n\nSorting vertices by \\`θ\\` produces a circular order.\n\nNotes:\n- this is invariant to rotating the entire 2D basis\n- stable tie-breaking ensures deterministic output`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":97,"value":"circularOrderFromUV = (u, v) => {\n assert(u.length === v.length, \"u,v length mismatch\");\n const n = u.length;\n const ang = new Float64Array(n);\n for (let i = 0; i < n; i++) ang[i] = Math.atan2(v[i], u[i]);\n return stableArgsortByKey(ang);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":100,"value":"md`## 7) The full pipeline: spectralCircleOrder\n\nThis ties everything together:\n- validate parameters\n- define \\`applyM(x,y)\\` using the CSR graph and \\`α\\`\n- run block power iteration to get \\`u,v\\`\n- produce the circular order by angle-sorting\n\nReturn structure:\n- \\`order\\`: Int32Array of vertex ids in circular order\n- \\`u,v\\`: the embedding coordinates (unit norm, orthogonal)\n- diagnostics: iters, converged, lastDelta`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":104,"value":"spectralCircleOrder = (csr, opts = {}) => {\n const alpha = opts.alpha ?? 0.95;\n const maxIters = opts.maxIters ?? 200;\n const tol = opts.tol ?? 1e-6;\n const seed = opts.seed ?? 12345;\n const passesOrtho = opts.passesOrtho ?? 2;\n\n assert(alpha > 0 && alpha < 1, \"alpha must be in (0,1)\");\n\n const n = csr.n;\n\n const applyM = (x, y) => applyM_normAdj(csr, x, y, alpha);\n\n const { u, v, iters, converged, lastDelta } = blockPower2(n, applyM, {\n maxIters,\n tol,\n seed,\n passesOrtho\n });\n\n const order = circularOrderFromUV(u, v);\n return { order, u, v, iters, converged, lastDelta };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":109,"value":"md`## Code example\n\nWe build a small graph and compute a circular order.\n\nIf you replace \\`edges\\` with your own edge list, the same pipeline applies.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":113,"value":"example = (() => {\n const n = 8;\n const edges = [\n [0, 1],\n [1, 2],\n [2, 3],\n [3, 4],\n [4, 5],\n [5, 6],\n [6, 7],\n [7, 0],\n [0, 4],\n [1, 5],\n [2, 6],\n [3, 7]\n ];\n const csr = buildCSR(n, edges);\n const res = spectralCircleOrder(csr, {\n alpha: 0.95,\n maxIters: 300,\n tol: 1e-7,\n seed: 1\n });\n return {\n n,\n edges,\n order: Array.from(res.order),\n converged: res.converged,\n iters: res.iters,\n lastDelta: res.lastDelta\n };\n})()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":237,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":241,"value":"\nsift_docs2 = md`### How to read the implementation below\n\n- **\\`bestInsertPosition\\`**: implements “remove v, try all slots, keep best”.\n- **\\`siftPass\\`**: applies \\`bestInsertPosition\\` to a whole vertex sequence once.\n- **\\`improveOrderSifting\\`**: repeats \\`siftPass\\` for multiple passes.\n\nThis version is intentionally simple (recomputes crossings from scratch per candidate) because \$n \\le 40\$ in this notebook. For larger graphs, you’d typically maintain incremental crossing counts per move instead of re-evaluating the full objective each time.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":194,"value":"bestInsertPosition = (n, edges, order, v) => {\n const arr = Array.from(order);\n const k = arr.indexOf(v);\n if (k < 0) throw new Error(\"v not found in order\");\n arr.splice(k, 1);\n let bestPos = 0;\n let bestCross = Infinity;\n let bestOrder = null;\n for (let pos = 0; pos <= arr.length; pos++) {\n const cand = arr.slice(0, pos);\n cand.push(v);\n for (let i = pos; i < arr.length; i++) cand.push(arr[i]);\n const candOrder = Int32Array.from(cand);\n const c = crossingsCount(n, edges, candOrder);\n if (c < bestCross || (c === bestCross && pos < bestPos)) {\n bestCross = c;\n bestPos = pos;\n bestOrder = candOrder;\n }\n }\n return { pos: bestPos, crossings: bestCross, order: bestOrder };\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":196,"value":"\nsiftPass = (n, edges, order, { vertexSequence = \"id\" } = {}) => {\n let current = Int32Array.from(order);\n let currentCross = crossingsCount(n, edges, current);\n\n let seq;\n if (vertexSequence === \"order\") seq = Array.from(current);\n else seq = Array.from({ length: n }, (_, i) => i);\n\n for (const v of seq) {\n const best = bestInsertPosition(n, edges, current, v);\n current = best.order;\n currentCross = best.crossings;\n }\n\n return { order: current, crossings: currentCross };\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":199,"value":"improveOrderSifting = (\n n,\n edges,\n initOrder,\n { passes = 1, vertexSequence = \"id\" } = {}\n) => {\n let order = Int32Array.from(initOrder);\n let crossings = crossingsCount(n, edges, order);\n const passCount = Math.max(0, passes | 0);\n\n for (let p = 0; p < passCount; p++) {\n const res = siftPass(n, edges, order, { vertexSequence });\n order = res.order;\n crossings = res.crossings;\n }\n\n return { order, crossings, passes: passCount };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":202,"value":"$3a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3b","stdlib":"1","titling":"auto"}} 30:"$2f:body"