Mazes Assignment Phase 2

Depth First Search Assignment

Overview

Imagine it's the first day of classes and you're trying to find your way around the science building to SB 100. You're trying to make it to lecture on time so that your absolutely terrifying professor doesn't humiliate you in front of the entire class for being late. But you're lost! Corridors double back on themselves. The third floor of Remsen connects to the second floor of the science building. You decide to follow the corridor and it somehow leads you to the floor above, though you have no memory of climbing stairs. You're running out of food and water. If only you knew how to get to the science building cafe!

In this totally plausible scenario, what do you do? You could strike out in random directions, bouncing off walls until you're lucky enough to get out and see your family again. Or you could be strategic. Pick a path, follow it until it either doubles back or reaches your destination. Do this with every possible path and, maybe by the end of the semester, you'll know a path to your lecture! Alternatively, you could use a computer to solve the maze for you, and have it show you the path to take.

Design

1. The goal of assignment 2 is to solve the maze, using depth-first search. Since this is a continuation of assignment 1, your solution must build on your own code from assignment 1. You are welcome to fix bugs in assignment 1 for this assignment, but only the code that is specific to assignment 2 is graded.

Your goal is to find the first possible path from the first room in the maze (rooms[0]) to the last one (if n is the number of rooms then rooms[n-1]) by applying the depth-first search algorithm. The depth-first search algorithm uses recursion (recursive calls) to find the solution. For a graph, since it can have cycles, the depth- first search algorithm employs a Boolean array visited to keep track of the visited status (visited or unvisited) of each vertex in the graph. Initially, all vertices are unvisited

Depth-First Search Algorithm (DFS):

• Find a path from a source vertex to the destination vertex in a graph.
• Start the search by making the current vertex the source vertex.
• Determine if the current vertex leads to the destination vertex:
  • Mark the current vertex as visited.
  • For each of the current vertexs outgoing edges, check the visited status of the edges adjacent vertex.
  • If the adjacent vertex is visited then move on to the next adjacent vertex.
  • If the adjacent vertex is unvisited then determine if there is a path from the adjacent vertex to destination vertex by recursively carrying out step 3 with the adjacent vertex being the current vertex in the recursive call to depth-first search.
• Once the depth-first search algorithm reaches the destination vertex it adds it to the solution path, and then recursively adds all the vertices on the direct path back to the source vertex.

This is the basic template for the depth-first search algorithm. You can use it as the basic starting point to write your version of the dfs method to find the first possible path from the first room to the last room in the maze.

dfs(Vertex s, Boolean visited)
{
visited[s] = true;
for each Vertex v adjacent to s
if (!visited[w]) dfs(w);
}

2. Add the following line of code to add the data member pathSolution to the Maze class:

private DoublyLinkedList< Vertex> pathSolution;

Place the above declaration of pathSolution in the Maze class right below the line of code:

private Vertex[] rooms;

3. You will write the public method findPath in the Maze class. This method should find the maze's solution the first time it is called, using the depth-first search algorithm described above, and stores the resulting linked list in the data member pathSolution. If there is no solution then pathSolution should store null. The idea is to compute the solution only once, and remember it. If findPath is called twice, the second time it is called it just returns the solution remembered. In addition to finding or remembering the path solution, the findPath method should print the path.

4. You will write the private method dfs in the Maze which has the three parameters: 1) the index of a starting vertex, 2) the index of an end vertex, and 3) the boolean array visited, and returns a path from the starting vertex to the ending vertex and null if it can't find a path to the end vertex.

5. The method findPath creates and initializes the Boolean array visited and starts the actual search by calling the method dfs with the Maze's first vertex (rooms[0]) as the start vertex, and the last vertex (rooms[n-1]) as the end vertex.

6. If needed, you can write additional methods to help in your implementation of findPath and dfs but they must be defined as private. Methods should be reasonably small following the guidance that "A function should do one thing, and do it well."

7. Create a driver class and make the name of the driver class Assignment2 and it should only contain only one method:

public static void main(String args[]).

The main method will receive the name of the maze file via a command line argument. For example, the command to run the program to process the maze file sample.maze is:

java Assignment2 sample.maze

The main method will create an instance of a Maze object passing the filename into the Maze objects constructor. Then, the main method will call the findPath method twice.

8. Do NOT use your own packages in your program. If you see the keyword package on the top line of any of your .java files then you created a package. Create every .java file in the src folder of your Eclipse project

9. Do NOT use any graphical user interface code in your program!

10. Document and comment your code thoroughly.