2a:null 2b:["$","title",null,{"children":"Efficient Graph Search | Philippe Rigovanov | Observable"}] 30:T5fc,plot = (step, stepIndex, frame) => Plot.plot({ className: "plot", style: { background: "transparent" }, marks: [ frame ? Plot.frame({ fill: stepIndex + 1 < completedAfter ? "transparent" : stepIndex + 1 == completedAfter ? "#FFF9C8" : "#eee", inset: -r * 2 + 1 }) : null, Plot.link(G.edges, { x1: ([u, v]) => vertX(u), y1: ([u, v]) => vertY(u), x2: ([u, v]) => vertX(v), y2: ([u, v]) => vertY(v), sort: ([u, v]) => selected(step, u, v), strokeWidth: ([u, v]) => (selected(step, u, v) ? 1.5 : 1), stroke: ([u, v]) => selected(step, u, v) }), Plot.dot([step.v], { x: vertX, y: vertY, stroke: "#EE2045", fill: "#eee", r: r + 2 }), Plot.dot(G.verts, { x: vertX, y: vertY, fill: (d) => step.u == d ? "active" : step.dist[d] < Infinity ? "notdone" : "done", r }) ], r: { type: "identity" }, caption: stepIndex + 1 == completedAfter ? `Step ${stepIndex + 1} (done!)` : `Step ${stepIndex + 1}`, color: { domain: [true, false, "done", "notdone", "active"], range: ["#EE2045", "#BCB6B1", "#BCB6B1", "#1D1917", "#EE2045"] }, x: { domain: [-radius, radius] }, y: { domain: [-radius, radius] }, width: size, height: size, axis: null, margin })31:[] 2e:{"id":"cfdfca832962a4db","slug":null,"title":"Efficient Graph Search","thumbnail":"6f2dfa8f1c85c61a6bccd8050bf0e8ce8e33810e717b41a70afce78497605106","access_level":"public","create_time":"$D2021-12-30T10:00:50.444Z","update_time":"$D2021-12-30T10:00:50.444Z","view_time":null,"first_public_time":"$D2022-12-16T23:39:50.415Z","fork":{"id":"654eb9e91b772a53","slug":"efficient-graph-search","title":"Efficient Graph Search","owner":{"id":"106fc7e7a0f11e48","login":"yurivish","name":"Yuri Vishnevsky"}},"stars":0,"starred":false,"owner":{"type":"team","id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":"starter_2024"},"version":1830,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null}],"members":[{"type":"individual","id":"968f76daa2a26d11","login":"a1ip","name":"Philippe Rigovanov","avatar_url":"https://avatars-next.observableusercontent.com/6359e02dc30dad37dc8aeff508f64823d0f57f42e9b940688bdd1af508bb839c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"f12a3f64915c0078","slug":"informatics","title":"Informatics","owner":{"id":"b5ee25cc13065361","login":"a1ip","name":"Philippe Rigovanov"}},"type":"notebook","body":{"title":"Efficient Graph Search","cells":[{"id":646,"value":"# Efficient Graph Search\n\nMany textbook implementations of [breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) contain a flaw: they are needlessly slow.\n\nTerence Kelly's [Drill Bits article](https://queue.acm.org/detail.cfm?id=3424304) describes the flaw and how to fix it. \n\nIt’s fun to see how this plays out visually, so here are a few pictures of the problem and how it can be solved.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":892,"value":"First, let's take a look at a textbook BFS implementation. The code below is adapted from [_Algorithms_](http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf) by Dasgupta, Papadimitriou, and Vazirani:\n\n```js\n${bfs.toString()}\n```","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1480,"value":"This algorithm is correct, but in some cases does extra work proportional to the number of vertices squared.\n\nWe can see the issue by looking at how this algorithm processes a [complete graph](https://en.wikipedia.org/wiki/Complete_graph), which has an edge between every pair of vertices. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1402,"value":"Plot.plot({\n marks: [\n Plot.link(G.edges, {\n x1: ([u, v]) => vertX(u),\n y1: ([u, v]) => vertY(u),\n x2: ([u, v]) => vertX(v),\n y2: ([u, v]) => vertY(v),\n stroke: \"#BCB6B1\"\n }),\n Plot.dot(G.verts, {\n x: vertX,\n y: vertY,\n fill: \"#8A837D\",\n r: 1 * r\n })\n ],\n r: { type: \"identity\" },\n color: {\n domain: [true, false, \"done\", \"notdone\", \"active\"],\n range: [\"#FD8842\", \"#BCB6B1\", \"#BCB6B1\", \"#1D1917\", \"#EE2045\"]\n },\n x: { domain: [-radius, radius] },\n y: { domain: [-radius, radius] },\n width: 1.5 * size,\n height: 1.5 * size,\n axis: null,\n margin\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":915,"value":"BFS on a complete graph starts at a source vertex and immediately visits all of the others, since each is just one hop away.\n\nOnce those vertices has been visited, *all of the useful work is done* — we now know the distance to every vertex from the source. But the textbook BFS is far from finished!\n\nSlide the slider below to watch the textbook algorithm play out.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":867,"value":"viewof bfsStepIndex = Inputs.range([0, steps.length - 1], {\n label: \"Step\",\n value: 0,\n step: 1,\n format: (d) => d + 1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":871,"value":"plot(steps[bfsStepIndex], bfsStepIndex, false)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":923,"value":"The ${redVertex} red vertex is the one being processed, the ${redOutlinedVertex} outlined vertex is a neighbor, and vertices turn ${blackVertex} black once they've been found.\n\nBy the ${V-1}th step all of the vertices have been found and processed, at which point we're done. \n\nBut because the neighbors of the first vertex were all enqueued, the algorithm proceeds to visit them, along with _their_ neighbors, which results in the inspection of ${steps.length-(V-1)} extra edges.\n\nFortunately, we can fix this with just a few lines of code:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1243,"value":"mdh`\n~~~js\n${bfsImproved\n .toString()\n .replace(\"let f = 1;\", \"___let f = 1;___\")\n .replace(\"if (++f == n) return dist;\", \"___if (++f == n) return dist;___\")}\n~~~\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1033,"value":"The added code tracks the number of vertices that have been found and finalized, and returns as soon as we've seen them all.\n\nIn the case of our complete graph this simple check takes the total number of steps down from ${steps.length} to ${V-1}:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":869,"value":"viewof bfsImprovedStepIndex = Inputs.range([0, V - 2], {\n label: \"Step\",\n value: 0,\n step: 1,\n format: (d) => d + 1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":877,"value":"plot(steps[bfsImprovedStepIndex], bfsImprovedStepIndex, true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":829,"value":"We can get a visceral sense for the amount of extra work by laying out all of the steps side-by-side. \n\nThe improved algorithm is finished by step ${V-1}:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":718,"value":"html`

${steps.slice(0, V - 1).map((d, i) => plot(d, i, true))}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1059,"value":"The textbook algorithm continues on, churning through ${steps.length-(V-1)} more edges before returning:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":656,"value":"html`

${steps\n .slice(V - 1)\n .map((d, i) => plot(d, i + V - 1, true))}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1201,"value":"Hopefully this primes your intuition for the problem and its solution. If you’d like to learn more, go read Terence Kelly's [article](https://queue.acm.org/detail.cfm?id=3424304).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1306,"value":"---\n\n
\n### Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":10,"value":"V = vScale(width)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":749,"value":"vScale = d3.scaleThreshold([400, 500, 750], [5, 6, 7, 8])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":372,"value":"r = Math.min(5, size * 0.035)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":327,"value":"margin = 2 * r","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":389,"value":"size = width / (V - 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":301,"value":"selected = (step, u, v) =>\n (u == step.u && v == step.v) || (u == step.v && v == step.u)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3,"value":"G = {\n let verts = array(V, (i) => i);\n let edges = [];\n for (let i = 0; i < V; i++) {\n for (let j = i + 1; j < V; j++) {\n edges.push([i, j]);\n }\n }\n let neighbors = array(V, (i) => array(V - 1, (j) => j + (j >= i)));\n return { verts, edges, neighbors };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":115,"value":"array = (length, f) => Array.from({ length }, (_, i) => f(i))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":58,"value":"function bfsTaped(G, s) {\n let dist = array(V, (i) => Infinity);\n let tape = [];\n dist[s] = 0;\n let Q = [s];\n while (Q.length > 0) {\n let u = Q.shift();\n for (let v of G.neighbors[u]) {\n if (dist[v] == Infinity) {\n dist[v] = dist[u] + 1;\n Q.push(v);\n }\n tape.push({ dist: dist.slice(0), u, v });\n }\n }\n return tape;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":780,"value":"// prettier-ignore\nfunction bfs(G, s) {\n // For all vertices `v` reachable from `s`, dist[v] is set\n // to the distance from `s` to `v`.\n let dist = new Array(V).fill(Infinity); // Init distances to ∞\n dist[s] = 0; // Init the source distance to zero\n let Q = [s]; // Init a queue containing just s \n while (Q.length > 0) { // While the queue is nonempty:\n let u = Q.shift(); // Pop the next vertex from the queue\n for (let v of G.neighbors[u]) { // For all edges (u, v):\n if (dist[v] == Infinity) { // If we haven't seen v before:\n dist[v] = dist[u] + 1; // Set its distance\n Q.push(v); // Push v onto the queue \n }\n }\n }\n return dist;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1393,"value":"// prettier-ignore\nfunction bfsImproved(G, s) {\n let dist = new Array(V).fill(Infinity); // Init distances to ∞\n dist[s] = 0; // Init the source distance to zero\n let Q = [s]; // Init a queue containing just s \n let f = 1; // Initialize the number of seen vertices\n while (Q.length > 0) { // While the queue is not empty:\n let u = Q.shift(); // Pop the next vertex from the queue\n for (let v of G.neighbors[u]) { // For all edges (u, v):\n if (dist[v] == Infinity) { // If we haven't seen v before:\n dist[v] = dist[u] + 1; // Set its distance\n if (++f == V) return dist; // Return if we've seen all V vertices\n Q.push(v); // Push v onto the queue \n }\n }\n }\n return dist;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":60,"value":"steps = bfsTaped(G, 0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":239,"value":"completedAfter = steps.findIndex((d) => d.dist.every((d) => d < Infinity)) + 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":15,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":35,"value":"vertX = (d) => radius * cos((tau * d) / V + tau / 4)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":38,"value":"vertY = (d) => radius * sin((tau * d) / V + tau / 4)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":28,"value":"tau = 2 * Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"radius = 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"cos = Math.cos","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":18,"value":"sin = Math.sin","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1240,"value":"// markdown with yellow and pink highlights (thanks Fil!)\nmdh = {\n const hljs = window.hljs || (await require(\"@observablehq/highlight.js\"));\n\n return function () {\n const node = md(...arguments);\n for (const fragment of node.querySelectorAll(\"code\")) {\n hljs.highlightBlock(fragment);\n\n fragment.innerHTML = fragment.innerHTML.replace(\n /___(.*?)___/g,\n \"$1\"\n );\n fragment.innerHTML = fragment.innerHTML.replace(\n /~~~(.*?)~~~/g,\n '$1'\n );\n }\n\n return node;\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":283,"value":"