DASL Wiki

User Tools

Site Tools

Trace: • testing_possible_fixes_to_problems
bfs_and_dfs_implementation_v2

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
bfs_and_dfs_implementation_v2 [2023/11/09 18:09] – [Robotino Functions] fpalustrebfs_and_dfs_implementation_v2 [2023/11/13 09:56] (current) – fpalustre
Line 1: Line 1:
-====== BFS & DFS Implementation V2 (IN-PROGRSS) ======+====== BFS & DFS Implementation (2023) (IN-PROGRSS) ======
 **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu> **Author:** Francis Palustre Email: <palusf1@unlv.nevada.edu>
 \\ \\
-**Date:** Last modified on <11/09/23>+**Date:** Last modified on <11/13/23>
 \\ \\
 **Keywords:** Navigation, BFS, DFS, Robotino, cpp, **Keywords:** Navigation, BFS, DFS, Robotino, cpp,
Line 9: Line 9:
 {{ :sampleimageforwritingtutorial.jpg?200 |}} {{ :sampleimageforwritingtutorial.jpg?200 |}}
 \\ \\
-The photo above depicts <fill in the blank> which allows you to <fill in the blank>. The big picture problem is <fill in the blank>. Solving this partially or completely is important because <fill in the blank>. This tutorial shows you how to <fill in the blank> and takes approximately <fill in the blank> hours to complete. +The photo above depicts the environment used for travel which allows you to visually see the intended path that should be taken for Robotino . The big picture problem is understanding the traversal process and how it came to be. Solving this partially or completely is important because this gives robots an autonomous navigation process, limiting human interference. This tutorial shows you how to apply BFS and DFS to Robotino and should take approximately 1-2 hour to complete. 
 \\ \\
 ===== Motivation and Audience ===== ===== Motivation and Audience =====
-This tutorial's motivation is to find ways for robots to autonomously navigate their environments. Readers of this tutorial assumes the reader has the following background and interests: +This tutorial's motivation is to find ways for robots to autonomously navigate within their environments. Readers of this tutorial assumes the reader has the following background and interests: 
  
 <fc blue>   <fc blue>  
Line 21: Line 21:
   * Know how to navigate within the terminal in Linux   * Know how to navigate within the terminal in Linux
 \\ \\
-  * This tutorial may also attract readers who are interesting in implementing algorithms in their own projects+  * This tutorial may also attract readers who are interested in implementing algorithms in their own projects
 </fc> </fc>
 \\ \\  \\ \\ 
Line 179: Line 179:
     }     }
 ==== Breadth First Search==== ==== Breadth First Search====
 + {{ youtube>GH0YCbQobio?large }}
 Algorithm for BFS Algorithm for BFS
 +
 +    vector<string> BFS(map<string, vector<string> > graph, string startingNode, string desiredNode) {
 +         //Creating containers of visited and queued nodes
 +         vector<string> visited;
 +         queue<vector<string> > queue;
 +         
 +         queue.push(vector<string>(1, startingNode)); //starting the queue with our starting node
 +         
 +         while (!queue.empty()) {
 +             vector<string> path = queue.front(); //store node item in path
 +             queue.pop(); //removes node from queue
 +             
 +             string currNode = path.back(); //tailed node becomes current node
 +             
 +             //iterates through a set to find the current value in the path
 +             vector<string>::iterator findCurr = find(visited.begin(), visited.end(), currNode);
 +             
 +             if (findCurr == visited.end()) {
 +                  visited.push_back(currNode); //marks as visited
 +                  
 +                  vector<string> adjNodes = graph[currNode]; //neighbor nodes of current
 +                  
 +                  for (vector<string>::iterator it = adjNodes.begin(); it != adjNodes.end(); it++) { //iterates through the adjNodes
 +                      vector<string> newPath = path;
 +                      newPath.push_back(*it); //add neighbor to newPath vector
 +                      queue.push(newPath); //adds resultant path to queue
 +                      
 +                      if (*it == desiredNode) { //if desired found, return current path
 +                         return newPath;
 +                      }
 +                  }
 +              }
 +          }
 +          //if no path, return empty vector
 +          return vector<string>();
 +    }
 +
 ==== Depth First Search ==== ==== Depth First Search ====
-Algorithm for DFS+Algorithm for DFS.  
 +\\ 
 +There are two ways to traverse in DFS, an iterative approach and recursive approach. The following is a recursive approach because it is the most common. In the source code, there will be iterative as well. 
 + 
 + 
 +    vector<string> DFS(map<string, vector<string> > &graph, const string &startingNode, const string &desiredNode, map<string, bool> &visited) { 
 +         //mark the current node as visited 
 +         visited[startingNode] = true; 
 +          
 +         //containers of current path 
 +         vector<string> path; 
 +          
 +         //get adjacent nodes of starting node 
 +         vector<string> adjNodes = graph[startingNode]; 
 +          
 +         //iterate through adjacent nodes 
 +         for ( vector<string>::iterator it = adjNodes.begin(); it != adjNodes.end(); it++) { 
 +             const string& nextNode = *adjNodes; 
 +              
 +              //check if next node has been visited 
 +              if (!visited[nextNode]) { 
 +                 //recursively call DFS on the next node 
 +                  vector<string> subPath = DFS(graph, nextNode, desiredNode, visited); 
 +                   
 +                  //if subPath not empty, path to desired node is found 
 +                  if (!subPath.empty()) { 
 +                     //insert current node at beginning of subPath and return final path 
 +                     subPath.insert(subPath.begin(), startingNode); 
 +                     return subPath; 
 +                  } 
 +              } 
 +          } 
 +          //if no path, return empty vector 
 +          return vector<string>(); 
 +    } 
 ==== Final Words ==== ==== Final Words ====
  
Line 187: Line 260:
 \\ \\
 \\ \\
-Speculating future work derived from this tutorial, includes <fill in the blank>. In the big picture, the problem of <fill in the blank> can be solved with this tutorial.+Speculating future work derived from this tutorial, includes applying these and other algorithms such as Dijkstra and A* to Robotino and other robots. In the big picture, the problem of autonomous navigation can be solved with this tutorial.
 \\ \\
 \\ \\
bfs_and_dfs_implementation_v2.1699582176.txt.gz · Last modified: by fpalustre