Introduction¶
Background
Understand the program being developed in this assignment.
Since this assignment includes code for a UI application, lets first take a moment to go over the distinct components of the code to frame the parts you will be implementing.
Application GUI¶
Background
Run the main application.
The mazes
package contains the main application code for this assignment; find and run Main.java
inside the package. This will launch a program that will (eventually) generate and solve mazes.
Note
If IntelliJ fails to run (e.g. cannot find symbol ExtrinsicMinPQ
), remember to refresh Gradle manually through the Gradle tool window (in the upper right by default).
The GUI consists of two main regions: the large region at the top that displays the current maze, and a few options and buttons at the bottom.
-
The “Maze base shape” drop-down controls what underlying “shape” your maze will have. The default is “Grid”, which creates a maze where each room is a rectangle.
Try switching the option to “Voronoi” and click the “Generate new maze” button to the left. This will generate a maze where the rooms are more irregular.
-
The “Maze generator” drop-down controls the actual maze generation process—it takes the initial set of room and removes walls to generate a plausible maze.
The default option is “Do not delete any walls”, which, as you may have guessed, does not delete any walls.
Now, try picking one of the “Delete random walls” options and generate a new maze. You should now see some of the walls removed and see something that more closely resembles a maze.
Unfortunately, the “randomly remove walls” strategy is not that great. If we remove 30% of the walls, the maze is too easy. If we remove 50% of the walls, we often end up with an unsolvable maze. (The red dots in the upper-left and lower-right corners are our starting and ending points.)
The final option labeled “Run (randomized) Kruskal” is what you will be implementing later. It turns out we can use the properties of minimum spanning trees to generate a much more interesting (and yet always solvable) maze!
-
The “Find shortest path” button, once implemented, will draw the shortest path between the two red dots.
Clicking this button should currently throw an exception—you’ll be implementing this later as well.
-
If you want to customize the different options (e.g. change the number of rows and columns in the grid maze, change the percentage of walls removed), you can modify the
main
method to do so—we will not be looking at this file when grading, so feel free to change anything there.
Navigating the Codebase (Part 1)¶
Background
Understand the package layout.
You don’t need to understand everything immediately, but it will be difficult to complete the assignment if you don’t know where anything is.
Mazes¶
Of course, there’s more in the mazes
package than just the Main
class.
- The
mazes.entities
package contains basic data structures representing individual components of the maze.- The
Wall
andRoom
classes should be the only ones you need to interact with directly to complete the assignment.
- The
- The
mazes.gui
package includes all the GUI code; you shouldn’t need to reference these files, but you’re welcome to take a look if you’re curious. - The
mazes.logic
package contains all the main application logic—the code used to generate and solve mazes.mazes.logic.generators
contains the generators for grid-based and Voronoi-based mazes.mazes.logic.carvers
contains the maze “carvers”—the random removal carver and the Kruskal-based on that you will implement later.mazes.logic
also includes aMazeGraph
class that serves as the primary graph representation used throughout the application, but the class itself does not contain much code and merely extends a graph from thegraphs
package instead.
Graphs¶
Meanwhile, the graphs
package is a generic library of graph data structures and algorithms. Here are a few classes that are related to Dijkstra’s algorithm.
graphs.Graph
: a basic directed graph, with generic type parameters for vertex and edge types.graphs.BaseEdge
: the base edge class; always directed and weighted.graphs.Edge
: the primary implementation ofBaseEdge
.graphs.EdgeWithData
: aBaseEdge
that additionally contains some extra, generic data; used byMazeGraph
.
graphs.shortestpaths
: contains algorithms for finding shortest paths
Solving Mazes¶
Background
Understand the interfaces involved in the first portion of the assignment.
The primary maze-solving logic is in mazes.logic.MazeSolver
, but the class basically just constructs a MazeGraph
and uses a ShortestPathsFinder
. This means that you won’t need to interact directly with MazeSolver
; instead, in order to get maze solving working, you just need to implement a ShortestPathsFinder
: namely, the DijkstraShortestPathsFinder
.
We won’t go over all the interfaces here; only the most important ones. Make sure to look around in the code to find documentation for other classes.
Shortest-Path Finder¶
Background
The ShortestPathFinder
interface describes an object with a method that computes shortest paths.
Note
The generic type declaration for this interface (and some others in this assignment) is particularly nasty. Fortunately, you shouldn’t need to worry about the exact definitions while implementing the code; the only important thing to know is that G
is a Graph
, V
can be any object, and E
is a BaseEdge
.
Signature | Description |
---|---|
ShortestPath<V, E> findShortestPath( G graph, V start, V end) | Computes a shortest path from start to end in given graph, and returns a ShortestPath object. |
In the Dijkstra-based implementation that you will be implementing, the method above is broken into two sub-methods:
Signature | Description |
---|---|
Map<V, E> constructShortestPathsTree( G graph, V start, V end) | Returns a (partial) shortest paths tree (a map from vertex to preceding edge) containing the shortest path from start to end in given graph. |
ShortestPath<V, E> extractShortestPath( Map<V, E> spt, V start, V end) | Extracts the shortest path from start to end from given shortest paths tree. |
The ShortestPath
object returned is essentially a container for edges, but also includes some other convenience methods.
Since all information needed is provided as method parameters, normal implementations shouldn’t require any fields or other persistent state. (This functionality could be defined as a static method, but having an associated object allows our grader code to be more flexible.)
Graph¶
Background
The path finder only requires the most basic functionality from the Graph
it operates on:
Signature | Description |
---|---|
Collection<E> outgoingEdgesFrom(V vertex) | Returns an unmodifiable collection of the outgoing edges from the given vertex. |
Note
The method returns a Collection
; this means that it’s up to the implementation to decide exactly what Collection
implementation to use (usually a List
or Set
).
Note
The returned Collection
is unmodifiable, so any attempts to modify it directly will throw an UnsupportedOperationException
. (It’s still possible to create a copy of the collection and modify that, though.)
Sample Lazy Implementation¶
Reference
The LazyShortestPathFinder
class provides examples for working with the other interfaces.
It will probably be useful to take a look at this class before you begin implementing Dijkstra’s algorithm. (The code doesn’t actually compute correct shortest paths most of the time, but the syntax for using Graph
, BasicEdge
, and ShortestPath
is correct.)
Dijkstra Implementation¶
Task
Complete DijkstraShortestPathFinder
using (a modified version of) Dijkstra’s algorithm to implement the ShortestPathFinder
interface.
With all the interfaces out of the way, you can finally start implementing Dijkstra’s algorithm (although it might be helpful to review the lectures and sections on the shortest path tree first).
Some implementation notes:
- You can use the
Double.POSITIVE_INFINITY
constant to represent infinity. - Recall that Dijkstra’s algorithm requires that we start by initializing the distances of all possible vertices to infinity. This isn’t actually possible with our graph interface, and also may not be feasible in practice for graphs with many vertices—more than a computer could store in memory, or potentially even infinitely many vertices. To save memory, we will implement a slightly-different version of Dijkstra’s algorithm with a couple fundamental differences:
- Instead of initializing values for all vertices at the beginning of the algorithm, we’ll initialize values for only the starting vertex. This necessitates that we also change our relaxation operation to match, to initialize values for new vertices as they are encountered.
- Additionally, since the maze application has a particular destination in mind, our algorithm does not need to compute the full SPT; we can stop as soon as we have found the shortest path from the starting vertex to the destination.
- Since Dijkstra’s algorithm relies heavily on a priority queue, we’ve provided an alternate priority queue implementation in the skeleton code. If you wish to try using your own heap from the previous assignment anyway, you may change
DijkstraShortestPathFinder
to do so, as described in the class itself.
Once you’re done and all your tests are passing, try re-running the program and click the “Find shortest path” button. If everything went well, the program should now draw a red line connecting the start and the end! (Or, if there is no valid path, display an alert box stating so.)
Testing¶
Unfortunately, if you find yourself passing our unit tests, but failing stress tests on the grader, your best course of action will be to carefully review your code until you figure out where your code deviates from Dijkstra’s algorithm.
Some of our stress tests will also check your code’s runtime; one will time your code on random graphs with many vertices and edges (so the shortest paths end up being only several edges in length), whereas another will test your runtime with very long paths. Again, if you fail these tests, make sure that you’re following the pseudocode in Dijkstra lecture correctly.
As always, if you find yourself debugging for over an hour, definitely post on Ed or come to office hours for assistance—we’re here to help you learn, and struggling on your own through multiple hours of debugging is not an efficient way to learn. (Additionally, by bringing our attention to bugs that our unit tests don’t catch, you help us write better tests for future quarters.)
Finally, for your convenience, here are some diagrams of graphs from provided tests.
Graphs used in tests:
Start and end vertices have bold outlines.
Graph with multiple paths between start and end:
Graph where least-cost path has more edges than other paths:
Graph requiring relaxation:
Graph not requiring relaxation:
Submission¶
Task
Commit and push your changes to GitLab before submitting to Gradescope.
Code from the second portion of the assignment does not interact with the code from this portion, so now is a good time to try submitting.
When you’re ready, continue on to the next section: Kruskal’s algorithm.