araharah-executor
f75dc9e8c6
- contractGraph: greedy edgeDifference + λ·deletedNeighbours priority, lazy PQ with id tie-breaks, rank = contraction position (total order) - overlay-only witness search: contracted node + candidate absent, bounded by candidate distance and max(60, 4·localDegree) settles - directed shortcut emission (ascending from, then to), via midpoints, f32 CSR; dominated-insert guard; explosion tripwire fails loud at 4×N - deterministic: no PRNG/map-order; identical input -> identical output - 25-node grid: 41 shortcuts (1.64/node), 0 budget hits
332 lines
16 KiB
JavaScript
332 lines
16 KiB
JavaScript
#!/usr/bin/env node
|
||
/*
|
||
* contraction.test.mjs — the CH construction core gates (C1–C7).
|
||
* ------------------------------------------------------------------
|
||
* RED first (plan 08.1-01 task 1): every case fails while
|
||
* routing/src/contraction.ts does not exist (lazy-import pattern —
|
||
* each case reports its own ERR_MODULE_NOT_FOUND, the landmark.test.mjs
|
||
* precedent this suite replaces).
|
||
*
|
||
* The module under test is the ONE contraction authority (the
|
||
* single-authority law): build-time node ordering + contraction +
|
||
* overlay-only witness search + shortcut emission, deterministic and
|
||
* pure. The case index:
|
||
*
|
||
* C1 total order — ranks are distinct and cover exactly [0, N)
|
||
* (a tie would drop legitimate upward edges —
|
||
* research Pitfall 9)
|
||
* C2 shortcut weights — every emitted shortcut's seconds equal the
|
||
* sum of the weights of the two edges it
|
||
* replaced (f32 round-trip tolerance)
|
||
* C3 upward shortcuts — rank(from) > rank(via) and rank(to) >
|
||
* rank(via) for every shortcut (the query's
|
||
* strict uphill law depends on it)
|
||
* C4 hand fixture — a 3-node bidirectional path yields the
|
||
* LITERAL expected contraction order and
|
||
* shortcut set (never a tautology — research
|
||
* Pitfall 10)
|
||
* C5 overlay witness — the witness search sees ONLY the overlay
|
||
* graph: a previously contracted node cannot
|
||
* witness a shortcut, so the shortcut that
|
||
* keeps the hierarchy distance-preserving IS
|
||
* emitted (the #1 correctness trap — research
|
||
* Pitfall 1)
|
||
* C6 explosion tripwire — a budget-miss cascade above
|
||
* CH_SHORTCUT_EXPLOSION_RATIO * nodeCount
|
||
* fails loud, naming the ratio and the
|
||
* measured count; a healthy graph passes
|
||
* C7 determinism — two calls on identical input produce
|
||
* byte-identical rank and shortcut arrays
|
||
*
|
||
* Run: npm run routing:test (exit 0 = all green)
|
||
*/
|
||
import { strict as assert } from "node:assert";
|
||
import { test } from "./harness.mjs";
|
||
|
||
// Lazy module load — missing module => per-case ERR_MODULE_NOT_FOUND (RED).
|
||
let contractionPromise = null;
|
||
function loadContraction() {
|
||
if (!contractionPromise) contractionPromise = import("../src/contraction.ts");
|
||
return contractionPromise;
|
||
}
|
||
|
||
/* ————— hand-built fixtures (hand-computed expectations) ————— */
|
||
|
||
/**
|
||
* Two independent overlay gadgets (nodes 0-3 and 4-7), the C5 shape at
|
||
* two weight classes (1+1 and 2+3). Hand-traced: inside each gadget ALL
|
||
* four priorities tie at −2 → the id order contracts the bypass first
|
||
* (its own pair is witnessed by the then-alive u → no shortcut), then u
|
||
* — whose pair has lost its only witness to the contraction → the
|
||
* shortcut a→b (via u) MUST be emitted. Result: exactly two shortcuts,
|
||
* 2→3 (w2, via 1) and 6→7 (w5, via 5) — a non-trivial invariant-sweep
|
||
* fixture for C1/C2/C3/C7.
|
||
*/
|
||
function pairsInput() {
|
||
return {
|
||
nodeCount: 8,
|
||
edges: [
|
||
{ from: 2, to: 1, seconds: 1, flags: 0 }, // a -> u (gadget A)
|
||
{ from: 1, to: 3, seconds: 1, flags: 0 }, // u -> b
|
||
{ from: 2, to: 0, seconds: 1, flags: 0 }, // a -> c
|
||
{ from: 0, to: 3, seconds: 1, flags: 0 }, // c -> b
|
||
{ from: 6, to: 5, seconds: 2, flags: 0 }, // a -> u (gadget B)
|
||
{ from: 5, to: 7, seconds: 3, flags: 0 }, // u -> b
|
||
{ from: 6, to: 4, seconds: 2, flags: 0 }, // a -> c
|
||
{ from: 4, to: 7, seconds: 3, flags: 0 }, // c -> b
|
||
],
|
||
};
|
||
}
|
||
|
||
/**
|
||
* C4's hand fixture: a 3-node bidirectional star — the MID node has id 0,
|
||
* the two endpoints ids 1 and 2, all four edges unit weight.
|
||
* HAND-COMPUTED under the plan's exact algorithm: every node's priority
|
||
* ties at −2 (the mid: 2 shortcuts would be added − 4 incident edges;
|
||
* an endpoint: 0 pairs − its 2 mirror edges), so the tie-break contracts
|
||
* the mid (id 0) FIRST. Its pairs (1,2) and (2,1) have no overlay
|
||
* witness (the endpoints' only edges ride the mid), so BOTH shortcuts
|
||
* are emitted with weight 1+1 = 2. The endpoints then contract free
|
||
* (their only edges are dead; deletedNeighbours = 1 each). Literal
|
||
* expectation below — never a tautology (research Pitfall 10).
|
||
*/
|
||
function handInput() {
|
||
return {
|
||
nodeCount: 3,
|
||
edges: [
|
||
{ from: 0, to: 1, seconds: 1, flags: 0 },
|
||
{ from: 1, to: 0, seconds: 1, flags: 0 },
|
||
{ from: 0, to: 2, seconds: 1, flags: 0 },
|
||
{ from: 2, to: 0, seconds: 1, flags: 0 },
|
||
],
|
||
};
|
||
}
|
||
|
||
/**
|
||
* C5's hand fixture: the overlay-witness law. Nodes: 0 = the bypass c,
|
||
* 1 = the mid node u, 2 = the witness source a, 3 = the target b. Edges:
|
||
* a→u→b (1+1) and a→c→b (1+1). ALL four priorities tie at −2 → the id
|
||
* order contracts the bypass (node 0) FIRST: its own pair (a,b) is
|
||
* witnessed by the then-alive u → no shortcut. When u (node 1) pops, its
|
||
* pair (a=2, b=3) had a witness ONLY through the bypass — now CONTRACTED
|
||
* — so the overlay search cannot traverse it and the shortcut a→b
|
||
* (via u, weight 2) MUST be emitted. On the ORIGINAL graph the a→c→b
|
||
* path still exists; a witness search that leaked out of the overlay
|
||
* would find it and silently drop the required shortcut — the exact #1
|
||
* trap, and the emitted shortcut is what keeps the hierarchy
|
||
* distance-preserving.
|
||
*/
|
||
function overlayInput() {
|
||
return {
|
||
nodeCount: 4,
|
||
edges: [
|
||
{ from: 2, to: 1, seconds: 1, flags: 0 }, // a -> u
|
||
{ from: 1, to: 3, seconds: 1, flags: 0 }, // u -> b
|
||
{ from: 2, to: 0, seconds: 1, flags: 0 }, // a -> c
|
||
{ from: 0, to: 3, seconds: 1, flags: 0 }, // c -> b
|
||
],
|
||
};
|
||
}
|
||
|
||
/**
|
||
* C6's explosion fixture (9 nodes, 40 edges): node 0 is the BYPASS hub,
|
||
* node 1 the BURST hub, nodes 2..8 the seven Y nodes; both hubs ride
|
||
* every Y with weight 1 in both directions, and the Y nodes carry a
|
||
* weight-100 ring (never on a cheapest path — pure degree ballast).
|
||
* HAND-TRACED under the plan's exact algorithm: the two hubs tie at
|
||
* priority −14 (42 pairs, all witnessed by the OTHER hub — 0 shortcuts —
|
||
* minus 14 incident edges) and the Y nodes sit at −6, so the tie-break
|
||
* contracts the bypass (id 0) FIRST. Its own 42 pairs are witnessed by
|
||
* the still-alive burst hub → no shortcuts. The burst hub's pop then
|
||
* recomputes against the overlay: its witness (the bypass) is DEAD, the
|
||
* weight-100 ring exceeds every candidate bound → all 7×6 = 42 pairs
|
||
* emit shortcuts (2 each, via the burst hub) — 42 > 4×9 = 36 → the
|
||
* tripwire MUST fail loud. (The Y nodes then witness each other through
|
||
* the fresh shortcuts — no further growth — but the count already blew
|
||
* the guard.)
|
||
*/
|
||
function explosionInput() {
|
||
const edges = [];
|
||
for (let y = 2; y <= 8; y++) {
|
||
edges.push({ from: 0, to: y, seconds: 1, flags: 0 });
|
||
edges.push({ from: y, to: 0, seconds: 1, flags: 0 });
|
||
edges.push({ from: 1, to: y, seconds: 1, flags: 0 });
|
||
edges.push({ from: y, to: 1, seconds: 1, flags: 0 });
|
||
}
|
||
for (let y = 2; y < 8; y++) {
|
||
edges.push({ from: y, to: y + 1, seconds: 100, flags: 0 });
|
||
edges.push({ from: y + 1, to: y, seconds: 100, flags: 0 });
|
||
}
|
||
return { nodeCount: 9, edges };
|
||
}
|
||
|
||
/** Min seconds over the ORIGINAL traversable (bit0-clear) edges u->v. */
|
||
function minTraversableSeconds(input, from, to) {
|
||
let best = Infinity;
|
||
for (const e of input.edges) {
|
||
if (e.from === from && e.to === to && (e.flags & 1) === 0 && e.seconds < best) {
|
||
best = e.seconds;
|
||
}
|
||
}
|
||
return best;
|
||
}
|
||
|
||
/* ————— C1–C7 ————— */
|
||
|
||
test("C1 total order — ranks are distinct and cover exactly [0, nodeCount)", async () => {
|
||
const { contractGraph, CH_LAMBDA_DELETED_NEIGHBOURS } = await loadContraction();
|
||
assert.equal(CH_LAMBDA_DELETED_NEIGHBOURS, 1, "the λ constant is the named export");
|
||
const input = pairsInput();
|
||
const result = contractGraph(input);
|
||
assert.ok(result.rank instanceof Uint32Array, "rank is a Uint32Array");
|
||
assert.equal(result.rank.length, input.nodeCount, "one rank per node");
|
||
const seen = new Set(result.rank);
|
||
assert.equal(seen.size, input.nodeCount, "ranks are DISTINCT (a tie drops upward edges — Pitfall 9)");
|
||
for (const r of result.rank) {
|
||
assert.ok(Number.isInteger(r) && r >= 0 && r < input.nodeCount, `rank ${r} in [0, ${input.nodeCount})`);
|
||
}
|
||
// stats travel with the result (the build prints them — D-08/D-09)
|
||
assert.equal(typeof result.stats.shortcutCount, "number");
|
||
assert.equal(typeof result.stats.ratioPerNode, "number");
|
||
assert.equal(typeof result.stats.witnessSearches, "number");
|
||
assert.equal(typeof result.stats.witnessBudgetHits, "number");
|
||
assert.equal(result.stats.shortcutCount, result.shortcutTarget.length, "stats agree with the CSR");
|
||
assert.ok(
|
||
Math.abs(result.stats.ratioPerNode - result.stats.shortcutCount / input.nodeCount) < 1e-12,
|
||
"ratioPerNode is shortcuts / nodeCount",
|
||
);
|
||
});
|
||
|
||
test("C2 shortcut weights — every shortcut's seconds equal the sum of the two edges it replaced", async () => {
|
||
const { contractGraph } = await loadContraction();
|
||
const input = pairsInput();
|
||
const result = contractGraph(input);
|
||
assert.ok(result.shortcutTarget.length > 0, "the chain fixture emits at least one shortcut");
|
||
for (let u = 0; u < input.nodeCount; u++) {
|
||
for (let s = result.shortcutStart[u]; s < result.shortcutStart[u + 1]; s++) {
|
||
const to = result.shortcutTarget[s];
|
||
const via = result.shortcutVia[s];
|
||
const w1 = minTraversableSeconds(input, u, via);
|
||
const w2 = minTraversableSeconds(input, via, to);
|
||
assert.ok(
|
||
Number.isFinite(w1) && Number.isFinite(w2),
|
||
`shortcut ${u}->${to} (via ${via}): both constituent edges exist in the input`,
|
||
);
|
||
assert.ok(
|
||
Math.abs(result.shortcutSeconds[s] - (w1 + w2)) < 1e-6,
|
||
`shortcut ${u}->${to}: ${result.shortcutSeconds[s]} === ${w1} + ${w2} (f32 tolerance)`,
|
||
);
|
||
}
|
||
}
|
||
});
|
||
|
||
test("C3 upward shortcuts — rank(from) > rank(via) and rank(to) > rank(via) for every shortcut", async () => {
|
||
const { contractGraph } = await loadContraction();
|
||
const input = pairsInput();
|
||
const result = contractGraph(input);
|
||
assert.ok(result.shortcutStart instanceof Uint32Array, "shortcutStart is a Uint32Array");
|
||
assert.equal(result.shortcutStart.length, input.nodeCount + 1, "CSR row pointers: N+1 entries");
|
||
for (let u = 0; u < input.nodeCount; u++) {
|
||
for (let s = result.shortcutStart[u]; s < result.shortcutStart[u + 1]; s++) {
|
||
const to = result.shortcutTarget[s];
|
||
const via = result.shortcutVia[s];
|
||
assert.ok(
|
||
result.rank[u] > result.rank[via],
|
||
`shortcut ${u}->${to}: rank(from)=${result.rank[u]} > rank(via)=${result.rank[via]}`,
|
||
);
|
||
assert.ok(
|
||
result.rank[to] > result.rank[via],
|
||
`shortcut ${u}->${to}: rank(to)=${result.rank[to]} > rank(via)=${result.rank[via]}`,
|
||
);
|
||
}
|
||
}
|
||
});
|
||
|
||
test("C4 hand fixture — the 3-node star yields its literal contraction order and shortcut set", async () => {
|
||
const { contractGraph } = await loadContraction();
|
||
const result = contractGraph(handInput());
|
||
// Literal rank (hand-computed in handInput's doc comment): the mid node
|
||
// (id 0) contracts first on the priority tie; endpoints follow by id.
|
||
assert.deepEqual([...result.rank], [0, 1, 2], "rank: the mid node first, then endpoints by id");
|
||
// Literal shortcut set: 1->2 (via 0, w2) and 2->1 (via 0, w2).
|
||
assert.deepEqual([...result.shortcutStart], [0, 0, 1, 2], "CSR: node 0 has 0, node 1 has 1, node 2 has 1");
|
||
assert.deepEqual([...result.shortcutTarget], [2, 1], "targets: 1->2 and 2->1");
|
||
assert.deepEqual([...result.shortcutSeconds], [2, 2], "unit weights sum to 2");
|
||
assert.deepEqual([...result.shortcutVia], [0, 0], "both shortcuts ride the contracted mid node");
|
||
assert.equal(result.stats.shortcutCount, 2);
|
||
});
|
||
|
||
test("C5 overlay witness law — a contracted node cannot witness a shortcut (the #1 trap)", async () => {
|
||
const { contractGraph } = await loadContraction();
|
||
const result = contractGraph(overlayInput());
|
||
// Hand-traced (overlayInput's doc comment): the bypass (node 0)
|
||
// contracts first; when the mid node u (node 1) contracts, its pair
|
||
// (a=2 -> b=3) has NO overlay witness left (the bypass is contracted),
|
||
// so the shortcut 2->3 (via 1) MUST be emitted — the emitted shortcut
|
||
// is exactly what keeps the overlay distance-preserving.
|
||
const found = [];
|
||
for (let u = 0; u < 4; u++) {
|
||
for (let s = result.shortcutStart[u]; s < result.shortcutStart[u + 1]; s++) {
|
||
found.push({ from: u, to: result.shortcutTarget[s], seconds: result.shortcutSeconds[s], via: result.shortcutVia[s] });
|
||
}
|
||
}
|
||
assert.equal(found.length, 1, `exactly the one required shortcut was emitted (got ${JSON.stringify(found)})`);
|
||
assert.equal(found[0].from, 2, "shortcut source is a");
|
||
assert.equal(found[0].to, 3, "shortcut target is b");
|
||
assert.equal(found[0].via, 1, "via is the contracted mid node u");
|
||
assert.ok(Math.abs(found[0].seconds - 2) < 1e-6, "weight is the 1+1 sum");
|
||
});
|
||
|
||
test("C6 explosion tripwire — fails loud above CH_SHORTCUT_EXPLOSION_RATIO * nodeCount; a healthy graph passes", async () => {
|
||
const { contractGraph, CH_SHORTCUT_EXPLOSION_RATIO, CH_WPS_MAX_SETTLED, CH_WPS_SETTLED_PER_DEGREE } =
|
||
await loadContraction();
|
||
assert.equal(CH_SHORTCUT_EXPLOSION_RATIO, 4, "the tripwire ratio is the named constant");
|
||
assert.equal(CH_WPS_MAX_SETTLED, 60, "the witness settle budget floor is the named constant");
|
||
assert.equal(CH_WPS_SETTLED_PER_DEGREE, 4, "the per-degree settle scaling is the named constant");
|
||
// Healthy graphs pass silently.
|
||
assert.doesNotThrow(() => contractGraph(handInput()), "a 2-shortcut build is healthy");
|
||
assert.doesNotThrow(() => contractGraph(pairsInput()), "the two-gadget build is healthy");
|
||
// The hand-traced cascade: 42 shortcuts on 9 nodes (4×9 = 36) — the
|
||
// message names the ratio and the measured count.
|
||
assert.throws(
|
||
() => contractGraph(explosionInput()),
|
||
(err) => {
|
||
assert.ok(err instanceof Error, "the tripwire throws an Error");
|
||
assert.match(err.message, /shortcut explosion/, "the message names the failure");
|
||
assert.match(err.message, /42/, "the message names the measured shortcut count");
|
||
assert.match(err.message, /4/, "the message names the ratio");
|
||
return true;
|
||
},
|
||
"the budget-miss cascade fails loud above the ratio",
|
||
);
|
||
});
|
||
|
||
test("C7 determinism — identical input yields byte-identical rank and shortcut arrays", async () => {
|
||
const { contractGraph } = await loadContraction();
|
||
const a = contractGraph(pairsInput());
|
||
const b = contractGraph(pairsInput());
|
||
assert.deepEqual([...a.rank], [...b.rank], "ranks identical");
|
||
assert.deepEqual([...a.shortcutStart], [...b.shortcutStart], "CSR pointers identical");
|
||
assert.deepEqual([...a.shortcutTarget], [...b.shortcutTarget], "targets identical");
|
||
assert.deepEqual([...a.shortcutSeconds], [...b.shortcutSeconds], "seconds identical");
|
||
assert.deepEqual([...a.shortcutVia], [...b.shortcutVia], "via identical");
|
||
assert.equal(a.stats.witnessSearches, b.stats.witnessSearches, "even the stats are deterministic");
|
||
// The oneway bit0 law: a blocked mirror edge is never relaxed — dropping
|
||
// the traversable direction changes the result; the FLAGGED one does not.
|
||
const withBlocked = {
|
||
nodeCount: 3,
|
||
edges: [
|
||
{ from: 0, to: 1, seconds: 1, flags: 0 },
|
||
{ from: 1, to: 0, seconds: 1, flags: 1 }, // bit0: stored, NEVER relaxed
|
||
{ from: 1, to: 2, seconds: 1, flags: 0 },
|
||
{ from: 2, to: 1, seconds: 1, flags: 0 },
|
||
],
|
||
};
|
||
const blocked = contractGraph(withBlocked);
|
||
// 1->0 is blocked, so node 0 has no in-edge: contracting 1 emits only 0->2.
|
||
assert.deepEqual([...blocked.shortcutStart], [0, 1, 1, 1], "only node 0's shortcut exists");
|
||
assert.deepEqual([...blocked.shortcutTarget], [2], "0->2 via 1");
|
||
assert.deepEqual([...blocked.shortcutVia], [1]);
|
||
assert.equal(blocked.stats.shortcutCount, 1, "the bit0 edge was never relaxed");
|
||
});
|