maxTime = 10

font-size: ${.83 * nodeLabelSize}px;

let lineHeight = 1.75 * queueFontSize;

let textX = 14*queueFontSize, textY = rows + lineHeight; // REMOVE

let currentTextX = 14 * queueFontSize;

let currentNodeX = currentTextX + 1.5 * nodeRadius;

let currentTextHeight = 1.5 * lineHeight;

let nodeOffset = -3;

let diagram = drawDijkstraDiagram(graph, state);

let diagramY = currentTextHeight;

let queueY = diagramY + rows + .75*lineHeight;

let queueHeight = 4 * lineHeight;

let queueX = 4.5 * queueFontSize;

let queueNodeRadius = Math.min(nodeRadius, .667 * queueFontSize);

let queueNodeLabelSize = 1.38 * queueNodeRadius;

let queueNodeX = queueX + 2*queueNodeRadius;

let queueNodeOffset = -1;

let totalHeight = queueY + queueHeight;

diagram = svg`

<g class=label>

<text text-anchor=middle x="${columns/2}">Edges in progress</text>

<text text-anchor=end y=${lineHeight} x=${queueX}>at time</text>

<text text-anchor=end y=${2*lineHeight} x=${queueX}>fluid from</text>

<text text-anchor=end y=${3*lineHeight} x=${queueX}>will reach</text>

</g>

<g class=nodes transform="translate(${queueNodeX}, ${lineHeight})">

${state.queue.map((e,i) => {

let x = 2.75*i*queueNodeRadius;

let y = 0;

let visited = e.dst in state.visited_nodes ? "visited" : "";

let rectangle = "";

if (e.src == state.node && state.neighbors.includes(e.dst)) {

rectangle = `<rect class=new x=${x-2.75/2*queueNodeRadius} y=${-.5*lineHeight} width=${2.75*queueNodeRadius} height=${3*lineHeight} fill="none" />`

}

return `${rectangle}

<line class=edges x1=${x} x2=${x} y1=${lineHeight} y2=${2*lineHeight} />

<text style="fill: black;" x=${x} y=0 text-anchor=middle>${e.dst_time}</text>

<g class=nodes transform="translate(0, ${queueNodeOffset})">

<circle class="nodes ${visited}" r=${queueNodeRadius} cx=${x} cy=${2*lineHeight} />

<text class=node-label x=${x} y=${2*lineHeight}>${e.dst.toUpperCase()}</text>

<circle class="nodes visited" r=${queueNodeRadius} cx=${x} cy=${1*lineHeight} />

<text class=node-label x=${x} y=${1*lineHeight}>${e.src.toUpperCase()}</text>

</g>

`})}

</g>

</g>

</svg>

`;

return diagram;

/*

// hack for iPad, which shrinks it to nothing if we don't provide a width or height! ugh.

diagram.style="min-width: 20em;"

let body = "";

for (let {src,dst,dst_time} of state.queue) {

body += `<tr><td>${dst_time}</td><td>Reach ${dst.toUpperCase()}</td></tr>`

}

// TODO: instead of just time, a caption, e.g. "at time 2, fluid reaches node B from node A"

// TODO: indicate which neighbors were just added to the queue w/ outline and hilight in table

return html`

<center><i>time =</i> ${state.time}</center>

<div style="display: flex; align-items: flex-start;">

${diagram}

<table style="width: 12em;">

<thead>

<tr style="border-bottom: none;"><th colspan=2 style="font-size: 110%; font-family: Source Serif Pro, serif; font-style: italic; font-weight: normal; text-align: center;">Event queue</th></tr>

<tr style="border-top: none;"> <th>Time</th> <th>Event</th> </tr> </thead>

<tbody> ${body} </tbody>

</table>

</div>

`

*/

}

let {time, visited_nodes, visited_edges, queue} = state;

let node_svg = ``, edge_svg = ``, queue_svg = ``, label_svg = ``;

// NODES

for (let [name, v] of Object.entries(graph.nodes)) {

let c = (name in visited_nodes) ? "visited" : "";

let a = name == state.node ? "active" : "";

if (state.neighbors.includes(name)) {

//edge_svg += `<circle fill=none class=new cx=${v.x} cy=${v.y} r=${1.33*nodeRadius} />`;

//node_svg += `<circle fill-opacity=.33 fill=none class=new cx=${v.x} cy=${v.y} r=${1.33*nodeRadius} />`;

}

node_svg += `<circle class="${c} ${a}" id="node-${name}" cx=${v.x} cy=${v.y} r=${nodeRadius} />\n`;

if (true || name == state.node || state.queue.some(e => e.dst == name))

node_svg += `<text class=node-label x=${v.x} y=${v.y}>${name.toUpperCase()}</text>\n`;

}

// EDGES & LABELS

for (let {src,dst,length} of graph.edges) {

let c = (visited_edges.some(([s,d]) => (s == src && d == dst) || (s == dst && d == src)))

? "visited" : "";

let v = graph.nodes[src], u = graph.nodes[dst];

edge_svg += `<line class="${c}" id="edge-${src}-${dst}" x1=${v.x} y1=${v.y} x2=${u.x} y2=${u.y} />\n`;

let lx = (v.x + u.x)/2, ly = (v.y+u.y)/2;

let dx = v.x-u.x, dy = v.y-u.y;

let distance = Math.sqrt(dx*dx+dy*dy);

let ox = labelOffset*dy/distance, oy = -labelOffset*dx/distance;

label_svg += `<text x=${lx+ox} y=${ly+oy}>${length}</text>\n`;

}

// QUEUE

for (let {src,dst,src_time,dst_time} of queue) {

// This avoids creating zero-length lines, which can ugly up the diagram.

if (time == src_time) continue;

let progress = (time - src_time)/(dst_time - src_time);

let v = graph.nodes[src], u = graph.nodes[dst];

let dx = u.x-v.x, dy = u.y-v.y; // vector from v to u

let distance = Math.sqrt(dx*dx + dy*dy);

// we offset the start of the blue water by the node radius

let vx = v.x + nodeRadius*dx/distance, vy = v.y + nodeRadius*dy/distance;

let ux = u.x - nodeRadius*dx/distance, uy = u.y - nodeRadius*dy/distance;

//ux = u.x; uy = u.y;

let x2 = vx + progress * (ux-vx), y2 = vy + progress * (uy-vy);

// console.log(src, dst, progress, v.x, x2, y2);

queue_svg += `<line x1=${v.x} y1=${v.y} x2="${x2}" y2="${y2}" />\n`

}

return svg`

let {time, visited_nodes, visited_edges, queue, path_edges} = state;

options = options === undefined ? [] : options.split(",");

let node_svg = ``, edge_svg = ``, queue_svg = ``, label_svg = ``;

// NODES

for (let [name, v] of Object.entries(graph.nodes)) {

let c = (name in visited_nodes) ? "visited" : "";

node_svg += `<circle class="${c}" id="node-${name}" cx=${v.x} cy=${v.y} r=${nodeRadius} />\n`;

if (options.includes("distances") && name in state.visited_nodes && name != graph.start) {

node_svg += `<text class=node-label x=${v.x} y=${v.y}>${state.visited_nodes[name]}</text>\n`;

}

}

// EDGES & LABELS

for (let {src,dst,length} of graph.edges) {

let c = (visited_edges.some(([s,d]) => (s == src && d == dst) || (s == dst && d == src)))

? ("visited" + (options.includes("paths") ? " longer" : "")) : "";

let v = graph.nodes[src], u = graph.nodes[dst];

edge_svg += `<line class="${c}" id="edge-${src}-${dst}" x1=${v.x} y1=${v.y} x2=${u.x} y2=${u.y} />\n`;

let lx = (v.x + u.x)/2, ly = (v.y+u.y)/2;

let dx = v.x-u.x, dy = v.y-u.y;

let distance = Math.sqrt(dx*dx+dy*dy);

let ox = labelOffset*dy/distance, oy = -labelOffset*dx/distance;

label_svg += `<text x=${lx+ox} y=${ly+oy}>${length}</text>\n`;

let ok = (([s,d]) => (s == src && d == dst) || (s == dst && d == src));

if (options.includes("paths") && path_edges.some(ok)) {

let [src,dst] = path_edges.find(ok);

let v = graph.nodes[src], u = graph.nodes[dst];

let length = .88*nodeRadius;

let dx = length*(u.x-v.x)/distance, dy = length*(u.y-v.y)/distance;

let o = 1.414*strokeWidth;

let ox= o*(v.y-u.y)/distance, oy = o*(u.x-v.x)/distance;

let l = (length/2 + nodeRadius)/distance;

let lx = u.x + l*(v.x-u.x), ly = u.y + l*(v.y-u.y);

edge_svg += `<g class=shortest>

<line x1=${v.x} y1=${v.y} x2=${u.x} y2=${u.y} />

<polygon stroke-width=${strokeWidth/4}px stroke-linejoin="round" points="${lx+dx} ${ly+dy}

${lx-dx+ox} ${ly-dy+oy}

${lx} ${ly}

${lx-dx-ox} ${ly-dy-oy}" />

</g>

`;

}

}

// QUEUE

for (let {src,dst,src_time,dst_time} of queue) {

// This avoids creating zero-length lines, which can ugly up the diagram.

if (time == src_time) continue;

let progress = (time - src_time)/(dst_time - src_time);

let v = graph.nodes[src], u = graph.nodes[dst];

let dx = u.x-v.x, dy = u.y-v.y; // vector from v to u

let distance = Math.sqrt(dx*dx + dy*dy);

// we offset the start of the blue water by the node radius

let vx = v.x + nodeRadius*dx/distance, vy = v.y + nodeRadius*dy/distance;

let ux = u.x - nodeRadius*dx/distance, uy = u.y - nodeRadius*dy/distance;

//ux = u.x; uy = u.y;

let x2 = vx + progress * (ux-vx), y2 = vy + progress * (uy-vy);

// console.log(src, dst, progress, v.x, x2, y2);

queue_svg += `<line x1=${v.x} y1=${v.y} x2="${x2}" y2="${y2}" />\n`

}

return svg`<svg class=diagram viewBox="0 0 ${columns} ${rows}">

<g class=edges> ${edge_svg} <g class=in-progress> ${queue_svg} </g> </g>

<g class=nodes> ${node_svg} </g>

<g class=edge-label> ${label_svg} </g>

</svg>`

}

node_strings = ["a 0 0", "b 1 2", "c 3 0", "d 5 2", "e 6 0"]

function stateAt(time) {

const state = dijkstra_states.slice().reverse().find(x => x.time <= time);

// Remarkably, the only thing we need to update is time; the only thing that changes in between dijkstra states is the progress of fluid along the edges in the queue, and that can be calculated from the current time and the source and destination times in the queue.

return {...state, time};

dijkstra_states = {

let time = 0;

// visited_nodes maps node names to the time they were reached

let visited_nodes = {};

// list of visited edges, represented as two-element arrays [src,dst]

let visited_edges = [];

// a queue entry is {src, dst, src_time, dst_time}

let queue = [];

// Edges of shortest paths, oriented towards the source

let path_edges = [];

// a state is {time, node, visited_nodes, visited_edges, queue}

let states = [];

function reach(v) {

visited_nodes[v] = time;

let neighbors = [];

for (let {src,dst,length} of graph.edges) {

if (dst == v) [src,dst] = [dst,src];

if (src != v) continue;

// In Dijkstra's we would normally avoid traversing edges to already-seen nodes, but when simulating fluid flow this is inappropriate.

//if (visited_nodes.includes(dest)) continue;

// Instead we avoid traversing edges we have already traversed in the opposite direction (such as the edge which brought us here).

if (visited_edges.some(([s,d]) => s == dst && d == src)) continue;

neighbors.push(dst);

queue.push({src, dst, src_time: time, dst_time: time + length})

}

// The world's worst priority queue implementation: sort after every batch of insertions

queue.sort((a,b) => a.dst_time-b.dst_time);

return neighbors

}

function visit(node) {

let neighbors = [];

if (!(node in visited_nodes)) neighbors = reach(node);

states.push({

time, node, neighbors,

path_edges: path_edges.slice(),

visited_nodes: {...visited_nodes},

visited_edges: visited_edges.slice(),

queue: queue.slice(),

})

}

visit(graph.start);

// trick to avoid inflooping in case I make a mistake

for (let i = 0; queue.length != 0 && i <= 2*graph.edges.length; i++) {

let {dst_time, src, dst} = queue.shift();

time = dst_time;

visited_edges.push([src,dst]);

if (!(dst in visited_nodes))

path_edges.push([src,dst]);

visit(dst);

}

if (queue.length != 0) { throw "oops" }

return states

let nodes = {}, edges = [];

for (let i = 0; i <= numberNodes; i++) {

nodes[i] = {x: Math.floor(1 + Math.random() * (columns-1)),

y: Math.floor(1 + Math.random() * (rows-1))}

}

for (let i = 0; i <= numberEdges; i++) {

let j = Math.floor(numberNodes * Math.random());

let k = Math.floor((numberNodes-1) * Math.random());

if (j <= k) k++;

edges.push({src: ""+j, dst: ""+k,

length: 1 + Math.floor(Math.random() * 16)});

}

return {nodes, edges, start: "0"}