Watts Threshold Cascade

// Watts threshold contagion on a Watts–Strogatz small-world graph (n = 80).
// Ring lattice with k=4 nearest neighbors per side, rewired with prob β=0.1.
// At each step a node activates iff ≥ φ fraction of its neighbors are active.
// Mouse X scrubs φ; cascade restarts from a small seed cluster on change.

const N = 80, K = 4, BETA = 0.1, SEED = 4;

let xs, ys;
let deg, nbrIdx, nbrOff;
let active, nextA;
let W = 0, H = 0;
let phi = 0.2, lastPhi = -1;
let activeCount = 0, stepIdx = 0;
let stepAccum = 0, stalled = 0;

function rngFn(a) {
  return function () {
    a = (a + 0x6d2b79f5) | 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function buildGraph() {
  const rng = rngFn(0xC0FFEE);
  const edges = new Set();
  const key = (a, b) => Math.min(a, b) * N + Math.max(a, b);
  const add = (a, b) => { if (a !== b) edges.add(key(a, b)); };
  for (let i = 0; i < N; i++) for (let j = 1; j <= K; j++) add(i, (i + j) % N);
  // Rewire with prob β
  for (const k of Array.from(edges)) {
    if (rng() >= BETA) continue;
    const lo = Math.floor(k / N);
    edges.delete(k);
    let tgt, tries = 0;
    do { tgt = Math.floor(rng() * N); tries++; }
    while ((tgt === lo || edges.has(key(lo, tgt))) && tries < 20);
    if (tgt === lo) edges.add(k); else edges.add(key(lo, tgt));
  }
  // CSR build
  deg = new Int32Array(N);
  for (const k of edges) { deg[Math.floor(k / N)]++; deg[k % N]++; }
  nbrOff = new Int32Array(N + 1);
  for (let i = 0; i < N; i++) nbrOff[i + 1] = nbrOff[i] + deg[i];
  const cur = new Int32Array(N);
  nbrIdx = new Int32Array(nbrOff[N]);
  for (const k of edges) {
    const a = Math.floor(k / N), b = k % N;
    nbrIdx[nbrOff[a] + cur[a]++] = b;
    nbrIdx[nbrOff[b] + cur[b]++] = a;
  }
}

// Light Fruchterman–Reingold once at init. Seeded for reproducibility.
function layoutFR() {
  const rng = rngFn(0xBEEFCAFE);
  xs = new Float32Array(N); ys = new Float32Array(N);
  const cx = W * 0.5, cy = H * 0.5, R0 = Math.min(W, H) * 0.32;
  for (let i = 0; i < N; i++) {
    const a = (i / N) * Math.PI * 2 + rng() * 0.4;
    xs[i] = cx + Math.cos(a) * R0; ys[i] = cy + Math.sin(a) * R0;
  }
  const kk = Math.sqrt((W * H) / N) * 0.55, k2 = kk * kk;
  const dx = new Float32Array(N), dy = new Float32Array(N);
  let t = Math.min(W, H) * 0.08;
  for (let it = 0; it < 120; it++) {
    dx.fill(0); dy.fill(0);
    for (let i = 0; i < N; i++) {
      for (let j = i + 1; j < N; j++) {
        let ddx = xs[i] - xs[j], ddy = ys[i] - ys[j];
        let d2 = ddx * ddx + ddy * ddy;
        if (d2 < 0.01) { ddx = rng() - 0.5; ddy = rng() - 0.5; d2 = 0.5; }
        const f = k2 / d2;
        dx[i] += ddx * f; dy[i] += ddy * f;
        dx[j] -= ddx * f; dy[j] -= ddy * f;
      }
    }
    for (let i = 0; i < N; i++) {
      for (let p = nbrOff[i]; p < nbrOff[i + 1]; p++) {
        const j = nbrIdx[p]; if (j <= i) continue;
        const ddx = xs[i] - xs[j], ddy = ys[i] - ys[j];
        const d = Math.sqrt(ddx * ddx + ddy * ddy) + 1e-6;
        const f = (d * d) / kk;
        dx[i] -= (ddx / d) * f; dy[i] -= (ddy / d) * f;
        dx[j] += (ddx / d) * f; dy[j] += (ddy / d) * f;
      }
    }
    for (let i = 0; i < N; i++) {
      const d = Math.sqrt(dx[i] * dx[i] + dy[i] * dy[i]) + 1e-6;
      const s = Math.min(d, t);
      xs[i] += (dx[i] / d) * s; ys[i] += (dy[i] / d) * s;
    }
    t *= 0.96;
  }
  // Fit to canvas with HUD padding
  let mnX = Infinity, mnY = Infinity, mxX = -Infinity, mxY = -Infinity;
  for (let i = 0; i < N; i++) {
    if (xs[i] < mnX) mnX = xs[i]; if (xs[i] > mxX) mxX = xs[i];
    if (ys[i] < mnY) mnY = ys[i]; if (ys[i] > mxY) mxY = ys[i];
  }
  const pL = 24, pR = 24, pT = 130, pB = 56;
  const s = Math.min((W - pL - pR) / (mxX - mnX + 1e-6), (H - pT - pB) / (mxY - mnY + 1e-6));
  const ox = pL + ((W - pL - pR) - (mxX - mnX) * s) * 0.5;
  const oy = pT + ((H - pT - pB) - (mxY - mnY) * s) * 0.5;
  for (let i = 0; i < N; i++) { xs[i] = ox + (xs[i] - mnX) * s; ys[i] = oy + (ys[i] - mnY) * s; }
}

function seedCascade() {
  active.fill(0); nextA.fill(0);
  const visited = new Uint8Array(N), queue = [0];
  visited[0] = 1; let placed = 0;
  while (queue.length && placed < SEED) {
    const u = queue.shift(); active[u] = 1; placed++;
    for (let p = nbrOff[u]; p < nbrOff[u + 1]; p++) {
      const v = nbrIdx[p];
      if (!visited[v]) { visited[v] = 1; queue.push(v); }
    }
  }
  activeCount = placed; stepIdx = 0; stalled = 0;
}

function cascadeStep() {
  let changed = 0;
  for (let i = 0; i < N; i++) {
    if (active[i]) { nextA[i] = 1; continue; }
    const d = deg[i];
    if (d === 0) { nextA[i] = 0; continue; }
    let on = 0;
    for (let p = nbrOff[i]; p < nbrOff[i + 1]; p++) if (active[nbrIdx[p]]) on++;
    if (on / d >= phi) { nextA[i] = 1; changed++; } else nextA[i] = 0;
  }
  const tmp = active; active = nextA; nextA = tmp;
  activeCount += changed; stepIdx++;
  return changed;
}

function phiFromInput(input) {
  const x = input.mouseX;
  if (x === undefined || x === null || x < 0 || x > W) {
    return 0.5 + 0.35 * Math.sin(performance.now() * 0.0003);
  }
  return Math.max(0, Math.min(1, x / W));
}

function init({ width, height }) {
  W = width; H = height;
  buildGraph(); layoutFR();
  active = new Uint8Array(N); nextA = new Uint8Array(N);
  phi = 0.2; lastPhi = phi;
  seedCascade();
}

function tick({ ctx, dt, width, height, input }) {
  if (width !== W || height !== H) { W = width; H = height; layoutFR(); }
  phi = phiFromInput(input);
  if (Math.abs(phi - lastPhi) > 0.01) { seedCascade(); lastPhi = phi; }

  stepAccum += dt;
  if (stepAccum > 0.15 && stalled < 24) {
    stepAccum = 0;
    const changed = cascadeStep();
    if (changed === 0) stalled++; else stalled = 0;
  }

  ctx.fillStyle = "#0a0d14"; ctx.fillRect(0, 0, W, H);

  // Inactive edges (gray) first
  ctx.lineWidth = 1; ctx.strokeStyle = "rgba(140,150,170,0.22)";
  ctx.beginPath();
  for (let i = 0; i < N; i++) {
    for (let p = nbrOff[i]; p < nbrOff[i + 1]; p++) {
      const j = nbrIdx[p]; if (j <= i) continue;
      if (active[i] && active[j]) continue;
      ctx.moveTo(xs[i], ys[i]); ctx.lineTo(xs[j], ys[j]);
    }
  }
  ctx.stroke();
  // Active edges (orange) on top
  ctx.lineWidth = 1.4; ctx.strokeStyle = "rgba(255,150,60,0.78)";
  ctx.beginPath();
  for (let i = 0; i < N; i++) {
    for (let p = nbrOff[i]; p < nbrOff[i + 1]; p++) {
      const j = nbrIdx[p]; if (j <= i) continue;
      if (!(active[i] && active[j])) continue;
      ctx.moveTo(xs[i], ys[i]); ctx.lineTo(xs[j], ys[j]);
    }
  }
  ctx.stroke();
  // Nodes
  for (let i = 0; i < N; i++) {
    if (active[i]) {
      ctx.fillStyle = "rgba(255,200,120,0.32)";
      ctx.beginPath(); ctx.arc(xs[i], ys[i], 7.5, 0, Math.PI * 2); ctx.fill();
      ctx.fillStyle = "#ff9a3c";
      ctx.beginPath(); ctx.arc(xs[i], ys[i], 4.2, 0, Math.PI * 2); ctx.fill();
    } else {
      ctx.fillStyle = "#8590a6";
      ctx.beginPath(); ctx.arc(xs[i], ys[i], 2.8, 0, Math.PI * 2); ctx.fill();
    }
  }

  drawHUD(ctx);
}

function drawHUD(ctx) {
  const pad = 12, frac = activeCount / N;
  ctx.fillStyle = "rgba(0,0,0,0.62)"; ctx.fillRect(pad, pad, 268, 104);
  ctx.fillStyle = "#fff"; ctx.font = "13px monospace";
  ctx.textAlign = "left"; ctx.textBaseline = "alphabetic";
  ctx.fillText(`n=${N}  k=${K}  β=${BETA}`, pad + 10, pad + 20);
  ctx.fillText(`φ     = ${phi.toFixed(3)}`, pad + 10, pad + 38);
  ctx.fillText(`step  = ${stepIdx}`, pad + 10, pad + 56);
  ctx.fillText(`active= ${activeCount}/${N}  (${(frac * 100).toFixed(0)}%)`, pad + 10, pad + 74);
  const state = stalled >= 1
    ? (activeCount === N ? "full cascade" : activeCount <= SEED ? "fizzled" : "locked-in")
    : "spreading…";
  ctx.fillText(`state = ${state}`, pad + 10, pad + 92);

  let regime, color;
  if (phi < 0.18) { regime = "low threshold — anything spreads"; color = "#ff7a7a"; }
  else if (phi < 0.34) { regime = "cascade window — full sweep likely"; color = "#ff9a3c"; }
  else if (phi < 0.5) { regime = "marginal — partial cascade"; color = "#ffd17a"; }
  else { regime = "high threshold — seed fizzles"; color = "#7aa2f7"; }
  ctx.fillStyle = "rgba(0,0,0,0.6)"; ctx.fillRect(pad, H - pad - 28, 340, 28);
  ctx.fillStyle = color; ctx.fillText(regime, pad + 10, H - pad - 10);

  // φ slider with 1/(2k) cascade-window marker
  const bx = pad + 280, by = pad, bw = W - (pad + 280) - pad, bh = 18;
  if (bw > 90) {
    ctx.fillStyle = "rgba(0,0,0,0.55)"; ctx.fillRect(bx, by, bw, bh + 20);
    ctx.fillStyle = "#2a3554"; ctx.fillRect(bx + 6, by + 6, bw - 12, bh - 12);
    ctx.fillStyle = "#ff9a3c"; ctx.fillRect(bx + 6, by + 6, (bw - 12) * Math.max(0, Math.min(1, phi)), bh - 12);
    const cu = 1 / (2 * K);
    ctx.strokeStyle = "#ffd17a"; ctx.lineWidth = 2;
    ctx.beginPath();
    ctx.moveTo(bx + 6 + (bw - 12) * cu, by + 2);
    ctx.lineTo(bx + 6 + (bw - 12) * cu, by + bh + 2);
    ctx.stroke();
    ctx.fillStyle = "#fff"; ctx.font = "11px monospace";
    ctx.fillText("move cursor X to scrub φ   (marker = 1/2k)", bx + 6, by + bh + 16);
  }
}