Public
Edited
Dec 14, 2022
Importers
16 stars
Hello, PGLiteINSEE ParquetHello, apcachDruidJS workerHello, OrbitWord Tour: 40k words and their friendsHello, spectral.jsHello, petite-vueHello, @thi.ng/grid-iteratorsHello, thumbhashHello, SwissGLHello, QOI (and glitches)Hello, orbHello, cosmographHello, TabulatorUsing d3.blur with PlotMath.cbrtHello debounceColorcetHello, gliiHello, Open MeteoHello, PyWaveletsHello, typesenseHello, libgifHello, kmeans-engineHappy anniversary, Project Gutenberg!Hello, fflateHello, ArchieML!Hello, d3-bboxCollideHello, jsgeoda!Hello, EDTF!Hello, protovis!Hello, placekeyHello, fuse.jsHello, Reorder.jsHello, shadow DOMjszipHello, procedural-glHello, qhullHello, genetic-jsDruidJSHello, Tippy.jsHello, paintWorkletBig πHello, AutoencoderHello, Shakespearean UUIDsHello, ccwt.jsHello, constrainautorHello, talismanHello, polygon-offsetHello p-queueHello async-poolHello rollup-plugin-asciiHello, algebra.jsHello, pixi.jsHello, d3-renderHello zip/unzipCumulative Wikipedia DonationsHTML <details>regl textureHello, npyjsHello protobufHello, pencil touchHello, LOESSHello html2canvaslegra mapscolor2cssHello, ecsy2D point distributionsHello, delatinThe gpu.js loopHello nojacko/Dijkstras-jsHello, tcort/dijkstrajsHello, lambdabaa/dijkstraHello, gpu.js v2Hello jsqrHello qrcodeHello SharedArrayBufferHello GamePad APIHello vtk.jsHello nd4jsHello BiofabricTravelling with a self-organizing mapHello glitchHello UMAP-jsHello pandemoniumHello iocaneHello JSON-editorHello d3-griddingHello mljs/knnWorkerHello lalolibImage to GPU.jsImage to blink.jsTissot's indicatrixVega projectionsHello WebCLGLUsing d3-inertia with observableVideo contouring 3ngraph: pagerank, louvain…Union-FindPerceptron (simple statistics)mljsHello h3-jsEmoji FlagsHello, poisson-disk-sampling
Dijkstra’s shortest-path tree
function* shortest_tree({ graph, origins, cutoff, step }) {
const start_time = performance.now(),
_step = step === undefined ? 0 : +step,
neigh = new Map();
let n = 0;
// populate a fast lookup Map of links indices for each source
for (let i = 0, l = graph.sources.length; i < l; i++) {
const a = +graph.sources[i],
b = +graph.targets[i];
if (!neigh.has(a)) neigh.set(a, []);
neigh.get(a).push(i);
// keep track of the highest node’s id
n = Math.max(n, a + 1, b + 1);
}
const q = new FlatQueue(),
front = q.ids,
cost = new Float64Array(n).fill(Infinity),
predecessor = new Int32Array(n).fill(-1),
origin = new Int32Array(n).fill(-1),
status = {
cost,
predecessor,
origin,
step: 0,
front,
max_front_size: 0,
ended: false
};
origins.forEach(node => {
if (isFinite(node)) node = { id: node, cost: 0 };
if (node.id < n) {
origin[node.id] = node.id;
q.push(node.id, (cost[node.id] = node.cost));
}
});
const time = performance.now();
while (q.length > 0) {
const curr = q.peekValue(),
node = q.pop();
if (curr > cost[node]) continue; // ignore obsolete elements
if (neigh.has(node)) {
for (const i of neigh.get(node)) {
const c = graph.costs ? +graph.costs[i] : 1;
if (!isFinite(c)) continue;
const tentative = c + cost[node];
if (tentative > cutoff) continue;
const dest = graph.targets[i];
if (tentative >= 0 && tentative < cost[dest]) {
predecessor[dest] = node;
origin[dest] = origin[node];
q.push(dest, (cost[dest] = tentative));
status.max_front_size = Math.max(status.max_front_size, front.length);
}
}
}
status.step++;
if (_step && status.step % _step === 0) {
status.performance = performance.now() - time;
yield status;
}
}
status.ended = true;
status.performance = performance.now() - time;
yield status;
}
function shortest_paths(graph, tree) {
const paths = [];
const P = shortest_junctions(graph, tree);
for (const code of P.costs.keys()) {
const cost = P.costs.get(code),
junction = P.junctions.get(code),
path = junction.slice();
path.reverse();
while (tree.predecessor[path[0]] > -1)
path.unshift(tree.predecessor[path[0]]);
path.reverse();
while (tree.predecessor[path[0]] > -1)
path.unshift(tree.predecessor[path[0]]);
paths.push({ cost, junction, path });
}
return paths;
}
// returns the shortest path that connects i to j:
// - without stepping into other origins’ zones
// - without going above cutoff in each origin’s zone
function shortest_path(graph, tree, i, j) {
const P = shortest_junctions(graph, tree);
let cost = Infinity,
junction = [],
path = [];
const code = `${i}-${j}`;
if (P.costs.has(code)) {
cost = P.costs.get(code);
junction = P.junctions.get(code);
path = junction.slice();
path.reverse();
while (tree.predecessor[path[0]] > -1)
path.unshift(tree.predecessor[path[0]]);
path.reverse();
while (tree.predecessor[path[0]] > -1)
path.unshift(tree.predecessor[path[0]]);
}
return { cost, junction, path };
}
// returns the junctions between zones
function shortest_junctions(graph, tree) {
const origins = [...new Set(tree.origin)].filter(i => i > -1);
let costs = new Map(),
junctions = new Map();
for (let l = 0; l < graph.sources.length; l++) {
const i = tree.origin[graph.sources[l]],
j = tree.origin[graph.targets[l]];
if (i !== j && i > -1 && j > -1) {
const code = `${i}-${j}`;
const c =
graph.costs[l] +
tree.cost[graph.sources[l]] +
tree.cost[graph.targets[l]];
if (!costs.has(code) || c < costs.get(code)) {
costs.set(code, c);
junctions.set(code, [graph.sources[l], graph.targets[l]]);
}
}
}
return { costs, junctions };
}
shortest_tree_async = async args =>
args.worker !== false
? Generators.queue(worker(shortest_tree, args, `${FlatQueue.toString()}`))
: shortest_tree(args)
n = 100
origins = [0, 1, 2]
step = 10 // yield every … steps
run_args = ({
worker: true,
origins,
graph,
cutoff,
step
})
run = shortest_tree_async(run_args)
FlatQueue = require("flatqueue")
import { worker } from "@fil/worker"
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
