(function () { const container = d3.select("#viz-CONTAINER"); container.selectAll("*").remove(); //----------------------------------------------------- // RESPONSIVE SIZING — KEY CHANGE! //----------------------------------------------------- function getDims() { const rect = container.node().getBoundingClientRect(); const width = rect.width; return { width, height: Math.max(250, width * 0.55), // proportional height nodeRadius: width < 500 ? 11 : 6, // bigger nodes on mobile edgeWidth: width < 500 ? 2.8 : 1.5, // thicker edges on mobile bfsSpeed: width < 500 ? 50 : 100 // faster BFS on mobile }; } let {width, height, nodeRadius, edgeWidth, bfsSpeed} = getDims(); //----------------------------------------------------- // THEME COLORS //----------------------------------------------------- const styles = getComputedStyle(document.documentElement); const COLOR_EDGE = "var(--gray-lines)"; const COLOR_NODE_FILL = "white"; const COLOR_NODE_BORDER = "var(--bs-secondary-dark)"; const COLOR_TARGET = styles.getPropertyValue("--bs-danger").trim(); const COLOR_PATH_NODE = styles.getPropertyValue("--bs-primary").trim(); const COLOR_PATH_EDGE = styles.getPropertyValue("--bs-danger").trim(); const COLOR_VISITING = styles.getPropertyValue("--bs-warning").trim(); //----------------------------------------------------- // UI //----------------------------------------------------- const resultBox = container.append("div") .style("font-family", "monospace") .style("font-size", width < 500 ? "12px" : "13px") .style("background", "var(--bs-secondary-dark)") .style("color", "#fff") .style("padding", "8px 12px") .style("border-radius", "6px") .style("width", "100%") .style("box-sizing", "border-box") .html("Click any node to begin."); const svg = container.append("svg") .attr("width", width) .attr("height", height) .style("touch-action", "none"); // allow pinch-zoom //----------------------------------------------------- // Pinch Zoom / Drag Support //----------------------------------------------------- const graphGroup = svg.append("g"); svg.call( d3.zoom() .scaleExtent([0.6, 4]) .on("zoom", ({transform}) => { graphGroup.attr("transform", transform); }) ); //----------------------------------------------------- // GRAPH GEN //----------------------------------------------------- const N = 100; const margin = 30; const nodes = d3.range(N).map(i => ({ id: i, x: margin + Math.random() * (width - 2 * margin), y: margin + Math.random() * (height - 2 * margin) })); const K = 7; let edges = []; for (let i = 0; i < N; i++) { const dists = []; for (let j = 0; j < N; j++) { if (i === j) continue; const dx = nodes[i].x - nodes[j].x; const dy = nodes[i].y - nodes[j].y; dists.push({ j, dist: dx * dx + dy * dy }); } dists.sort((a, b) => a.dist - b.dist); const neighbors = dists.slice(0, K); neighbors.forEach(n => { const a = i; const b = n.j; if (a < b) edges.push({ u: a, v: b }); else edges.push({ u: b, v: a }); }); } const seen = new Set(); edges = edges.filter(e => { const key = `${e.u}-${e.v}`; if (seen.has(key)) return false; seen.add(key); return true; }); const adj = {}; nodes.forEach(n => { adj[n.id] = []; }); edges.forEach(e => { adj[e.u].push(e.v); adj[e.v].push(e.u); }); const targetId = Math.floor(Math.random() * N); //----------------------------------------------------- // DRAW //----------------------------------------------------- const edgeSelection = graphGroup.append("g") .selectAll("line") .data(edges).enter().append("line") .attr("x1", d => nodes[d.u].x) .attr("y1", d => nodes[d.u].y) .attr("x2", d => nodes[d.v].x) .attr("y2", d => nodes[d.v].y) .attr("stroke", COLOR_EDGE) .attr("stroke-width", edgeWidth) .attr("opacity", 0.85); const nodeSelection = graphGroup.append("g") .selectAll("circle") .data(nodes).enter().append("circle") .attr("id", d => `node-${d.id}`) .attr("cx", d => d.x) .attr("cy", d => d.y) .attr("r", nodeRadius) .attr("fill", d => d.id === targetId ? COLOR_TARGET : COLOR_NODE_FILL) .attr("stroke", d => d.id === targetId ? COLOR_TARGET : COLOR_NODE_BORDER) .attr("stroke-width", nodeRadius / 3) .style("cursor", "pointer") .on("click", (event, d) => { if (d.id === targetId) { resultBox.text("Target selected (distance = 0)."); highlightNone(); } else { runBFS(d.id, targetId); } }) .on("touchstart", (event, d) => { event.preventDefault(); if (d.id === targetId) { resultBox.text("Target selected (distance = 0)."); highlightNone(); } else { runBFS(d.id, targetId); } }); //----------------------------------------------------- // RESET //----------------------------------------------------- function highlightNone() { edgeSelection.attr("stroke", COLOR_EDGE).attr("stroke-width", edgeWidth); nodeSelection .attr("fill", n => n.id === targetId ? COLOR_TARGET : COLOR_NODE_FILL) .attr("stroke", n => n.id === targetId ? COLOR_TARGET : COLOR_NODE_BORDER) .attr("stroke-width", nodeRadius / 3) .attr("opacity", 1.0); } //----------------------------------------------------- // BFS ANIMATION (responsive) //----------------------------------------------------- const stepBox = container.append("div") .style("font-family","monospace") .style("font-size", width < 500 ? "11px" : "12px") .style("background","#f8f9fa") .style("color","#000") .style("padding","6px 10px") .style("border-radius","6px") .style("margin-bottom","10px") .text("BFS Steps: (not running)"); let bfsInterval = null; function runBFS(startId, goalId) { highlightNone(); stepBox.text("Starting BFS..."); const queue = [startId]; const visited = new Set([startId]); const parent = {}; parent[startId] = null; if (bfsInterval) clearInterval(bfsInterval); bfsInterval = setInterval(() => { if (queue.length === 0) { clearInterval(bfsInterval); stepBox.text("Finished — No path found."); return; } const current = queue.shift(); d3.select(`#node-${current}`) .attr("fill", COLOR_VISITING) .attr("stroke", COLOR_VISITING) .attr("opacity", 1.0); stepBox.text(`Dequeued ${current} → neighbors: ${adj[current].join(", ")}`); if (current === goalId) { clearInterval(bfsInterval); reconstructPath(parent, startId, goalId); return; } for (const nei of adj[current]) { if (!visited.has(nei)) { visited.add(nei); parent[nei] = current; queue.push(nei); d3.select(`#node-${nei}`) .transition().duration(200) .attr("fill", COLOR_PATH_NODE) .attr("opacity", 1.0); const key = current < nei ? `${current}-${nei}` : `${nei}-${current}`; graphGroup.selectAll("line") .filter(d => (d.u + "-" + d.v === key)) .transition().duration(220) .attr("stroke", COLOR_VISITING) .attr("stroke-width", edgeWidth * 1.8); } } }, bfsSpeed); } //----------------------------------------------------- // PATH //----------------------------------------------------- function reconstructPath(parent, startId, goalId) { stepBox.text("Goal found — reconstructing path..."); const path = []; let cur = goalId; while (cur !== null) { path.push(cur); cur = parent[cur]; } path.reverse(); const distance = path.length - 1; resultBox.html( `Start: ${startId}
`+ `Target: ${goalId}
`+ `Shortest distance: ${distance}
`+ `Path: ${path.join(" → ")}` ); highlightPath(path); } function highlightPath(path) { for (let i = 0; i < path.length - 1; i++) { const a = path[i]; const b = path[i+1]; const key = a < b ? `${a}-${b}` : `${b}-${a}`; graphGroup.selectAll("line") .filter(d => (d.u + "-" + d.v === key)) .transition().duration(350) .attr("stroke", COLOR_PATH_EDGE) .attr("stroke-width", edgeWidth * 2) .attr("opacity", 1.0); } } //----------------------------------------------------- // REDRAW ON SCREEN RESIZE 🚀 //----------------------------------------------------- window.addEventListener("resize", () => { container.selectAll("*").remove(); (arguments.callee)(); // re-run IIFE }); })();

Connected Topic(s):

Search Algorithm

Figure:

Related Topic(s):