drawDijkstra(graph, dijkstra_states[step0])
draw(graph,dijkstra_states[step0])
drawDijkstra = (graph, state) => {
let x = draw(graph, state);
x = html`<p>WHAT IS GOING ON</p>`
x.style = "background-color: green;"
console.log(x);
let body = "";
for (let {src,dst,dst_time} of state.queue) {
body += `<tr><td>${dst_time}</td><td>Reach ${dst}</td></tr>`
}
//return draw(graph, state)
return html`
<center><i>time =</i> ${state.time}</center>
<table><tr>
<td>
<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>
</td>
<td>${x}</td>
<td><svg viewBox="0 0 100 100" width=300px height=100px><text x=0 y=50>hello</text>
<rect fill="black"stroke=blue stroke-width=5 x=0 y=0 width=20 height=20> </rect>
</svg></td>
</tr>
</table>
`
}
html`<h2>CSS</h2><style>
svg { max-height: 12em; }
.nodes { fill: hsl(15, 67%, 33%); }
.nodes .visited { fill: hsl(230, 40%, 62%); }
.edges { stroke-width: ${strokeWidth}px; stroke: hsl(20, 45%, 75%); }
.edges .visited, .in-progress { stroke: hsl(230, 40%, 60%); }
.in-progress line { stroke-linecap: round; }
svg .labels text {
font-size: ${labelSize}px; font-family: Noto Sans, Open Sans, Verdana, Source Sans Pro, sans-serif; font-variant-numeric: proportional-nums;
/* NB. iPadOS chrome/safari calculated baseline offsets in DISCRETE PIXELS */
text-anchor: middle; dominant-baseline: central;
}
</style>`
function draw(graph, state) {
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" : "";
node_svg += `<circle class="${c}" id="node-${name}" cx=${v.x} cy=${v.y} r=${nodeRadius} />\n`;
}
// sort our edges
// 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}" 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`;
// TODO: we need to do some offsetting logic here, like in the case for in progress edges
/*for (let i = 0; i <= length; i++) {
let offset = distance/length
label_svg += `<line x1=${} />\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`<svg 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=labels> ${label_svg} </g>
</svg>`
}
md`## FURTHER DETAILS TO DISCUSS / THINGS TO DO
- Improve the final diagram
- What if the fluid meets in the middle of an edge?
- An introduction
- A conclusion, with links to redblobgames' version
- How do we extract the actual shortest paths, or the spanning tree?
- What is the asymptotic complexity of this approach?
- maybe give some pseudocode?
`
//maxTime = dijkstra_states[dijkstra_states.length-1].time
maxTime = 10
labelOffset = strokeWidth + labelSize/2
// node_strings = ["a 1 1", "b 1 3", "c 3 1", "d 5 3", "e 5 1", "f 8 5"]
node_strings = ["a 0 0", "b 1 2", "c 3 0", "d 5 2", "e 6 0"]
edge_strings = ["a b 2", "c a 5", "b d 10", "c d 2", "b c 4", "d e 3", "e c 5"]
emptyState = ({time: null, visited_nodes: {}, visited_edges: [], queue: []})
// Produces {time, visited_nodes, visited_edges, queue}
function stateAt(time) {
const {visited_nodes, visited_edges, queue} = 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 {time, visited_nodes, visited_edges, queue};
}
// Produces a list of states. A state is an object {time, visited_nodes, visited_edges, queue}.
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 = [];
function visit(v) {
visited_nodes[v] = time;
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;
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);
}
visit(graph.start);
let currentState = () => ({time, visited_nodes: {...visited_nodes}, visited_edges: visited_edges.slice(), queue: queue.slice() })
let states = [currentState()];
// 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)) visit(dst);
states.push(currentState());
}
if (queue.length != 0) { throw "oops" }
return states
}
edgeName = (src,dst) => "" + [src,dst].sort()
viewof numberNodes = Inputs.range([1,50], {label: "Number of nodes", step: 1, value: 10})
viewof numberEdges = Inputs.range([1,50], {label: "Number of edges", step: 1, value: 10})
randomGraph = {
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"}
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.