COMP2521 24T1 - Week 07 Lab Exercise

Objectives

To explore an application of graphs
To get some practice implementing graph search algorithms
To perform complexity analysis on graph algorithms
To understand the difference between BFS and DFS

Admin

Marks: 5 (see the Assessment section for more details)
Demo: in the Week 7, 8 or 9 lab session
Submit: see the Submission section
Deadline to submit to give: 5pm Monday of Week 8
Late penalty: 0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted

Background

In lectures, we learned about two basic graph search algorithms: breadth-first search (BFS) and depth-first search (DFS). BFS explores the vertices in order of distance from the starting vertex, and is guaranteed to find the shortest path to any vertex (in an unweighted graph). Meanwhile, DFS tries to explore as far as possible by following edges to unvisited vertices before backtracking. In this lab, we will explore the differences between these algorithms by implementing our own maze solvers!

Mazes and Graphs

Almost everyone has seen a maze before - a maze is a collection of walls and paths, typically with a start and finish. But how can we represent a maze using a graph?

Visually, it's quite easy - given a maze, we can treat each uninterrupted stretch (uninterrupted meaning no turns or intersections) as an edge, and create vertices at the ends of each edge. For example, here is a maze and its graph equivalent:


This maze was taken from this Computerphile video

In this graph representation, each vertex would consist of an identifier, a set of coordinates and a list of neighbours (up to four). However, producing this graph representation is quite complex. For mazes that have a grid layout, it is simpler to treat each every cell of the grid as a potential vertex. Then, identifying neighbours for each vertex is easy - all we need to do is to check the four adjacent cells. If an adjacent cell is a wall cell, then it is not a vertex (and hence not a neighbour), otherwise it must be a neighbour.

In this new representation, all we need is a 2D matrix (array) of booleans to indicate whether a cell is a wall or a path, and it is up to the user of the maze to determine where the vertices and edges are. This is the representation that we will be using in the lab.

Setting Up

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/24T1/labs/week07/downloads/files.zip

If you've done the above correctly, you should now have the following files:

Makefile: a set of dependencies used to control compilation
cell.h: the definition of the cell data type used by the rest of the code
Maze.h: the interface to the Maze ADT
Maze.c: a complete implementation of the Maze ADT
Queue.h: the interface to the Queue ADT
Queue.c: a complete implementation of the Queue ADT
Stack.h: the interface to the Stack ADT
Stack.c: a complete implementation of the Stack ADT
matrix.h: the interface to utility functions for creating matrices (2D arrays)
matrix.c: a complete implementation of the utility functions for matrices
solve.h: the interface to the maze solver, used by solver.c
solveBfs.c: an implementation of the maze solver using breadth-first search
solveDfs.c: an implementation of the maze solver using depth-first search
solveDfsBacktrack.c: an implementation of the maze solver using recursive depth-first search
solveKeepLeft.c: an implementation of the maze solver using the "keep left" strategy
solver.c: a driver program that creates a maze and runs a maze-solving algorithm on it
mazes/: a directory containing example mazes
analysis.txt: a template for you to fill in your answers for Task 3

Once you've got these files, the first thing to do is to run the command

make

This will compile the initial version of the files, and produce four executables: ./solveBfs, ./solveDfs, ./solveDfsBacktrack and ./solveKeepLeft.

File Walkthrough

solver.c: solver.c is the entry point of the program. Given the path to a maze file, it opens the file, creates a maze from it and then calls solve(), which should solve the maze.
cell.h: cell.h contains the definition of the cell data type used by the rest of the code. A cell is simply represented by two integers: a row number and a column number.
Maze.h: Maze.h defines the interface to the Maze ADT, which provides all the functionality required to access information about the maze. In addition to storing the structure of the maze, the Maze ADT also keeps track of the state of all of the cells during a traversal so it can display the maze and produce an animation. You should read Maze.h, as you will be using many of its interface functions.
Queue.h and Stack.h: Queue.h and Stack.h define the interfaces to the Queue and Stack ADTs respectively. You will need these ADTs to implement your solvers, so you should read the header files to find out how to use them.
matrix.h: matrix.h defines the interface to some useful functions involving matrices/2D arrays that you may want to use to implement your solvers.
solveBfs.c, solveDfs.c, solveDfsBacktrack.c and solveKeepLeft.c: These files (will) contain the implementation of your maze solvers, each using a different algorithm. Only two of these are compulsory tasks - the others are there if you are looking for a challenge.
Maze files: The mazes/ directory contains some example mazes that you can use to test your maze solvers. You can create your own mazes, but to ensure that the mazes are read in correctly, you must follow the format specified in Maze.h.

Note that the implementations of the Queue and Stack ADTs in Queue.c and Stack.c have been minified and are intentionally hard to read. This is because users of an ADT can only access an ADT via its interface, so there is no need for users to read the implementation. We have therefore intentionally made Queue.c and Stack.c hard to read to discourage you from reading the ADT implementations. Maze.c has not been minified, but you should still avoid reading it, as the only way for you to interact with the Maze ADT is via its interface functions in Maze.h.

Task 1 - BFS Maze Solver

Implement the solve() function in solveBfs.c which takes in a maze and tries to find a path from start to finish using the breadth-first search algorithm. If there is a path, the function should mark the path on the maze using the MazeMarkPath() function and return true. Otherwise, the function should return false.

While searching the maze, you should call MazeVisit() every time you visit a cell. This will cause the maze to be redisplayed with the most recently visited cell marked. Important: Additionally, MazeVisit will return true if the cell you passed it was the finishing cell.

When you want to test your function, use the make command to recompile the program and then run ./solveBfs maze-file, where maze-file is one of the maze files in the mazes/ directory.

For example, running ./solveBfs mazes/small-1.txt should produce an animation like the following:

Your code does not have to produce this exact animation - other animations are possible depending on the order in which you visit neighbours. Here is another possible animation produced from a different visit order:

If there is no path from start to finish, then eventually, every cell that is reachable from the starting cell will be visited. Here is a possible animation for small-2.txt, which is not solveable:

You can adjust the speed of the animation by providing an additional command-line argument to the program - a number between 1 and 11, where 1 is the slowest and 11 is the fastest. The default speed is 3.

Here is the pseudocode for the BFS algorithm for general graphs:

bfs(g, src):
	Inputs: graph g
	        starting vertex src
	
	create visited and predecessor arrays
	create queue and enqueue src

	mark src as visited
	while the queue is not empty:
		dequeue v
		
		for all edges (v, w) where w has not been visited:
			mark w as visited
			set predecessor of w to v
			enqueue w

You can follow this pattern in this task, however note that you will need to adapt it for mazes and you should stop the search as soon as you have found the exit. You also need to mark the path after you have found the exit.

You may find the createXYZ functions in matrix.h useful for creating visited and predecessor arrays. If you do use these functions, make sure to free the arrays once you no longer need them with the corresponding free functions. Avoid memory leaks!

Task 2 - DFS Maze Solver

Implement the solve() function in solveDfs.c which also tries to solve the given maze but instead uses the depth-first search algorithm. Use the iterative implementation of the algorithm (i.e., the version that uses a stack), do not use recursion. When you think you are done, use the make command to recompile the program and then run ./solveDfs maze-file.

Here are some possible animations produced from ./solveDfs mazes/small-1.txt:

Here is the pseudocode for the DFS algorithm for general graphs:

dfs(g, src):
	Inputs: graph g
	        starting vertex src
	
	create visited and predecessor arrays
	create stack and push src

	while the stack is not empty:
		pop v

		if v has been visited:
			continue (i.e., return to beginning of loop)

		mark v as visited

		for all edges (v, w) where w has not been visited:
			set predecessor of w to v
			push w

Task 3 - Analysis

Congratulations for completing your maze solver! Now it's time to analyse the complexity of your algorithms. Given a maze with \( n \) cells in total (i.e., \( n = \text{width} \times \text{height} \)), what would be the time complexity of your BFS and DFS algorithms? Enter your answers into analysis.txt, along with an explanation for each answer. Important: you should ignore the maze-displaying code when analysing the time complexity, as that code only exists to produce an animation.

Optional Challenge Task 1

One slight advantage of depth-first search over breadth-first search is that it can be easily implemented recursively, and therefore does not require any additional data structures such as a queue or stack. Recursive depth-first search also induces backtracking behaviour, which occurs when there are no more new vertices to visit from a particular vertex (say B), and you backtrack to the previous vertex (say A) on your current path to continue searching. In the code, backtracking behaviour occurs when the function call where B was visited returns to the call where A was visited.

The backtracking behaviour of recursive depth-first search allows us to produce more natural movement in our animations. Instead of immediately jumping to a new cell once we reach a dead end (like in iterative depth-first search), we show the backwards movement along the path until a new cell is found. Here are some examples of recursive depth-first search and backtracking in action:

If there is no path from start to finish, then eventually, every cell that is reachable from the starting cell will be visited, and the algorithm will backtrack all the way back to the starting cell, like so:

Implement this algorithm in solveDfsBacktrack.c. Once you are done, use the make command to recompile the program and then run ./solveDfsBacktrack maze-file.

Optional Challenge Task 2

A nice trick to remember for maze solving is that if both the start and finish are on the edges of the maze, then it is possible to solve the maze by following the left or right wall all around the maze. If your goal is simply to find the finish, then this algorithm requires only constant \( O(1) \) memory (!), as all you need to keep track of is which cell you are at and what direction you are moving. (If you want to show a path that doesn't involve moving backwards over where you've already been, however, then you will still need a predecessor array.) Note that this is not a graph-search algorithm - it's just a simple algorithm that works for certain mazes. Here is the keep-left algorithm in action:

If there is no path from start to finish, then eventually, you will loop back to the start and you can use this to deduce that there is no path.

Notice that if there are cycles in the maze (like the one above), this algorithm may not visit all the cells in the maze - this is why it is only guaranteed to work if the start and finish are on the edges of the maze.

Implement this algorithm in solveKeepLeft.c. Once you are done, use the make command to recompile the program and then run ./solveKeepLeft maze-file.

Submission

You need to submit three files: solveBfs.c, solveDfs.c and analysis.txt. You must submit all of these files, even if you did not complete all of the tasks. You can submit via the command line using the give command:

give cs2521 lab07 solveBfs.c solveDfs.c analysis.txt

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Assessment

There is no automarking for this lab. To receive a mark, you must show your work to your tutor during your Week 7, 8 or 9 lab session. You will be marked based on the following criteria:

Aspect	Marks	Criteria
Code correctness	3	Your tutor will assess the correctness of your code for Tasks 1 and 2 by running your submission on a few select mazes.
Complexity analysis	1	This mark is for how accurate you were with your time complexity analysis in Task 3 and the quality of your explanations in `analysis.txt`.
Code style	1	This mark is for your code style in Tasks 1 and 2. Code with good style should have these qualities: consistent indentation and spacing, no repetition of code, no overly complicated logic, no overly long functions, correct use of C constructs (such as `if` statements and `while` loops), and comments where appropriate. See the style guide.