MCL summer workshop in graph theory

Project 1: Maze solver

Due: Thursday, July 14

In this project you will use breadth-first search (BFS) to solve mazes.

Part 1: shortest paths

I added the BFS function to graphs.py. Recall that it computes the legnth of the shortest path from a start vertex $s$ to each other vertex. But for our maze solver we will need to know the vertices in these paths, not just their lengths.

To accomplish this, in addition to keeping track of each vertex's distance from $s$, you can keep track of each vertex's predecessor—the vertex from which it was "discovered" (i.e., when it's distance was set). To do this, use another list pred to store the predecessors. pred[ $u$ ] should give the predecessor of vertex $u$, or None if it has not been set. The way you do get this to happen is simple: when you set a vertex's distance, also set its predecessor. Then, at the end, return pred instead of dists.

Complete the function modifiedBFS below. Test it on a complete graph, a path, a cycle, and a random graph.

In [ ]:
from graphs import *

def modifiedBFS(G, s):
    """BFS in G starting from s"""
    
    n = G.numVertices()
    
    dists = {v: "Infinity" for v in G.vertices}
    pred = {v: None for v in G.vertices}
    
    dists[s] = 0
    toVisit = [s]

    i = 0
    while(i < len(toVisit)):
        v = toVisit[i] # We already know v's distance from s

        # Set distances of all v's neighbors
        for u in G.neighbors(v):
            if dists[u] == "Infinity":
                dists[u] = dists[v] + 1
                
                #### TO DO: SET PREDECESSOR HERE ####
                
                toVisit.append(u)

        i += 1

    return pred

#### Testing ####
n = 10
G = CompleteGraph(n)
s = 0
print(G)
print("Start vertex: " + str(s))
print("Distances: " + str(BFS(G, s)))
print("Predecessors: " + str(modifiedBFS(G, s)))

Great. You've got a list of every vertex's predecessor. Now you need to use it to construct the shortest path from $s$ to a vertex $t$. You can do this by starting with $t$ and "backtracking" through the list of predecessors until you get to $s$.

Complete the function shortestPath( $G$, $s$, $t$ ) below. It should return a list [ $s, \ldots, t$ ] representing the shortest path from $s$ to $t$ in $G$. Assume $t$ is connected to $s$. Hint: use a while loop.

In [ ]:
from graphs import *

def shortestPath(G, s, t):
    
    # Get list of predecessors
    pred = modifiedBFS(G, s)
    # print(pred) # For testing
    
    path = []
    
    # YOUR CODE HERE
    
    return path
    
#### Testing ####
n = 10
G = RandomGraph(n)
print(G)
s = 0
t = 9
print("Start: " + str(s))
print("End: " + str(t))
print("Shortest path: " + str(shortestPath(G, s, t)))

Part 2: from maze to graph

Now you must now write a function to construct a graph from a text representation of a maze that looks like this:

11 13
+++++++++++++
+          s+
+  ++++++++++
+           +
+  +++++++  +
+  +     +  +
+  +  t  +  +
+  +     +  +
+  +++   +  +
+           +
+++++++++++++
  • The first line gives you the dimensions of the maze.
  • Spaces represent open squares.
  • + signs represent walls.
  • s represents the start square.
  • t represents the end square (both s and t count as open).

Your project folder contains sample mazes maze-1, maze-2, maze-3, maze-4, maze-5, maze-6.

Complete the function mazeToGraph below.

  • Instead of having vertices 0, 1, ..., $n - 1$ as usual, we will have vertices $(i, j)$ representing the coordinates of each space, with $(0, 0)$ representing the top left.
  • Add a vertex for each space, s, and t.
  • For each space, add an edge to each of its adjacent open spaces.
  • Return the graph constructed AND the coordinates of the start and finish spaces.
In [ ]:
from graphs import *

def mazeToGraph(fileName):
    
    # Start with an empty graph
    G = Graph()
    s = t = None

    # This is how you read a file in Python...
    f = open(fileName, "r")
    
    # Get the dimensions
    dim = f.readline().split()
    m, n = int(dim[0]), int(dim[1])
    
    maze = f.readlines()
        
    for i in range(m):
        for j in range(n):
                        
            # maze[i][j] is the (i, j)th position in the maze

            # If it is ' ', 's', or 't', add a vertex to the graph
            # and add edges to all adjacent open spaces
            
            # maze[i][j] has 4 adjacent spaces: 
            # maze[i - 1][j], maze[i + 1][j], maze[i][j - 1], and maze[i][j + 1]
            
            # If maze[i][j] is 's' or 't', assign it to s or t
    
    
    f.close()
    
    return G, s, t
    
#### Testing ####

G, s, t = mazeToGraph("maze-6")
print(G)
print("Start: " + str(s))
print("Finish: " + str(t))

Now write a function to solve the maze and return the path from start to finish. This should be easy using mazeToGraph and shortestPath...

In [ ]:
def solveMaze(fileName):
    # YOUR CODE HERE
    
#### Testing ####

print(solveMaze("maze-6"))

"Extra credit": pretty pictures

Write a function graphToMaze( $G$, $P$ ) which takes a graph $G$ and reconstructs the maze corresponding to $G$, using 'O's to mark the path $P$ from s to t. In the example above, this would look like:

+++++++++++++
+ OOOOOOOOOs+
+ O++++++++++
+ O         +
+ O+++++++  +
+ O+     +  +
+ O+  t  +  +
+ O+  O  +  +
+ O+++O  +  +
+ OOOOO     +
+++++++++++++
In [ ]:
def graphToMaze(G, path):
    # YOUR CODE HERE

Write-up

Write a few paragraphs here describing how you solved these problems, any difficulties you encountered along the way, etc. Explain what your code does and why you think it works.

Double click on this box to edit it, and press Shift-Enter to display it.

When you're done, save this file and email it to scole3@uic.edu.

Enjoy the rest of your summer!

In [ ]: