here to learn
Published
Edited
Feb 15, 2019
Importers
10 stars
MathJaxPolygon inputMultiple SankeysDrag to re-arrange (vertical edition)d3 quadtrees with more dataHexagonal World (coloring by country)DLA + CA rules!Fullscreen CanvasD3 ScatterplotD3 Log-Scaled HistogramDijkstra's algorithm (d3-delaunay version)TOCNotebook Visualizer (Firefox-compatible)Lazy DownloadDOM.download(callback) feature request [solved]Version Pinning for Notebooks
Dijkstra's algorithm (huge version)
function dijkstra(pts) { // The unvisited set
const Q = new BHeap(({dist}) => dist);
const dist = new Map();
const prev = new Map();
const prevEdge = new Map();
const visit = new Map();
pts.forEach(pt => {
dist.set(pt, Infinity);
prev.set(pt, undefined);
Q.push({pt, dist:pt === pts[0] ? 0 : Infinity});
});
dist.set(pts[0], 0);
while (Q.size()) {
// Find the node with least distance.
// Remove it from the visited queue.
const u = Q.pop().pt;
if (visit.has(u)) continue;
visit.set(u, true);
const minDistance = dist.get(u);
for (const edge of u.edges) {
const v = edge.source === u ? edge.target : edge.source;
const alt = dist.get(u) + edge.distance;
if (alt < dist.get(v)) {
dist.set(v, alt);
prev.set(v, u);
prevEdge.set(v, edge);
Q.push({pt:v, dist:alt});
}
}
}
return {dist, prev, prevEdge};
}
// http://eloquentjavascript.net/1st_edition/appendix2.html
class BHeap {
constructor(score, compare=null) {
this._arr = [];
this.score = score;
this.compare = compare ? compare : (a,b) => a >= b; // min-heap, bigger score goes later
}
push(x) {
this._arr.push(x);
this.bubbleUp(this._arr.length-1);
}
pop() {
const result = this._arr[0];
const last = this._arr.pop();
if (this._arr.length > 0) {
this._arr[0] = last;
this.bubbleDown(0);
}
return result;
}
size() {
return this._arr.length;
}
bubbleUp(n) {
const val = this._arr[n];
const score = this.score(val);
while (n > 0) {
const parentN = Math.floor((n+1)/2) - 1;
const parent = this._arr[parentN];
if (this.compare(score, this.score(parent))) break;
this._arr[parentN] = val;
this._arr[n] = parent;
n = parentN;
}
}
bubbleDown(n) {
const length = this._arr.length;
const val = this._arr[n];
const score = this.score(val);
while (true) {
const child2N = 2*(n+1);
const child1N = child2N-1;
let swap = null;
let child1,
child1score;
if (child1N < length) {
child1 = this._arr[child1N];
child1score = this.score(child1);
if (!this.compare(child1score, score)) {
swap = child1N;
}
}
if (child2N < length) {
const child2 = this._arr[child2N];
const child2score = this.score(child2);
if (!this.compare(child2score, (swap === null ? score : child1score))) {
swap = child2N;
}
}
if (swap === null) break;
this._arr[n] = this._arr[swap];
this._arr[swap] = val;
n = swap;
}
}
}
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.
