-
Notifications
You must be signed in to change notification settings - Fork 1
Breadth first graph traversal visualization.
Breadth-first traversal traverses the graph layer by layer, breadthwise , exploring neighboring nodes directly connected to the node currently being explored. We use a queue here to store nodes of the graph. We first visit all nodes at a layer before moving on to the next layer. The algorithm can be understood as a fire spreading on the graph, at the 0th step only the source is on fire. At each step, the burning fire at each vertex spreads to all its neighbors. The ring of fire is expanded at each iteration.
Path: /code/assets/js/visual/PathFindingAlgorithms/bfs.js.
We first get the speed slider button value which we use for timing the speed with which the algorithm will run.
const speedSlider = document.querySelector(".speedSlider");
let time = speedSlider.value;We change the colors of nodes under exploration and nodes already explored layer by layer. The function takes the current node under exploration, count which we use for timing, and cost which we use to label the cost from source to that node, after exploration, a path from the source node to the destination node is highlighted with green color after the fire reaches the destination node. It will change the color of nodes with timing first denoting exploration(green-blue) then followed by the node being selected as a path(green).
changeColor = (node, count, cost) => {
setTimeout(() => {
node.setAttribute("class", "chosenPath");
if (cost) {
node.innerHTML = cost;
}
}, count * time);
setTimeout(() => {
node.setAttribute("class", "pathColor");
}, count * time + 100);
};It takes the coordinates(row, col) to keep track of the position we are at in the grid, the current node under exploration, a visited array to store visited nodes, and the count which we use for timing. It is responsible for updating the nodes, that is, it will change the colors and update the cost which is the distance from the source to that node.
//1.
checkUpdateNode = (row, col, curr, checker, visited, count) => {
// 2.
if (row >= 0 && col >= 0 && row < rowSize && col < colSize) {
//3.
let node = document.querySelector(`div[row="${row}"][col="${col}"]`);
//4.
let wall = parseInt(node.getAttribute("wall"));
if (wall == 1) return;
//5.
let prow = parseInt(curr.getAttribute("row"));
let pcol = parseInt(curr.getAttribute("col"));
//6.
let cost = Math.min(
parseInt(curr.getAttribute("cost")) +
Math.abs(Math.abs(prow - row) + Math.abs(pcol - col)),
node.getAttribute("cost")
);
//7.
if (cost < node.getAttribute("cost")) {
node.setAttribute(
"parent",
curr.getAttribute("row") + "|" + curr.getAttribute("col")
);
node.setAttribute("cost", cost);
}
//8.
changeColor(curr, count, curr.getAttribute("cost"));
//9.
if (!visited.includes(node)) {
checker.push(node);
bfsSteps.push([row, col, cost, prow, pcol]);
}
//10.
visited.push(node);
//11.
return node;
} else {
//12.
return false;
}
};- The algorithm takes the current row and column, the current node being explored, checker queue and visited array, and count.
- Checking edge cases to ensure traversal does not extend outside the grid. That is, the algorithm will run as long as the following conditions stand; Row and column coordinates are greater than 0, meaning at least 0. keep in mind that (0,0) is the least coordinate in the grid. Row and column coordinates are not greater than the number of grid rows and columns.
- We get the node that we are currently at during the traversal of the grid.
- We avoid walls, if there is a wall nothing is done, and the function returns.
- Get the coordinates of the current node under exploration.
- Minimize the cost from the current node to the next by comparing the current node cost + next node cost and the cost of the next node which at this point is initialized to Positive Infinity.
- We go incrementing the cost from the source node layer to the current layer, as we do so we keep track of the path by setting parent attribute with coordinates at that point which we shall use to trace the shortest path from the source to destination.
- We change the colors and the cost from the source to that node.
- Check if the node is already explored, if not we explore it and later we push it to the visited array. We also push the row, column, cost at a node, the parent row, and parent column to the bfs steps array which we shall use to explore the algorithm in steps(manually).
- Push the already visited node to the visited array.
- Return visited node.
- Otherwise we return false.
We implement the breadth-first traversal visualization here, updates and color changes are made and finally, the shortest path from source to destination is highlighted in green. The function takes the start row and column as 0,0 and the last node in the last row and column.
//1.
bfs(x1 = 0, y1 = 0, x2 = rowSize - 1, y2 = colSize - 1){
//2.
time = speedSlider.value;
time = 40 + (time - 1) * -2;
gridContainer.removeEventListener("mousedown", setWall);
gridContainer.removeEventListener("mouseover", setWall);
let startNode = document.querySelector(`div[row='${x1}'][col='${y1}']`);
let endNode = document.querySelector(`div[row='${x2}'][col='${y2}']`);
//3.
startBtn.setAttribute("disabled", "true");
clearPathBtn.setAttribute("disabled", "true");
//4.
let visited = [startNode];
let checker = [startNode];
let count = 1;
//5.
while (checker.length != 0) {
//6.
checker.sort((a, b) => {
if (
parseInt(a.getAttribute("cost")) <
parseInt(b.getAttribute("cost"))
)
return 1;
if (
parseInt(a.getAttribute("cost")) >
parseInt(b.getAttribute("cost"))
)
return -1;
return 0;
});
//7.
let curr = checker.pop();
//8.
let row = parseInt(curr.getAttribute("row"));
let col = parseInt(curr.getAttribute("col"));
//9.
if (row == x2 && col == y2)
break;
//10.
let wall = parseInt(curr.getAttribute("wall"));
if (wall == 1) continue;
//11.
checkUpdateNode(row + 1, col, curr, checker, visited, count);
checkUpdateNode(row - 1, col, curr, checker, visited, count);
checkUpdateNode(row, col - 1, curr, checker, visited, count);
checkUpdateNode(row, col + 1, curr, checker, visited, count);
//12.
count++;
}
}- The algorithm takes the first node and last node in the graph.
- Here we initialize time which we use to time the visualization, the source, and destination nodes, we remove event listeners to prevent adding walls after the visualization has already started.
- Disabling the start and clear path buttons to prevent clicking during the execution of the algorithm.
- We initialize the checker queue, visited array for storing already visited nodes, and count which increments after each iteration and later we use it for timing the algorithm.
- Checker acts as the queue where we store nodes and once we explore a node we pop it from the queue, so while the queue is not empty we perform actions.
- Return 1 if the cost of the element at the front of the queue is less than the incoming element, -1 if the cost is greater otherwise return 0.
- We pop the front node from the checker queue which we use to start the exploration of adjacent nodes.
- We get the current position we are at during traversal.
- Breadth-first traversal terminates when we arrive at the destination, we check if the current position is at the destination if so we terminate.
- We ignore walls/obstacles, in such cases, we return nothing.
- These functions check the right, left, bottom, and left sides of a node during the traversal.
- We increment count throughout the whole procedure, that is until nodes added to the checker(queue) are all popped(explored). We use this for the timing of the algorithm.
After the algorithm explores all nodes from source to destination, this function will estimate the shortest path from source to destination, and the path is highlighted with green color.
//draw route
setTimeout(() => {
//1.
startNode.setAttribute("class", "pathNode");
//2.
while (endNode.getAttribute("parent") != "null") {
endNode.setAttribute("class", "chosenPath");
let coor = endNode.getAttribute("parent").split("|");
let prow = parseInt(coor[0]);
let pcol = parseInt(coor[1]);
endNode = document.querySelector(
`div[row="${prow}"][col="${pcol}"]`
);
//3.
dijkstrasPath.push([parseInt(prow), parseInt(pcol)]);
}
//4.
endNode = document.querySelector(`div[row="${x2}"][col="${y2}`);
endNode.setAttribute("class", "pathNode");
}, count * time + 100);
//5.
setTimeout(() => {
startBtn.removeAttribute("disabled");
clearPathBtn.removeAttribute("disabled");
manualStart.removeAttribute("disabled");
wallBtn.removeAttribute("disabled");
}, count * time + 100);- We maintain the styling of the start node to denote the source of the path.
- Remember the updating of nodes where we set the values of the parent attribute to the node coordinates, we use this node attribute to trace the shortest path from source to destination highlighted by the color green.
- Store nodes on the path from source to destination in an array which we shall use for highlighting the path after traversal.
- We maintain the styling of the end node to denote the destination.
- We enable the buttons that were disabled during the visualization, one can restart the algorithm or add more obstacles and restart the algorithm.