-
Notifications
You must be signed in to change notification settings - Fork 1
Depth first graph traversal visualization.
This algorithm works by traversing a node as deep as possible and when a dead end is encountered it backtracks. That is all nodes on the current path will be visited until they run out then the next path will be selected. In our grid, the traversal starts downwards, all nodes heading downwards will be traversed after which they will run out and the algorithm will opt for the right side, after the right side is deeply explored it will move upwards then downwards until the destination is arrived at. We implement depth-first search using stack data structure. We pick a node, push all its adjacent nodes to the stack then pop a node from the stack and select the next node, push its adjacent nodes to the stack, and we repeat this until the stack is empty. We keep a visited array to store already visited nodes.
Path: /code/assets/js/visual/PathFindingAlgorithms/dfs.js.
We get the speed slider button its value which we use to time the visualization. We also initialize a boolean which we use to denote arrival at the destination, therefore, terminating the algorithm. We initialize count which we use to count the number of steps which we also use for timing, that is, after the value given by count we perform certain actions such as enabling the clear path and start buttons which we disable at the start of the algorithm.
let speedSlider = document.querySelector(".speedSlider");
let time = speedSlider.value;
let bool = false;
let count = 1;This function checks for edges cases to avoid going out of the grid during traversal. 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.
checker = (row, col) => {
if (row >= 0 && col >= 0 && row < rowSize && col < colSize) return true;
return false;
};We change the colors of nodes under exploration and nodes already explored. The function takes the current node under exploration 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. 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).
// visualize algorithm
const changeColor = (node, cost) => {
setTimeout(() => {
node.setAttribute("class", "chosenPath");
node.innerHTML = cost;
}, cost * time);
// draw path blue
setTimeout(() => {
node.setAttribute("class", "pathColor");
}, cost * time + 100);
//draw path green
setTimeout(() => {
node.setAttribute("class", "chosenPath");
}, cost * time + 1000);
};We traverse the grid in a depth-first traversal by, given a node we explore it fully before going to the next, that is, going as deep as possible. The traverse function takes in a node which is the node we are currently at, a visited stack that stores already visited nodes, a cost denoting the cost to that node from the source, and an end node which represents the destination.
//traverse grid
traverse = (node, visited, cost, endNode) => {
// 1.
let row = parseInt(node.getAttribute("row"));
let col = parseInt(node.getAttribute("col"));
// 2.
if (bool || node == endNode) {
bool = true;
return;
}
// 3.
let wall = parseInt(node.getAttribute("wall"));
if (wall == 1) return;
// 4.
visited.push(node);
dfsSteps.push([row, col, cost, row, col]);
//5.
changeColor(node, count);
// 6.
let cr = row,
cc = col;
if (checker(cr + 1, cc)) {
let child = document.querySelector(`div[row="${cr + 1}"][col="${cc}"]`);
if (!visited.includes(child)) {
traverse(child, visited, cost + 1, endNode);
count++;
} else {
dfsSteps.push([row, col, cost, cr + 1, cc]);
}
}
if (checker(cr, cc + 1)) {
let child = document.querySelector(`div[row="${cr}"][col="${cc + 1}"]`);
if (!visited.includes(child)) {
traverse(child, visited, cost + 1, endNode);
count++;
} else {
dfsSteps.push([row, col, cost, cr, cc + 1]);
}
}
if (checker(cr - 1, cc)) {
let child = document.querySelector(`div[row="${cr - 1}"][col="${cc}"]`);
if (!visited.includes(child)) {
traverse(child, visited, cost + 1, endNode);
count++;
}else {
dfsSteps.push([row, col, cost, cr - 1, cc]);
}
}
if (checker(cr, cc - 1)) {
let child = document.querySelector(`div[row="${cr}"][col="${cc - 1}"]`);
if (!visited.includes(child)) {
traverse(child, visited, cost + 1, endNode);
count++;
}else {
dfsSteps.push([row, col, cost, cr, cc - 1]);
}
}
};- We get the current coordinates(row, col) of the node in the grid, this is the position we are at any point during the exploration.
- When we arrive at the destination node, the algorithm terminates and a path is highlighted from source to destination.
- We check if the node is a wall, that is, the wall attribute will have a value of '1' denoting a wall. The function returns null and if nothing is done to the node, the algorithm will proceed.
- We push the current node to the stack containing already visited nodes. We also push the row, column, cost, parent row, and parent column to the dfsSteps array of arrays which we use for later step by step execution of the algorithm.
- We change the color of the node either currently under exploration, already explored or a path to be taken to the destination.
- These functions enable traversal to the bottom, right, top, and left of the grid, We first do an error checking to ensure that we don't go outside the grid then proceed with the exploration, we keep a count which we use to timing the traversal. At this step we also push the row, column, cost, parent row, and column which we use for the step by step execution of the algorithm, these nodes will act as the nodes we pop off the stack once we either reach a wall or the end node on the grid.
This function is responsible for starting and running the whole visualization. It is executed once the start button is clicked and stops either when a destination node is arrived at or no path can be found.
dfs = (x1 = 0, y1 = 0, x2 = rowSize - 1, y2 = colSize - 1) => {
// 1.
time = speedSlider.value;
time = 40 + (time - 1) * -2;
// 2.
gridContainer.removeEventListener("mousedown", setWall);
gridContainer.removeEventListener("mouseover", setWall);
// 3.
let startNode = document.querySelector(`div[row='${x1}'][col='${y1}']`);
let endNode = document.querySelector(`div[row='${x2}'][col='${y2}']`);
// 4.
//hide start and clear path buttons
let startBtn = document.querySelector(".start");
let clearPathBtn = document.querySelector(".clearPath");
startBtn.style.visibility = "hidden";
clearPathBtn.style.visibility = "hidden";
// 5.
let visited = [];
let cost = 1;
bool = false;
// 6.
traverse(startNode, visited, cost, endNode);
// 7.
setTimeout(() => {
clearPathBtn.style.visibility = "visible";
}, count * time + 100);
};- We get the speed button from DOM and run the algorithm according to its value. Practically the algorithm will very fast run depending on various factors such as cpu, and the size of the graph, in this case in milliseconds right after the click of the start button but in the visualization we can either increase or decrease the speed.
- We remove event listeners, we can neither add walls to the grid after the start of the visualization.
- We get the start and end node from the grid which we shall pass to the traverse function.
- We cannot start or clear the path after the initialization has started because the buttons for this are disabled.
- We initialize an empty visited stack, boolean to denote the termination of algorithm and count which we use for speed and timing of the algorithm.
- We run the algorithm passing start and end nodes, empty visited array, and count.
- After the algorithm has been executed and finished the clear path button is enabled and now can be clicked, one can either clear the path and add obstacles or start the algorithm again.