Homework 8: Graph Algorithms - Programming

Due by 11:59PM EDT on Monday, November 18, 2024

Required Problems (170 points)

Setup and Logistics

We have put together several stub files –– click here to download them.

At least 12 files to submit: ResizingDequeImpl.java, ResizingDequeImplTest.java, Graph.java, GraphTest.java, MazeSolver.java, MazeSolverTest.java, IslandBridge.java, IslandBridgeTest.java, Dijkstra.java, DijkstraTest.java, WidestPath.java, WidestPathTest.java
Make sure to submit any other files you write which are required to compile your code!

Be sure to follow these guidelines:

• Ensure source files are not located in any package and that none of the files have a package declaration (e.g. package src;).
• When submitting, submit each file individually at the root level (not contained in a folder or zip files).
• Ensure that your own test files pass and do not run into infinite loops.
• You have unlimited submissions until the deadline on the autograder marked [compilation], and two free submissions on the autograder marked [full].
• For this assignment:
  • Number of Free Submissions: 2
  • Deduction Per Additional Submission: 10 points
  • Max Code Coverage Deduction: up to 20 points
  • Max Style Score Deduction: up to 5 points
  • Manual TA Efficiency/Style Grading: yes
• Do not wait until the last minute to try submitting. You are responsible for ensuring your submission goes through by the deadline.
• Before asking questions on Piazza, be sure to check and keep updated with the pinned clarifications post.
• Gradescope issues? Be sure to check out our Gradescope help page before posting to Piazza.

Motivation: Network Connectivity

You can think of the Internet as a graph where machines and routers are vertices, and the wires between them are edges. Various questions concern the implementation and structure of the Internet, such as “How many hops must a message take to reach a destination?” and “What is the cheapest way to connect and route all computers to each other?”

In this assignment, you will implement several data structures and algorithms to answer these questions. Note: using items from Java collections is okay (examples: Collections.sort) except for the Queue and Deque/Stack classes! You must use your own implementation for those.

Part 1: Binary Min-Heap (0 Points)

Files to submit: BinaryMinHeapImpl.java

We will provide a Gradescope submission so you can test your implementation from the Huffman assignment with unlimited submissions allowed and instant feedback. This submission will not count towards your grade. It is necessary to have a working version so that you can test your Dijkstra implementation which will make use of the BinaryMinHeapImpl class.

To test your heap, submit only BinaryMinHeapImpl.java to the Binary Min-Heap Autograder on Gradescope. You will have unlimited submissions.

Regardless, a working BinaryMinHeap will be provided when you submit to the autograder for this assignment. That is, you will not be submitting BinaryMinHeapImpl; we will run your code by providing a working version ourselves.

Part 2: Implementing a Resizing Deque (30 Points)

Files to submit: ResizingDequeImpl.java and ResizingDequeImplTest.java

A deque (pronounced deck) is a double-ended queue. It combines the functionality of queues and stacks. Queues typically only support adding to the back (enqueueing) and deleting from the front (dequeueing). Stacks support adding to the front (pushing) and deleting from the front (popping). A deque allows you to add and remove items to either the front or the back, and thus can function as either a stack or a queue.

You will implement the provided ResizingDeque interface. This API is a simplification of Java’s Deque interface.

Use a resizing array

You will implement your deque using array resizing. Inside your implementation, you should have an array for storing the elements of your deque. The array should start with a capacity of 2 elements, and it should double in size (resize up) every time it fills up. That is, whenever the addition of a new element would cause the deque to exceed the size of the array. Whenever the removal of an element would cause the number of elements in the deque to fall to less than one quarter of the size of the array, you should cut the size of the array in half (resize down). See the resizing up and down rules below for more details.

Generics and Weird Java Behavior

Note that Deque<E> is generic, so your implementation must also be generic; therefore the underlying array of elements must be of type E[]. Unfortunately, Java doesn’t cleanly support generic arrays, so the code to initialize a generic array of type E of size 2 in Java is

E[] array = (E[]) new Object[2];

Java is weird sometimes, so to get the size of your underlying array (for testing), you will need to do:

((Object[]) deque.getArray()).length;

Implement wraparound

Your implementation should use wraparound. After a series of pushes and pops, you may have a case where the head of your deque is not at array index 0, but maybe at an index farther along the array (like array index 4). After some more pushes, the index of the tail of your deque will get to the end of the array. The next push should then be at index 0, then index 1, etc.

Loitering

When you implement any method that removes an element from the array (such as pollFirst() and pollLast()), you should assign null to associated entry in the array – do not just increment/decrement your head/tail pointers. If you do not mark the element removed from the array as null, then references to that element will loiter in the array, i.e. Java’s garbage-collection mechanism won’t be able to clean up that memory, since there are still have references to an object.

Resize up:

When inserting an element would cause you to surpass the array’s capacity, you’ll want to:

1. Make a new array of double the length
2. Copy the old elements into this new array with the head pointing to index 0
3. Insert the new element

Examples:

[1,3] addFirst(7) = [1,3,_,7]
[1,2,4,3] addLast(9) = [1,2,4,3,9,_,_,_] (if head points to index 0 and tail points to index 3 originally)
[1,2,4,3] addLast(9) = [2,4,3,1,9,_,_,_] (if head points to index 1 and tail points to index 0 originally)
[_, _] addLast(1) = [1, _]
[_, _] addFirst(1) = [1,_]
[_,_,_,_,1,2,3,4], addLast(5) = [5,_, _,_,1,2,3,4]
[_,_,_,_,1,2,3,4], addFirst(5) = [_,_,_,5,1,2,3,4]
[1,2,_,_] addFirst(3) = [1,2,_,3]

Resize down

When removing an element that would cause you to have $<\frac{n}{4}$ elements where $n = array.length$:

1. Remove the element
2. Make a new array of half the size (but never resize smaller than 2)
3. Copy the old elements into this new array with the head pointing to index 0

Ex:

[_,1,_,_] pollFirst() = [_,_]
[_,_,_,_,1,2,_,_] pollLast() = [1,_,_,_]

Resizing Deque Visualizer

We are providing a visualizer to help you visualize your resizing deque. There are several important information regarding the limitations of the visualizer so please read the following carefully.

• Adding null or empty strings to the deque is prohibited. Setting the field to null is simply interpreted as a "null" string
• null values created due to initialization or resizing up/down are represented as empty cells
• The referentially equal elements determined by peekFirst() and peekLast() methods are denoted with blue and red bordered cells respectively. If these two elements overlap, the border is instead denoted as purple.

If you run into any difficulties using the visualizer, please post on Piazza.

Reminder!

Please make sure to make your implementation of ResizingDequeImpl.java generic; this means that the class header of ResizingDequeImpl.java should be public class ResizingDequeImpl<E> implements ResizingDeque<E>!

Part 3: Graph Representations (20 Points)

Files to submit: Graph.java, GraphTest.java

Since this homework will require implementing algorithms that run on both directed and undirected graphs, you will implement an optionally weighted-directed graph in Graph.java. That is, you have the option to use it as a weighted or unweighted graph, as well as a directed or undirected graph.

To use this class as a weighted/unweighted graph, you can choose to ignore edge weights to treat it like an unweighted graph and take into account the weights for a weighted (think about how BFS doesn’t use edge weights but Dijkstra’s does).

To use this class as a directed graph, each edge represents a single direction edge between two vertices. That is, to add the edge from u to v, add an edge from u to v.

To use this class as an undirected graph, inserting an undirected edge between u and v can be accomplished by inserted an edge from u to v AND an edge from v to u. That is, we are representing an undirected edge as two directed edges.

The implementation details are largely up to you, but be sure to consider the runtimes of each operation, which are provided in Graph.java. Please make sure that your solution only uses $O(m + n)$ space - don’t use adjacency matrices!

Also, to reach the time complexity we require, your adjacency list must be implemented as an array of HashMaps. That is, instead of using linked lists to maintain the outgoing edges for each vertex, you should use hashmaps that map the endpoints of the edges to the edge weights.

Your solution does not need to handle self-loop and parallel edges, but it must support negative edge weights. Overall, the graph implementation is largely up to you for design as long as it meets the space and time requirements. The graph implementation also assumes that the vertices will be represented by integers in $[0..n-1]$. The stub file provides more specific details.

For Fun: Defensive Programming

Something else to keep in mind is what data your methods expose. Remember, you should practice defensive coding. If you return the data structures containing your graph to a client, then they can modify them as they wish (which is very bad!). Thus, you should use Collections.unmodifiableXXX (where the XXX is Map, Set, etc.) to ensure that the user cannot modify the data structures you are passing them. We won’t be checking/grading for this, so this is just for fun!

Part 4: Let’s Talk About Design

Now that you have your basic data structures set up, it’s time to get into the algorithms. Take some time to read through the problems below, and think through what you need to solve them. Some problems may require you to write BFS, DFS, etc., so it may be a good idea for you to abstract this logic so that you do not need to code the same thing repeatedly.

Thinking about design now will help you in the long run, and will make this assignment more manageable. Many of the questions have hints about what sort of algorithms you will need to solve the problems, others are more open ended and will require you to put in more thought.

NOTE: this means you are allowed to create additional classes, and to submit these with your submission! How you design those classes is up to you – that’s part of the challenge of this assignment.

Part 5: Maze Solving Revisited (30 points)

Files to submit: MazeSolver.java, MazeSolverTest.java

It’s now halfway through the course, the perfect time for retrospection. Recall the very first homework: HW 0, Part 2, in which we gave you a maze and asked you to find a path to go from a specific source cell to a target cell on the maze. We solved that question using recursion, with an instruction on how to traverse through the maze in some specific order.

Realize that we can represent the maze as an unweighted undirected graph, where the vertices are cells in the maze, and the neighbors for each vertex are its up, down, left, and right adjacent cells, if they exist.

It is easy to see that our recursive approach from HW0 was essentially a depth-first search. However, as we now know, DFS is not guaranteed to return the shortest path between two vertices in the graph. This was also the case in HW0, where the path you ultimately found may not have been the shortest path from the given source to the given target cell.

Therefore, instead of using DFS, we’ll use BFS to find the shortest path from the source cell to the target cell.

In this problem you will implement the getShortestPath(int[][] maze, Coordinate src, Coordinate tgt) method in MazeSolver.java, whose input is the $m \times n$ 2D array consisting of 0s and 1s representing the maze, the source, and the target coordinate. The method returns a List<Coordinate> of the vertices on the shortest path from src to tgt. For more details, please refer to the JavaDoc in the stub file.

Your algorithm should run in $O(m\times n)$ time.

Maze Solver Visualizer

We have modified the visualizer from HW0 for you to use in this assignment as well! Please refer to the previous assignment’s instructions here if you need a reminder on how it works.

Part 6: Islands and Bridges (30 Points)

Files to Submit: IslandBridge.java, IslandBridgeTest.java

Consider a directed graph $G = (V, E)$ where the vertices are islands and the edges are one-way bridges between two islands. For a given island $x$, we are interested in the following claim: For any island $v$ that can be reached from $x$ through a series of bridges, there also exists a series of bridges to go from $v$ to $x$.

Design an algorithm that takes in as input a directed graph $G$ and an island $x$ and returns true if the claim holds for $x$, and false otherwise.

Your algorithm should run in $O(n+m)$ time.

Part 7: Shortest Paths and Dijkstra’s Algorithm (30 Points)

Files to Submit: Dijkstra.java, DijkstraTest.java

In lecture you learned how to solve the single-source shortest path problem for weighted graphs using Dijkstra’s algorithm. Specifically, given a weighted directed OR undirected graph $G=(V,E)$ and a source $s\in V$, Dijkstra’s algorithm can compute the shortest path from $s$ to every other vertex in $O((n+m) \lg n)$ time (assuming you use a binary min heap implementation of the priority queue).

For this part of the assignment, you will use your BinaryMinHeap implementation from Part 1 to implement Dijkstra’s algorithm. Your min heap will act as a priority queue, storing each vertex and its distance away from the source $s$. At each step of the algorithm, you will need to extract from the heap the vertex with the smallest distance from $s$ (this should tell you what the Key and Value should be).

While Dijkstra’s algorithm computes the shortest path from $s$ to all vertices in $V$, your implementation should only compute the shortest path from $s$ to a specific vertex $t$. See the stub file for more details. Your implementation should run in $O((n+m)\lg n)$ time.

Note: You may assume that the weights of all edges will be non-negative! Additionally, your implementation should work on both directed and undirected graphs.

Part 8: Widest Path Algorithm (30 points)

Files to submit: WidestPath.java, WidestPathTest.java

Consider a graph and a path $P$. The path $P$ is a widest path when the weight of smallest edge in $P$ is maximal. This maximal minimum-weight edge is known as a bottleneck edge. In other words, if you wanted to transfer a large amount of something (internet packets, car traffic, etc.) along a graph, and you considered edge weights to be capacities, you would want to find a path with the largest overall capacity. If we think about Internet packets, then the overall capacity of a route would be limited by the lowest-bandwidth connection in that route, as we would not be able to send more information along that path. Thus, the widest path is the path along which we can send the most stuff. The constraining edge on that path, or in this example, the lowest-bandwidth connection, would be the bottleneck edge of the path.

How can we algorithmically find a graph’s widest path? That’s up to you to devise and implement. There are multiple ways to solve this problem, so consider how you can do it with what you’ve already learned (namely, BFS and Kruskal’s). Note that within a widest path, edge weights are not necessarily distinct, and those weights take precedence over the length of the path. To clarify, if there are multiple widest paths with the same bottleneck but different lengths then any of those paths are a valid solution. Runtime for this algorithm should be $O((n + m)\lg n)$.

Important: Do not modify the private constructor.

Graph Algorithm Visualizers

Lastly, we have provided a visualizer for you to see your graph algorithms in action!

Eclipse Setup

For the graph algorithm visualizer we need you to add the graphJar.jar file to your build path. To do so, right click on your project in Eclipse → Build Path → Configure Build Path → Click on Classpath → Click on Add External JARs… on the right pane → select GraphJar.jar → Open → Apply and Close. Make sure that it is not under ModulePath, that will cause it to not work.

This is the same setup required to run the Huffman visualizer.

IntelliJ Setup

You should be able to run the visualizer(s) by right-clicking on the respective file and running the main() method. Otherwise, make sure that GraphJar.jar is added as a library to your project file by looking under (File → Project Structure → Libaries → Plus in the Right Pane → Select GraphJar.jar).

This should be the same setup as for the Huffman Visualizer.

Importing Graphs

At startup, the visualizer will require you to type in formatted text to import graphs. You can choose to import two types of graphs, undirected or directed.

The format for each line is as follows: {srcNode Id} {tgtNode Id} {edge Weight}. Use a single space to separate the three elements, with each edge taking up one line. The weight value must be an integer.

For both graph types, you need a line for each edge you intend to create.

When importing undirected graphs, the following input will create the graph shown below

a b 1
b c 2
a d 3
d c 2

Similarly for directed graphs, the input below results in the following

a b 2
b a 3
a c 4
c b 2

Once you fill in the source and target cell Id text fields, and press either of the two path buttons to see a path highlighted in dark green. As the widest path algorithm assumes an input of an undirected graph, the widest path button will only function if you import an undirected graph. The source and target vertex will appear blue and red respectively. If these overlap, the node will be highlighted in purple. Note how the result of the two algorithms can differ!

Style & Tests

The above parts together are worth a total of 170 points. Style and code coverage are graded on a subtractive basis with deductions as specified in the Setup and Logistics section of the writeup, and you will be graded according to the CIS 1210 style guide. Gradescope will give you your grade on this section immediately upon submission to either autograder.

You will need to write comprehensive unit test cases for each of the classes, inner classes, and methods you implement (including helper methods!) in order to ensure correctness. Make sure you consider edge cases and exceptional cases in addition to typical use cases. Use multiple methods instead of cramming a bunch of asserts into a single test method. Your test cases will be auto-graded for code coverage. Be sure to read the testing guide for some pointers on what level of testing we expect from you. Finally, due to the Code Coverage tools we use, please be sure to use JUnit 4 as it is the only version supported.

Note: You will not be able to write JUnit test cases for any private methods. Instead, make them package-private by leaving off any privacy modifier (i.e., do not write public or private).