29:null 2a:["$","title",null,{"children":"Iterative Deepening Depth First Search | Vaishnavi Gurav | Observable"}] 2f:T146b,// This function just draws the picture + dfs function draw_network_viz() { let svg = d3.create("svg").attr("width", w).attr("height", h); //edges let link = svg.append("g").attr("id", "links"); link .selectAll("line.link") .data(G.links) .join("line") .attr("class", "link") .attr("id", (d) => d.cy_data.id) .attr("stroke", "black") .attr("stroke-width", 1) .attr("stroke-opacity", 0.1) .attr("x1", (d) => d.source.x) .attr("y1", (d) => d.source.y) .attr("x2", (d) => d.target.x) .attr("y2", (d) => d.target.y); //nodes let node = svg.append("g").attr("stroke", "#fff").attr("stroke-width", 1.5); node .selectAll("circle") .data(G.nodes) .join("circle") .attr("class", (o) => (o.valence == G.max_valence ? "hub" : "port")) .attr("id", (d) => d.cy_data.id) .attr("cx", (d) => d.x) .attr("cy", (d) => d.y) .attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1) .attr("fill", "black"); node .selectAll("circle.hub") .nodes() .forEach(function (c, i) { console.log(c, i); //root node if (i == 0) { d3.select(c).attr("r", 8).attr("fill", "red").raise(); } else { d3.select(c).attr("class", "port"); } }); //on pointer move - clear the bfs paths + select other node svg .on("touchmove", (evt) => evt.preventDefault()) .on("pointerenter pointermove", function (evt) { //clear the paths node .selectAll("circle.port") .attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1) .attr("fill", "black"); node.selectAll("circle.hub").attr("fill", "red"); link.selectAll("line.link").attr("stroke", "black").attr("stroke-opacity", 0.1); //scroll for end node let [x, y] = [evt.layerX, evt.layerY]; let closest = qt.find(x, y); if ((closest.x - x) ** 2 + (closest.y - y) ** 2 < 1000) { let end = svg.select(`#n${closest.index}`) if (end.attr("fill") != "red" ) { end.attr("fill", "green"); } } }); //on click - select end node + dfs svg .on("touchmove", (evt) => evt.preventDefault()) .on("click", function (evt) { //remove previously selected end node node .selectAll("circle.end") .nodes() .forEach( function (c, i) { d3.select(c).attr("r", (o) => 6 * (o.valence / G.max_valence) ** 1).attr("fill", "black").attr("class", "port"); }); //select new end node let [x, y] = [evt.layerX, evt.layerY]; let closest = qt.find(x, y); if ((closest.x - x) ** 2 + (closest.y - y) ** 2 < 1000) { let end = svg.select(`#n${closest.index}`) if (end.attr("fill") != "red" ) { end .attr("class", "end") .attr("r", 8) .attr("fill", "green") .raise(); //iddfs let currentDepth = 0; let f = closest.index; let start = G.root_node; let time = 0; const nodeDepth = new Map(); nodeDepth.set(start.index, 0); let color = ["#4e79a7","#f28e2c","#e15759","#76b7b2","#59a14f", "#edc949","#af7aa1","#ff9da7","#9c755f","#bab0ab", "#4e79a7","#f28e2c","#e15759","#76b7b2","#59a14f",]; while( currentDepth < maxDepth ){ let V = {}; let stack = []; stack.unshift( start ); while( stack.length !== 0 ){ let s = stack.pop(); let n1 = svg.select(`#n${ s.index }`); n1.transition().delay(time).attr("fill", color[currentDepth]); if ( nodeDepth.get(s.index) <= currentDepth ){ V[ s.index ] = true; let vw = adjlist.get(s); for( let i = 0; i < vw.length; i++ ){ let e = vw[ i ]; if (! V[ e.index ]){ stack.push(e); V[ e.index ] = true; nodeDepth.set(e.index, nodeDepth.get(s.index) + 1); let n2 = svg.select(`#n${ e.index }`); n2.transition().delay(time + 50).attr("fill", color[currentDepth]); let e1 = svg.select(`#n${s.index}--n${e.index}`); e1.transition().delay(time + 50).attr("stroke", color[currentDepth]).attr("stroke-opacity", 1); let e2 = svg.select(`#n${e.index}--n${s.index}`); e2.transition().delay(time + 50).attr("stroke", color[currentDepth]).attr("stroke-opacity", 1); time = time + 50; }//end if }//end for }//end if if ( V[ f ] ){ break; }//end if }//end while currentDepth++; if ( V[ f ] ){ break; }//end if }//end while //end iddfs }//end if }//end if }); return svg.node(); } 30:T52d,// The network is represented by the following random geometric graph. G = { let N = Math.round(800 * s); let seed = 0.1234; seed = Math.random(); let random_source_x = d3.randomLcg(seed); let random_source_y = d3.randomLcg(seed / 2); let random_x = d3.randomUniform.source(random_source_x)(0, w); let random_y = d3.randomUniform.source(random_source_y)(0, h); let pts = d3.range(N).map(() => [random_x(), random_y()]); let nodes = pts.map((p, i) => ({ x: p[0], y: p[1], index: i, cy_data: { id: `n${i}` } })); let R = 4000; let links = nodes .map((node, i) => nodes.slice(i + 1).filter((n) => dist2(node, n) < R)) .map((a, i) => a.map((o) => ({ source: nodes[i], target: nodes[o.index], length2: Math.sqrt(dist2(nodes[i], nodes[o.index])), cy_data: { id: `n${i}--n${o.index}` } })) ) .flat(); nodes.forEach( (o) => (o.valence = links.filter( (l) => l.source.index == o.index || l.target.index == o.index ).length) ); let max_valence = d3.max(nodes.map((o) => o.valence)); let root_node = nodes.filter((o) => o.valence == max_valence)[0]; let G = { nodes, links, max_valence, root_node }; return G; function dist2(o1, o2) { return (o1.x - o2.x) ** 2 + (o1.y - o2.y) ** 2; } }31:[] 2d:{"id":"62896c59e8709fd2","slug":"iterative-deepening-depth-first-search","title":"Iterative Deepening Depth First Search","thumbnail":"722a4a9c1ebfef5db6dfabd061ab357ed2807161aa18fa426e81ccd9eb6c2a90","access_level":"public","create_time":"$D2022-08-15T10:00:43.281Z","update_time":"$D2022-09-02T09:49:36.138Z","view_time":null,"first_public_time":"$D2022-09-02T09:38:24.494Z","has_unpublished_edits":null,"fork":true,"stars":1,"starred":false,"owner":{"type":"team","id":"0f48945324c7c546","login":"vaishnavi5gurav","name":"Vaishnavi Gurav","avatar_url":"https://avatars-next.observableusercontent.com/9da31b9c962ea9d950b56fbe18df8e4229311ae42a1fdd9e36f0257089773ffa","tier":"starter_2024"},"version":605,"publish_version":605,"role":null,"authored":false,"authors":[{"type":"individual","id":"4798cde801b791f1","login":"vaishnavi5gurav","name":"Vaishnavi Gurav","avatar_url":"https://avatars-next.observableusercontent.com/9da31b9c962ea9d950b56fbe18df8e4229311ae42a1fdd9e36f0257089773ffa","tier":null}],"members":[{"type":"individual","id":"4798cde801b791f1","login":"vaishnavi5gurav","name":"Vaishnavi Gurav","avatar_url":"https://avatars-next.observableusercontent.com/9da31b9c962ea9d950b56fbe18df8e4229311ae42a1fdd9e36f0257089773ffa","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Iterative Deepening Depth First Search","cells":[{"id":108,"value":"# Iterative Deepening Depth First Search \n\nThe graph below is a random geometric graph (RGG) and the large, red node is root node of the graph. When you select another node with your pointer, the [Iterative Deepening Depth First Search Algorithm (IDDFS)](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) searches for it starting from the red node and iteratively increasing the depth till set max depth is reached. Iterations can be seen with the change in color.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":439,"value":"viewof maxDepth = Inputs.range([0, 15], {label: \"Max Depth\", step: 1})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"rgg = draw_network_viz()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"function DLS(src, target, maxDepth){\n let n2 = svg.select(`#n${ src.index }`);\n n2.attr(\"fill\", \"blue\");\n if ( src.index == target.index){\n let n2 = svg.select(`#n${ target.index }`);\n n2.attr(\"fill\", \"blue\");\n return true;\n }//end if\n if ( maxDepth <= 0 ){\n return true;\n }//end if\n let vw = adjlist.get(src)\n for( let i = 0; i < vw.length; i++ ){\n if ( DLS(i, target, maxDepth - 1) ) {\n return true;\n }//end if\n }//end for\n}//end func","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"//quadtree of graph - to find closest node to pointer\nqt = d3\n .quadtree()\n .x((d) => d.x)\n .y((d) => d.y)\n .addAll(G.nodes)\n .extent([\n [0, 0],\n [w, h]\n ])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"cy = {\n let nodes = G.nodes.map((n) => ({ data: { id: `n${n.index}` } }));\n let edges = G.links.map(function (e) {\n let source_node = `n${e.source.index}`;\n let target_node = `n${e.target.index}`;\n return {\n data: {\n source: source_node,\n target: target_node,\n id: `${source_node}--${target_node}`,\n length2: e.length2\n }\n };\n });\n return cytoscape({\n elements: {\n nodes: nodes,\n edges: edges\n }\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":" adjlist = adl()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":287,"value":"//adjacency list of graph for search algorithm\nfunction adl(){\n const adl = new Map();\n for (let j = 0 ; j < G.links.length; j++ ){\n if (!adl.has(G.links[j].source)){\n adl.set(G.links[j].source, []);\n }\n if (!adl.has(G.links[j].target)){\n adl.set(G.links[j].target, []);\n }\n adl.get( G.links[j].source).push( G.links[j].target); \n adl.get( G.links[j].target).push( G.links[j].source); \n }\n return adl;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"r = w / 1000;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"h = 0.625 * w;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"s = r ** 2;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"w = width < 1100 ? width : 1100;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"cytoscape = require(\"cytoscape\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":583,"value":"## Reference\n\n1. [Observable](https://observablehq.com/@observablehq/documentation)\n2. [D3.js](https://github.com/d3/d3/wiki)\n3. [Cytoscape](http://manual.cytoscape.org/en/stable/)\n4. [Graph Visualization Inspiration](https://observablehq.com/@mcmcclur/dijkstras-algorithm-on-an-rgg)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":601,"value":"## Checkout my visualizations\n\n1. [Breadth First Search](https://observablehq.com/@vaishnavi5gurav/breadth-first-search)\n2. [Depth First Search](https://observablehq.com/@vaishnavi5gurav/depth-first-search)\n3. [Depth Limited Search](https://observablehq.com/@vaishnavi5gurav/depth-limited-search)\n4. [Iterative Deepening Depth First Search](https://observablehq.com/@vaishnavi5gurav/iterative-deepening-depth-first-search)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2e:"$2d:body"