{
const svgBackgroundColor = "#081c15",
mazeEnterColor = "#f8961e",
mazeExitColor = "#faedcd",
mazePathColor = "#333d29",
mazeWallColor = "#95d5b2",
mazeWallWidth = 4,
radius = 4,
svg = d3.create("svg")
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.style("background-color", svgBackgroundColor),
container = svg.append("g")
.attr("transform",`translate(${margin.left},${margin.top})`),
numRows = mazeWidth,
numCols = mazeHeight,
y = d3.scaleBand()
.range([0,width])
.domain(d3.range(numRows)),
x = d3.scaleBand()
.range([0, height])
.domain(d3.range(numCols)),
clusterColors = d3.scaleSequential()
.domain([0,numCols * numRows])
.interpolator(d3.interpolateRainbow),
update = (edges,nodes) => {
let lines = container.selectAll(".mazePathLines")
.data(edges, d => d.id)
lines
.join(
enter => enter.append("path")
.classed('mazePathLines', true)
.attr("d", d => {
let x1 = x(d.source.id % numCols) + x.bandwidth();
let y1 = y(Math.floor(d.source.id/numCols)) + y.bandwidth();
let x2 = x(d.target.id % numCols) + x.bandwidth();
let y2 = y(Math.floor(d.target.id/numCols)) + y.bandwidth();
return d3.line()([[x1,y1],[x2,y2]]);
})
.attr("stroke", d => clusterColors(d.cluster))
.attr("stroke-width", mazeWallWidth)
.attr("fill", mazePathColor)
.style('opacity', d => d.status == 'union' ? 1 : .05)
.attr("stroke-linecap", "round"),
update => update.call(e => e.transition()
.duration(0)
.attr("stroke", d => clusterColors(d.cluster))
.style("opacity", d => d.status == "union" ? 1 : .05)
)
)
let circles = container.selectAll("circle")
.data(nodes, d => d.id)
.join(
enter => enter.append("circle")
.attr('cx', d => x(d.id%numCols) + x.bandwidth())
.attr('cy', d => y(Math.floor(d.id/numCols)) + y.bandwidth())
.attr('r', radius)
.attr("stroke", d => clusterColors(d.cluster))
.attr("fill", d => clusterColors(d.cluster))
.style("opacity", d => d.status == "visible" ? .6 : .2),
update => update.call(e => e.transition()
.duration(0)
.attr("fill", d => clusterColors(d.cluster))
.attr("stroke", d => clusterColors(d.cluster))
.style("opacity", d => d.status == "visible" ? .6 : .2)
)
)
}//end update function
let mazeSolution = kruskalMaze();
let maze = mazeSolution[0];
let animated = mazeSolution[1];
update(graph.edges,graph.nodes);
let count = 0
let interval = d3.interval(function(elapsed) {
if (count >= animated.length) {
interval.stop(); // <== !!!
return;
}
let updatedClusters = animated[count];
let currentEdge = maze[count];
if(currentEdge){
//display this edge/nodes
graph.edges.forEach(gE => {
if(gE.id == currentEdge.id){
//un-hide the edge
gE.status = currentEdge.final;
}
gE.cluster = updatedClusters[gE.source.id];
});
graph.nodes.forEach(gn => {
if(gn.status != 'visible'){
if(gn.id == currentEdge.source.id || gn.id == currentEdge.target.id){
gn.status = "visible";
}
}
gn.cluster = updatedClusters[gn.id];
})
}//end if currentEdge
update(graph.edges,graph.nodes);
count++
}, 1);
yield svg.node();
}
getCellNumber = (x,y) => {
let rowCount = mazeHeight;
let colCount = mazeWidth;
let cell = (x*colCount) + y;
return cell;
}
createEdge = (newNode,currentNode) => {
if(newNode != currentNode){
let edge = {id: `${currentNode.id}${newNode.id}`, source: currentNode, target: newNode, status: "start", cluster: currentNode.id};
return edge;
}
return;
}
nodeToIds = new Map()
getOrCreateNode = (i,j) => {
let node,created;
let currentNodeId = getCellNumber(i,j);
if(nodeToIds.has(currentNodeId)){
node = nodeToIds.get(currentNodeId);
created = 0;
}else{
node = {id: currentNodeId, cluster: currentNodeId};
nodeToIds.set(currentNodeId,node);
created = 1;
}
return [node,created];
}
checkEdge = (i,j,currentNode) => {
//checks for duplicates
let node2 = getOrCreateNode(i,j),
n2 = node2[0],
edge = createEdge(n2,currentNode);
if(edge){
let currentEdgeId = edge.id;
let reverseEdgeId = `${n2.id}${currentNode.id}`;
if(!(edgeIds.has(currentEdgeId) || edgeIds.has(reverseEdgeId)))
{
edgeIds.set(currentEdgeId,edge);
edgeIds.set(reverseEdgeId,edge);
return edge;
}
}
return;
};
edgeIds = new Map()
createGraph = (width,height) => {
let graph = {};
let x = width,
y = height;
let nodes = [];
let edges = [];
d3.range(x).forEach(i => {
d3.range(y).forEach(j => {
let newNode = getOrCreateNode(i,j),
currentNode = newNode[0],
created = newNode[1];
nodes.push(currentNode);
let ed;
if(i > 0){
ed = checkEdge(i-1,j,currentNode);
if(ed){
edges.push(ed);
}
};
if(i < width-1){
ed = checkEdge(i+1,j,currentNode);
if(ed){
edges.push(ed);
}
};
if(j > 0){
ed = checkEdge(i,j-1,currentNode);
if(ed){
edges.push(ed);
}
};
if(j < height-1){
ed = checkEdge(i,j+1,currentNode);
if(ed){
edges.push(ed);
}
};
})
})
graph.nodes = nodes;
graph.edges = edges;
return graph;
}
assignRandomEdgeWeights = (graph) => {
let edges = graph.edges;
let weights = edges.map(e => {
e.weight = getRandomInt(1,5); //random weight
e.status = "start";
return e;
});
//viz looks better when shuffled first
d3.shuffle(weights);
//sort edges by weight
weights = weights.sort((a, b) => (a.weight > b.weight) ? 1 : -1);
return weights;
}
mazeWidth = 20
mazeHeight = 20
graph = createGraph(mazeWidth,mazeHeight)
kruskalMaze = () => {
//assign random edge weights to each edge of the graph
const weightedEdges = assignRandomEdgeWeights(graph);
let animation = [];
let count = 0;
const clusterRanks = getClustersAndRanks(graph);
const clusters = clusterRanks[0];
const ranks = clusterRanks[1];
//union find algorithm
const find = (u) => {
if(clusters[u] != u){
clusters[u] = find(clusters[u]);
}
return clusters[u];
}
const union = (x,y) => {
x = find(x);
y = find(y);
if(ranks[x] > ranks[y]){
clusters[y] = x;
}else{
clusters[x] = y;
}
if(ranks[x] == ranks[y]){
ranks[y]++;
}
}
let solution = [];
let allRoots = [];
for(let edge of weightedEdges){
let x = edge.source.id, y = edge.target.id;
if(x != y){
if(find(x,x) != find(y,y)){
union(x,y);
edge.final = "union";
}else{
//they are the same, discard
edge.final = "discard";
}
}else{
edge.final = "discard";
}
//update each node's root for visualization
for(let cl in clusters){
find(cl,clusters);
}
//steps for animation
let clusterCopy = JSON.parse(JSON.stringify(clusters));
animation.push(clusterCopy);
solution.push(edge);
}
return [solution,animation];
}
getClustersAndRanks = (graph) => {
const clusters = {};
const ranks = {};
Array.from(graph.nodes).forEach(n => {
clusters[n.id] = n.id;
ranks[n.id] = 0;
})
return [clusters,ranks];
}
width = 400
height = 400
margin = ({top: 10, bottom: 30, left: 10, right: 30})
d3 = require("d3@6")
getRandomInt = (min, max) => {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min) + min);
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
