Description

In this project, you will implement both DFS and BFS to solve several different mazes. You will be required to implement your solutions in their respective locations in the provided project2.py file.

1       Pair Programming

You are allowed to work in pairs for this project. If you elect to work with a partner:

• You should submit only one version of your final code and report. Have one partner upload the code and report on their Sakai site. Make sure that both partner’s names are clearly indicated at the top of both the code and the report.
• When work is being done on this project, both partners are required to be physically present at the machine in question, with one partner typing (‘driving’) and the other partner watching (‘navigating’).
• You should split your time equally between driving and navigating to ensure that both partners spend time coding.
• You are allowed to discuss this project with other students in the class, but the code you submit must be written by you and your partner alone.

2       Style Points

Part of your grade for this project will be ‘style points’. The idea here is that the code you turn in must be well commented and readable. A reasonable user aught to be able to read through your provided code and be able to understand what it is you have done, and how your functions work. For these sorting algorithms, this means that a grader should be able to read over your code and tell that your algorithms are implemented correctly.

The guidelines for these ‘style points’:

• Your program file should have a header stating the name of the program, the author(s), and the date.
• All functions need a comment stating: the name of the function, what the function does, what the inputs are, and what the outputs are.
• Every major block of code should have a comment explaining what the block of code is doing. This need not be every line, and it is left to your discretion to determine how frequently you place these comments. However, you should have enough comments to clearly explain the behavior of your code.
• Please limit yourself to 80 characters in a line of code. In python, you can use the symbol \ to indicate a line break/continuation.

3       Provided Code

Your goal in this project will be to implement both DFS and BFS to solve several given mazes. To aid you in this, you have been provided with several fully functioning classes, several partially implemented classes, and functions for creating and testing the mazes.

3.1       Vertex Class

The first of the fully functioning classes is the Vertex class. This class has 5 class attributes:

• rank: the rank (label) of the given vertex
• neigh: the list of the neighboring vertices
• dist: the distance from the start vertex
• visited: a flag for marking a vertex as visited
• prev: the previous vertex in the path

Along with these are three implemented member functions:

• init : this is the constructor function for the Vertex class. It requires an input rank for the vertex, and sets all of the attributes to have reasonable starting values. You will create a new Vertex with a call: v = Vertex(rank).
• repr : this function is called whenever a Vertex is printed, i.e. when the call print(v) is made. It simply prints the rank of the vertex.
• isEqual: this takes in a second Vertex as an input, and compares the rank of the two vertices, returning True if they are equal rank (i.e., if they had the same label). This function can be called using: isEqual(u).

3.2       Maze Class

You have also been provided with a fully functioning Maze class with 7 class attributes:

• maze: a 2D array representing the maze (for internal use only)
• adjList: the adjacency list of Vertex objects
• adjMat: the adjacency matrix (stored as a 2D list of 0 or 1)
• start: the starting Vertex object
• exit: the exit Vertex object
• path: what will ultimately contain the path from start to exit, stored as a list of ranks

(not a list of vertices)

• verb: a flag that controls the verbosity of the printing, set to False to suppress printing the maze when solving and testing

The Maze class has 5 member functions:

• init : this is the constructor for the Maze class. It has two optional inputs: the mazeNum which selects which maze to use (options: 0,1,2,3 – default: 0); and the verbosity (True/False – default: False). This initialization function correctly creates the adjacency list and matrix, and finds the start and exit vertices. The path attribute is initialized as an empty list. A new maze can be created with the call m = Maze(mazeNum, verbosity).
• repr : this function is called when a Maze object is printed. It will check to see if a path has been set, and if that path correctly solves the maze. If verbosity is True, this function will print out the maze with a highlighted path if one was present. If verbosity if False, only statements concerning the correctness of the path will be printed.

When the maze is printed, walls are marked with an ‘X’, the start with an ‘s’, the exit with an ‘e’, and the path with ‘o’. If you see a ‘G’, it means your path attempted to pass through a wall. If you see an ‘R’, your path had a repeated vertex.

• printList: this function can be used to aid with debugging. It prints the adjacency list in a more readable format.
• printMat: this function can be used to aid with debugging. It prints the adjacency matrix in a more readable format.
• solve: this function takes in an alg (either the string ‘DFS’ or the string ‘BFS’), and a flag for verbosity (default: False). It then calls the function bdfs on the maze to obtain the path through the maze. You will be responsible for implementing the bdfs function (described later).

3.3 getMaze and testMazes

You have also been provided with two functions that create the maze and test your code:

• getMaze: this function takes in 0, 1, 2, or 3 and outputs the 2D array of 0s and 1s representing the maze. This is used internally by the Maze class. The mazes are:
  1. A small open room for debugging.
  2. A small maze for debugging.
  3. A large maze.
  4. A large zig-zag map.
• testMazes: this function will allow you to test your code on the entire set of mazes. It takes in an optional arguement verbosity, which controls whether each maze gets printed as it is solved (default = False).

4       Problem Statement

You will have three primary tasks in this project:

1. Properly implement a Stack class for use in DFS.
2. Properly implement a Queue class for use in BFS.
3. Implement the function bdfs that can run either DFS or BFS to solve the maze.

4.1       Stack Class

You have been provided with a partially implemented Stack class. It has 3 class attributes: • stack: the array representing the stack

• top: the index of the top element of the stack (will point directly at the top element in the stack)
• numElems: the number of elements currently in the stack There are 5 fully implemented member functions:
• init: the constructor which initializes an empty stack
• repr: the printing function the displays the stack’s info in a readable format
• isFull: this function will return true when the stack is full (and so requires resizing)
• isEmpty: this function will return true when the stack is empty
• resize: this function can be called to double the size of the stack in memory when you want to push a new element into a full stack

You will be responsible for implementing two more member functions:

• push: this function should take in some value and push it onto the top of the stack
• pop: this function should pop the top value off the stack and return it

Note: you are not allowed to use built-in function like append or remove for these tasks. Instead, you are expected to implement these functions directly using the provided attributes of the Stack class.

It is highly suggested that you ensure your Stack code is working correctly before proceeding.

4.2       Queue Class

You have been provided with a partially implemented Queue class. It has 4 class attributes: • queue: the array representing the queue

• front: the index of the front element of the queue (will point directly at the front element), this is the next element to be popped
• rear: the index that is ONE PAST the rear element of the queue, this is the location where the next pushed value will be written
• numElems: the number of elements currently in the queue There are 5 fully implemented member functions:
• init: the constructor which initializes an empty queue
• repr: the printing function the displays the queue’s info in a readable format
• isFull: this function will return true when the queue is full (and so requires resizing)
• isEmpty: this function will return true when the queue is empty
• resize: this function can be called to double the size of the queue in memory when you want to push a new element into a full queue

You will be responsible for implementing two more member functions:

• push: this function should take in some value and push it into the rear of the queue
• pop: this function should pop the front value from the queue and return it

Note: you are not allowed to use built-in function like append or remove for these tasks. Instead, you are expected to implement these functions directly using the provided attributes of the Queue class.

It is highly suggested that you ensure your Queue code is working correctly before proceeding.

4.3         DFS/BFS Implementation

The bulk of your submission will concern the function bdfs. This function should take in an input Maze object and a string that is either ‘DFS’ or ‘BFS’. Your implementation of this function should be able to run either DFS or BFS depending on this input string. Recall that the only major difference between the two algorithms is that one uses a stack and the other uses a queue.

The Maze class provides you with both an adjacency list of Vertex objects, and an adjacency matrix. So, you may use whichever representation you prefer when creating this function.

The output of this bdfs should be a list of vertex ranks (NOT Vertex objects) representing the path starting at the start vertex (which should be the first rank in your returned path) and ending at the exit vertex (which should be the last rank in your returned path).

You should not call this function directly when creating your code, but should instead use the Maze class’s member function solve, i.e., to test the small open room maze with printing enabled:

m = Maze(0, True) m.solve(‘DFS’)

m.solve(‘BFS’)

Note that the path will be overwritten with each call to solve, so you can resolve a maze that has already been solved.

Note that the function call testMazes(True) will test all four mazes with both DFS and BFS, and print the resulting paths (you can set the verbosity input to False to suppress the printing).