79 lines
3.8 KiB
JavaScript
79 lines
3.8 KiB
JavaScript
import { strict as assert } from 'node:assert';
|
|
import { test } from './harness.mjs';
|
|
import { encodeGraph, decodeGraph } from '../src/graph.ts';
|
|
import { landmarkTables } from '../src/landmark.ts';
|
|
import { routeDirectionSplit } from '../scripts/experiment-alt-direction-split.mjs';
|
|
|
|
function fixture(n, edges, anchors) {
|
|
const q = 1;
|
|
const tables = landmarkTables({ nodeCount: n, edges: edges.map(e => ({ ...e, flags: e.flags ?? 0 })), quantumS: q }, Uint32Array.from(anchors));
|
|
const lat = Array(n).fill(3.14), lng = Array(n).fill(101.68);
|
|
return decodeGraph(encodeGraph({ lat, lng, edges, names: [], maxSpeedKmh: 120, landmarks: { nodes: anchors, quantumS: q, ...tables } }));
|
|
}
|
|
|
|
// Independent O(V²) oracle, not the experiment's heap-based Dijkstra.
|
|
function oracle(g, o, target) {
|
|
const d = Array(g.nodeCount).fill(Infinity), seen = new Set(); d[o] = 0;
|
|
for (let k = 0; k < g.nodeCount; k++) {
|
|
let u = -1;
|
|
for (let v = 0; v < g.nodeCount; v++) if (!seen.has(v) && (u < 0 || d[v] < d[u])) u = v;
|
|
if (u < 0 || d[u] === Infinity) break;
|
|
if (u === target) return d[u];
|
|
seen.add(u);
|
|
for (let e = g.edgeStart[u]; e < g.edgeStart[u + 1]; e++) if (!(g.edgeFlags[e] & 1)) d[g.edgeTarget[e]] = Math.min(d[g.edgeTarget[e]], d[u] + g.edgeSeconds[e]);
|
|
}
|
|
return Infinity;
|
|
}
|
|
|
|
function checkAll(graph) {
|
|
assert.ok(graph);
|
|
for (let o = 0; o < graph.nodeCount; o++) for (let g = 0; g < graph.nodeCount; g++) {
|
|
const actual = routeDirectionSplit(graph, o, g), expected = oracle(graph, o, g);
|
|
assert.equal(actual === null, expected === Infinity, `${o}→${g} reachability`);
|
|
if (!actual) continue;
|
|
assert.ok(Math.abs(actual.seconds - expected) <= 1e-6, `${o}→${g} cost ${actual.seconds} != ${expected}`);
|
|
assert.equal(actual.nodes[0], o); assert.equal(actual.nodes.at(-1), g);
|
|
let sum = 0;
|
|
for (let i = 1; i < actual.nodes.length; i++) {
|
|
const a = actual.nodes[i - 1], b = actual.nodes[i];
|
|
const edgeIds = [];
|
|
for (let e = graph.edgeStart[a]; e < graph.edgeStart[a + 1]; e++) if (graph.edgeTarget[e] === b && !(graph.edgeFlags[e] & 1)) edgeIds.push(e);
|
|
assert.equal(edgeIds.length, 1, `illegal ${a}→${b}`);
|
|
sum += graph.edgeSeconds[edgeIds[0]];
|
|
}
|
|
assert.ok(Math.abs(sum - actual.seconds) <= 1e-6);
|
|
}
|
|
}
|
|
|
|
test('direction split: directed ring, blocked mirrors, incoming spur and equal alternatives', () => {
|
|
checkAll(fixture(6, [
|
|
...[0, 1, 2, 3].map(u => ({ from: u, to: (u + 1) % 4, seconds: 2 })),
|
|
{ from: 1, to: 0, seconds: 1, flags: 1 }, { from: 0, to: 3, seconds: 1, flags: 1 },
|
|
{ from: 4, to: 1, seconds: 3 }, { from: 4, to: 2, seconds: 5 },
|
|
{ from: 0, to: 5, seconds: 2 }, { from: 3, to: 5, seconds: 2 },
|
|
], [0, 2, 4]));
|
|
});
|
|
|
|
test('direction split: one-way bridge both travel directions, anchored and unanchored islands', () => {
|
|
checkAll(fixture(9, [
|
|
{ from: 0, to: 1, seconds: 1 }, { from: 1, to: 0, seconds: 1 },
|
|
{ from: 1, to: 2, seconds: 2 }, { from: 2, to: 3, seconds: 1 }, { from: 3, to: 2, seconds: 1 },
|
|
{ from: 3, to: 2, seconds: 1, flags: 1 },
|
|
{ from: 4, to: 5, seconds: 1 }, { from: 5, to: 4, seconds: 1 },
|
|
{ from: 6, to: 7, seconds: 1 }, { from: 7, to: 6, seconds: 1 },
|
|
], [0, 3, 4]));
|
|
});
|
|
|
|
test('direction split: per-node skip adversary on finite→sentinel boundary and mixed clean/dirty columns', () => {
|
|
// At edge 1→2, to(anchor 0) at 1 is finite only via 1→0, while 2 cannot reach 0.
|
|
// At edge 1→2, from(anchor 2) at 1 is sentinel and at 2 finite.
|
|
const graph = fixture(5, [
|
|
{ from: 1, to: 0, seconds: 100 }, { from: 1, to: 2, seconds: 1 },
|
|
{ from: 2, to: 3, seconds: 1 }, { from: 3, to: 2, seconds: 1 },
|
|
{ from: 3, to: 4, seconds: 1 }, { from: 4, to: 3, seconds: 1 },
|
|
], [0, 2, 3]);
|
|
assert.equal(graph.landmarkTo[2], 0xffff);
|
|
assert.equal(graph.landmarkFrom[2 * 5 + 1], 0xffff);
|
|
checkAll(graph);
|
|
});
|