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.
1
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: v.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)
2
• 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).
3
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
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.
5
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).
5 Submission
You must submit your project2.py code online on Sakai. If you worked with a partner,
only submit one version of your completed project and indicate clearly the names and NetIDs
of both partners.
This project is worth 100 points. The points will be assigned as follows:
• 10 points for a correct Stack push function
• 10 points for a correct Stack pop function
• 10 points for a correct Queue push function
• 10 points for a correct Queue pop function
• 30 points for a correct DFS implementation
• 30 points for a correct BFS implementation
