The graphs is a powerful and fundamental data abstraction in computer
science. It is defined to be a set of vertices and edges and can be
used to represent many things, such as network connections,
dependencies, image compositions, state machines, and artificial
neural networks. It is *critical* for you understand graphs if you
want to pursue a future in computer science<-->whether that's in
research or industry. We will explore some of the most fundamental
graph algorithms today, namely *breadth first search* (BFS), *depth
first search* (DFS), *Dijkstra's algorithm*, and the *A star
algorithm* (A*).

## A. Introduction to our Maze Solver

In this lab, we'll explore how a few graph algorithms behave in the context of mazes, like the one shown below. We will only be using this maze visualization with a select few of the graph algorithms (BFS, DFS, and A*, not Dijkstra's; we will work with Dijkstra's algorithm in a different way for this lab).

One way to represent a maze is as an undirected graph. The vertices of such a graph are shown below, with one dimensional (vertex number) coordinates on the left version and (X, Y) coordinates on the right version. If there is no wall between two adjacent vertices, then the corresponding graph has an undirected edge between the vertices. For example, adj(11) would be an iterable containing the integers 12 and 16.

Following the representation method dictated above, both of these mazes could be represented as the graph shown below, where each red circle represents a vertex (also called nodes) and each black line represents an undirected edge between two vertices.

In this lab, you'll implement a few key graph algorithms using the
provided `Maze`

class, which has the following methods of interest:

` `**public int N()**: Size of the maze [mazes are N x N]
**public int V()**: Total number of vertices in the maze
**public Iterable** adj(int v) : Returns the neighbors of v
**public int toX(int v)**: Returns the x coordinate of vertex v
**public int toY(int v)**: Returns the y coordinate of vertex v
**public int xyTo1D(int x, int y)**: Returns the vertex number of x, y

We've provided `MazeDepthFirstPaths.java`

, a version of *depth first
paths* adapted for use with mazes. Later in the lab, we will ask you
to implement *breadth first paths* and a *cycle detection algorithm*.
For those of you who want a deeper understanding of graph algorithms,
we've also provided an optional challenge to implement the *A*
shortest paths algorithm*. For this particular section of the lab, you
will be required to modify the following files:

`MazeBreadthFirstPaths.java`

: Uses BFS to find all paths from a given source, terminating as soon as the target vertex is observed.`MazeCycles.java`

: Searches for cycles in the maze. If a cycle is detected, the algorithm terminates.

The following file is optional:

`MazeAStarPath.java`

: Searches for the shortest path from source to a target using A*, terminating when the target is observed.

These maze solvers should be subclasses of the abstract `MazeExplorer`

class, which has the following fields and methods:

` `**public boolean[] marked**: Locations to mark in blue
**public int[] distTo**: Distances to draw over the Maze
**public int[] edgeTo**: Edges to draw on Maze
**public Maze maze**: The maze being solved
**public void announce()**: Call whenever you want the drawing updated
**public solve()**: Solves the given Maze problem

The `Maze`

class has special functionality built in so that it can see
your `MazeExplorer`

's public variables. Specifically, whenever you
call `announce`

, it will draw the contents of your `MazeExplorer`

's
`marked`

, `distTo`

, and `edgeTo`

arrays. Make sure to call the
`announce`

method any time you want the drawing to be updated.

As an example, try compiling and running
`TrivialMazeExplorerDemo.java`

in IntelliJ. Open up the
`TrivialMazeExplorer.java`

and `TrivialMazeExplorerDemo.java`

files to
understand what's going on.

If you would like to compile these files without IntelliJ, simply run
`make`

or `javac -g *.java`

in the lab directory with all the Java files.
To run a particular demo, say `TrivialMazeExplorerDemo`

, execute ```
java
TrivialMazeExplorerDemo
```

in the command line.

As a more complex example, try compiling and running `DepthFirstDemo`

.
This code was adapted from the
DepthFirstPaths class.

Before moving to the next section, try tweaking the parameters of the
maze by editing the `maze.config`

file. There are three different
types of maze (`SINGLE_GAP`

, `POPEN_SOLVABLE`

, and `BLANK`

) to choose
from. A "%" sign at the beginning of a line in the config file comments
it out. Feel free to play around with all different types by changing
which `MazeType`

s are commented out.

## B. Breadth First Search

BFS and DFS are very similar. BFS uses a queue (FIFO) to store the fringe, whereas DFS uses a stack (FILO). Naturally, programmers often use recursion for DFS, since we can take advantage of and use the implicit recursive call stack as our fringe. For BFS? There are no implicit structures that we can use. We must use a loop to simulate the expansion of the fringe.

You will need to use a FIFO queue for this part. Luckily, Java's
powerful library already has a [`Queue`

interface] built in.
Read the interface documentation carefully. **Hint:** see if you can
find a familiar `Collection`

-implementing class that also implements
this `Queue`

interface. Feel free to use any of them.

You'll now write a class `MazeBreadthFirstPaths.java`

that extends
`MazeExplorer`

. It is highly recommended you look at the code in
`MazeDepthFirstPaths`

and use it as inspiration. When you compile and
run `BreadthFirstDemo.java`

, you should see your algorithm crawl the
graph, locating the shortest path from position (1, 1) to (N, N),
stopping as soon as the (N, N) position is found.

You can also use
BreadthFirstPaths
as inspiration, as well as this video
created by Professor Hug showcasing the expected behavior of each
class (though there's a small bug in `MazeBreadthFirstPaths`

that he
pointed out during the video).

## C. Depth First Search & Cycle Check

In the world of graph theory, there exist many cycle detection
algorithms. For example, the union-find algorithm can detect cycle in
$O(E \cdot \lg V)$ time. For today's exercise, we will use DFS to detect
cycles in this maze (an undirected graph) in $O(V + E)$ time. For every
visited vertex `v`

, if there is an adjacent `u`

such that `u`

is
already visited and `u`

is not parent of `v`

, then there is a cycle in
graph.

For this part of the lab, you'll write a cycle detection algorithm.
When you compile and run `CyclesDemo`

, you should see your algorithm
crawl the graph. If it identifies any cycles, it should connect the
vertices of the cycle using purple lines (by setting values in the
`edgeTo`

array and calling `announce()`

) and terminate immediately.
The vertices of the part of the graph that has been traversed to find
the cycle should also be drawn, but there should be no edges
connecting the part of the graph that doesn't contain a cycle. **The
only edges that should be drawn are the ones connecting the cycle.**
Consider using another data structure to keep track of edges until a
cycle is detected and `edgeTo`

is updated in order to avoid
displaying edges that are not part of the cycle. You
can change the maze type by making edits to your `maze.config`

file,
allowing you to test on a maze with cycles.

You can use either recursion or a `Stack`

class for DFS. If you decide to go with latter, you need to look up
the Java `Stack`

class, or use some linear structure in a FILO
fashion.

## D. Dijkstra's Algorithm

Dijkstra's algorithm is useful when we want to find the shortest paths from a starting vertex to all vertices in the graph, effectively finding the 'shortest paths tree' (SPT).

You will be implementing Dijkstra's algorithm in the file
`Graph.java`

. Take a look at that class and familiarize yourself with
how the graph is being represented. For this method, assume that each
edge in the graph has a weight field that is a positive integer, which
will be represented by the `Edge`

object's `edgeWeight`

field.

For this exercise, we will not ask you to reconstruct the paths in your algorithm. However, implementing this functionality is good practice and may be something you want to try out on your own!

**Hint 1:** At a certain point in Dijkstra's algorithm, you have to
change the value of nodes in the fringe. Java's priority queue does
not support this operation, unfortunately. This is understandable; they are
using a heap to implement the queue, and finding an arbitrary element in a heap
in order to update its position is expensive. Instead, we can simply use
a `TreeSet`

, which supports finding and removing the smallest element
in $\lg N$ time as well as removing and adding items in
$\lg N$ time. Thus, you can remove an element from the queue,
change its priority, and then re-insert it (in that order).

**Hint 2:** Adding the vertices to our priority queue fringe directly
won't be enough. Our vertices are Integers, so our priority queue will
order them by their natural ordering. Is this what we want? If not, is
there a way we can change how to order the items in the queue? (Be careful
here. In order for `TreeSet`

to work, the ordering relation must never
give two items equal priority. Sets do not have duplicates, and `TreeSet`

will throw out items that are given equal ordering. Fortunately, it doesn't
matter which of two nodes with equal weight gets chosen as smaller, so you
can arrange to order first by weight and break ties by choosing the
smaller-numbered node.)

### Runtime

When implemented properly using a binary heap, Dijkstra's algorithm should run in $O((|V| + |E|) \cdot \log |V|)$ time. This is because at all times our heap size remains a polynomial factor of $|V|$ (even with lazy removal, our heap size never exceeds $|V|^2$), and we make at most $|V|$ equeues and $|E|$ updates requiring heap operations.

For connected graphs, the runtime can be simplified to $O(|E| \cdot \log |V|)$, as the number of edges must be at least $|V|-1$. Using alternative implementations of the priority queue can lead to increased or decreased runtimes.

## E. A* (optional, but worth a read)

In graph theory, determining the shortest path between two nodes is one of the most common and important questions asked. This problem has many real world examples, with shortest route between two cities as one of the most overused in computer science. Dijkstra's algorithm is the most basic shortest path algorithm and can find the shortest path between two points assuming no negative edge weights. Dijkstra's is very similar to BFS, for we can replace the queue in BFS with a priority queue (with some more minor tweaks) and end up with Dijkstra's!

However, Dijkstra's algorithm is a uniform-cost search. If we want to
find the shortest path from SF to NYC, Dijkstra's will expand in all
directions centered at SF, meaning the traversal will reach Seattle
before even getting close to the East coast. It can explore in the
wrong direction and end up wasting time doing unnecessary work.
However, we can make it "smarter" by giving it a *heuristic*.

Introducing A* ("A star") search! A* is the state-of-the-art shortest path finding algorithm (given that the programmer provides a good heuristic, such as the Manhattan distance to the destination). Let's go back to the SF to NYC path finding analogy: with this new heuristic, A* will prioritize moving to the East first, since our heuristic will tell it that moving straight up toward Seattle (going to Canada?) is bad compared to moving toward Denver (closer to NYC).

Here is a nice visualization for BFS, DFS, Dijkstra's algorithm, and A* algorithm. We highly recommend playing around with it to improve your understanding of these most basic graph algorithms.

For this part of the lab, you'll implement the A* algorithm. When you
compile and run `AStarDemo`

, you should see your algorithm crawl the
graph, seeking the shortest path from (1, 1) to (N, N). Unlike BFS,
the algorithm should take into account the target vertex.

For your heuristic h(v), we recommend that you use the Manhattan distance, which can be simply expressed as:

` Math.abs(sourceX - targetX) + Math.abs(sourceY - targetY);`

Experiment with different graph types and heuristics to see how they behave.

## Submission

- You need to submit
`MazeBreadthFirstPaths.java`

,`MazeCycles.java`

, and`Graph.java`

with Dijkstra's algorithm implemented. `MazeAStarPath.java`

is optional.- Make sure to run
`BreadthFirstDemo`

and`CyclesDemo`

and that your code functions correctly before you submit!