Lab 10: Shortest Paths & Hashing

Lectures needed for this lab: Lecture 23 (Shortest Paths), or Chapter 22. The bonus part uses Lecture 26 (Hashing I) and Lecture 27 (Hashing II), or Chapters 25 and 26.

FAQ

Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for Lab 10 is located here.

Introduction

In this lab, we’ll pick up where we left off last time with Dijkstra’s algorthim.

If you finish that, there is bonus content on hashing: writing equals and hashCode for a small class, testing whether a hash code is any good, and finding the flaw in a hash function that looks fine at first glance. The bonus part is not required for checkoff.

Goals and Outcomes

By the end of this lab, you will…

  • Be able to implement Dijkstra’s algorithm using a priority queue that supports changePriority.
  • Be able to read shortest paths and distances off of the distTo and edgeTo arrays it builds.

Bonus:

  • Get more practice with equals using instanceof.
  • Understand why a class that overrides equals must also override hashCode, and what goes wrong in a HashSet if it doesn’t.
  • Be able to tell a good hashCode from a bad one, both by writing a test and by looking at a picture.
  • Have seen how integer overflow can quietly ruin a hash function.

Setup

Follow the Assignment Workflow Guide to get started with this assignment. This starter code is in the lab10 folder. NOTE as with previous labs you do not need to submit this assignment. Instead, you will get credit by completing a checkoff with your TA during lab.

The graph code is a copy of Lab 9’s, renamed, so that this lab stands on its own:

Folder What’s in it
lab10lib Lab10Graph and ExtrinsicMinPQ, the two data structures you’ll build on. No need to open or modify these files.
lab10main Main, which builds an example graph and opens the visualizer. The other file in this package is the visualizer’s internals, and you don’t need to open it.
lab10algorithms Lab10Dijkstras. This is where you write code. Lab10DFS and Lab10BFS are provided already solved, since the visualizer uses them.

The bonus hashing files sit directly in src (SimpleOomage, ComplexOomage, OomageTestUtility, Hint, and a hash table visualizer) and tests (TestSimpleOomage, TestComplexOomage, plus two tiny sanity-check tests).

Lab10Graph

In this lab, you’ll be using a provided graph class called Lab10Graph.

Lab10Graph is an undirected graph whose nodes are Strings and whose edges have int weights. It has six methods:

Method What it does
void addNode(String s) Adds node s. Does nothing if s is already in the graph.
void addEdge(String u, String v, int w) Adds an undirected edge between u and v with weight w. If u or v isn’t in the graph yet, it is added.
boolean hasEdge(String u, String v) Returns whether there is an edge between u and v.
int edgeWeight(String u, String v) Returns the weight of the edge between u and v. Throws an exception if there is no such edge.
List<String> neighbors(String u) Returns the neighbors of u.
List<String> nodes() Returns every node in the graph.

In 61B, all graphs are simple, i.e. we do not allow self-edges (e.g. cow - cow) or parallel edges (two edges between cow - dog). The Lab10Graph class has the property that nodes and edges are returned by nodes and neighbors in the order added, though not all real world graph classes do this.

Part 1: Dijkstra’s Algorithm

If you completed lab 9 all the way, SKIP to “Main” and copy your code over.

Open lab10algorithms/Lab10Dijkstras.java.

public Lab10Dijkstras(Lab10Graph g, String source)

The constructor runs Dijkstra’s algorithm from source, treating every edge weight as a distance, and stores the resulting shortest paths tree. The three query methods then just read off the answers:

Method What it returns
boolean hasPathTo(String v) Whether there is any path from the source to v. The source always has a path to itself.
int distTo(String v) The total weight of the shortest path from the source to v. Throws IllegalArgumentException if there is no path.
List<String> shortestPathTo(String v) The shortest path as a list of nodes, starting with the source and ending with v. For the source itself this is the one-element list [source]. Throws IllegalArgumentException if there is no path.

We’ve provided the needed instance variables for you. The starter constructor already throws IllegalArgumentException if source is not a node of g.

The starter constructor also does step 1 of the algorithm below for you: it puts every node into the fringe with priority Integer.MAX_VALUE and sets the source’s distance and priority to 0. Your job is the rest.

The algorithm

Recall Dijkstra’s from lecture 23 (the demo is a good refresher). It keeps track of:

  • distTo: the best known distance from the source to each node, and
  • edgeTo: the node we came from on that best known path.

Then:

  1. Set distTo[source] = 0. Add every node to an ExtrinsicMinPQ with priority equal to its distTo (use a large value like Integer.MAX_VALUE for nodes you haven’t reached yet).
  2. While the priority queue is not empty, remove the node u with the smallest priority. If its distance is still “infinite”, every remaining node is unreachable and you must stop.
  3. For each neighbor v of u, relax the edge: if distTo[u] + edgeWeight(u, v) is less than distTo[v], update distTo[v] and edgeTo[v], and call changePriority(v, distTo[v]).

To answer shortestPathTo(v), walk edgeTo backwards from v to the source, then reverse the result.

You’ll need to use the provided ExtrinsicMinPQ class described in the next section.

Only relax edges to nodes that are still in the priority queue. Once a node has been removed, its distance is final, and calling changePriority on an item that isn’t in the queue throws an exception. contains is available to check if an item is in the queue.

Implement the constructor and the three query methods of Lab10Dijkstras.

ExtrinsicMinPQ

ExtrinsicMinPQ is a priority queue of Strings, where each item’s priority is an int supplied from the outside (hence “extrinsic”). You’ll use it for the fringe in Dijkstra’s algorithm. The methods you need:

Method What it does
void add(String x, int priority) Adds x with the given priority. Throws if x is already present.
String removeSmallest() Removes and returns the item with the smallest priority.
int size() Returns the number of items in the queue.
void changePriority(String x, int p) Changes the priority of x to p. Throws if x isn’t in the queue.
boolean contains(String x) Returns whether x is in the queue.

This project is called an extrinsicMinPQ because the priorities of an item are set extrinsically to the item. That is, the priority of a given String isn’t given by its alphabetical order or its length or anything like that, but rather the integer that is arbitrarily assigned to it.

Main

After passing the tests, to see your Dijkstra’s in action, open the Main class and run its main method. Then go to http://localhost:4567 in your web browser. In the Order dropdown, choose Lab10Dijkstras order and click Compute. The program will run your Lab10Dijkstras from the selected Start node, draw the shortest paths tree in blue, and label every reachable node with its distance. Click any node to see the shortest path to it. Visualize steps through the order in which Dijkstra’s settles the nodes.

You can select other Start nodes if you’d like.

To check off your lab, show your TA the visualizer after running Dijkstra’s from a start node of your choice: the shortest paths tree, the distances, and the path to one node you click on. The server keeps running until you stop the program, so when you’re done looking, stop Main in IntelliJ.

If you see an error about port 4567 already being in use, you probably have an earlier run of the visualizer still going. Stop it and try again.

Hashing

Everything from here on is bonus content. It is not required for checkoff, but it is good midterm 2 practice for the material from Lectures 26 and 27, and it’s short.

In this part, we’ll work to better our understanding of hash tables.

Part A: SimpleOomage

Your goal in this part of the lab will be to write an equals and hashCode method for the SimpleOomage class, as well as tests for the hashCode method in the TestSimpleOomage class.

To get started, open up the class SimpleOomage and take a quick look around. A SimpleOomage has three properties: red, green, and blue, and each may have any value that is a multiple of 5 between 0 and 255. For example, a SimpleOomage with red=35, green=90, and blue=215 would be valid, since all of these are multiples of 5 between 0 and 255. Try running SimpleOomage and you’ll see four random Oomages drawn to the screen.

equals

Start by running TestSimpleOomage. You’ll see that you fail the testEquals test. The problem is that two SimpleOomage objects are not considered equal, even if they have the same red, green, and blue values. This is because SimpleOomage is using the default equals method, which simply checks to see if the ooA and ooA2 references point to the same memory location.

Your first task for this bonus part is to write an equals method.

We’ve already done this before, e.g.

if (o instanceof SimpleOomage other) {
    // In here, "other" is o, but with type SimpleOomage,
    // so you can access other.red, other.green, and other.blue.
}

If o is not a SimpleOomage (including if it is null), the condition is simply false. For a complete example of an equals method written this way, see the ColoredNumber example from Lecture 27 or the ArraySet example from Lecture 10.

Override the equals method so that it works properly. Make sure to test your equals method by running the test again. After fixing equals, your code should now pass the test.

A Simple hashCode

In Java, it is critically important that if you override equals that you also override hashCode. Uncomment the testHashCodeAndEqualsConsistency method in TestSimpleOomage. Run it, and you’ll see that it fails. The reason is that we’ve overridden equals but not hashCode.

To understand more deeply why this failure occurs, consider the code shown below.

Two questions to ponder when reading this code:

  • What should each print statement output?
  • What will each print statement output?
public void testHashCodeAndEqualsConsistency() {
    SimpleOomage ooA = new SimpleOomage(5, 10, 20);
    SimpleOomage ooA2 = new SimpleOomage(5, 10, 20);

    IO.println(ooA.equals(ooA2));

    HashSet<SimpleOomage> hashSet = new HashSet<>();
    hashSet.add(ooA);
    IO.println(hashSet.contains(ooA2));
}

Think about it before you click.

Click to reveal the answers
  • The first print statement should and will output true, according to the definition of equals that we created in the previous part of the lab.
  • The second print statement should output true. The HashSet does contain a SimpleOomage with r/g/b values of 5/10/20!
  • The second print statement will print false (almost always). When the HashSet checks to see if ooA2 is there, it first computes ooA2.hashCode(), which for our code is still the default hashCode(), based on the memory address. Since ooA and ooA2 have different addresses, their hash codes will (almost certainly) be different, so the HashSet looks in the wrong bucket and never even calls equals. The only way it prints true is if the two addresses happen to land in the same bucket by luck.

The Java specification for equals mentions this danger as well: “Note that it is generally necessary to override the hashCode method whenever the equals method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.”

Uncomment the given hashCode method in SimpleOomage, which will return a hashCode equal to red + green + blue. Note that this hashCode is now consistent with equals, so you should now pass all of the TestSimpleOomage tests.

testHashCodePerfect

While the given hashCode method is okay, in the sense that it is consistent with equals and thus will pass testHashCodeAndEqualsConsistency, it is only using a tiny fraction of the possible space of hash codes, meaning it will have many unnecessary collisions.

Our next goal for the SimpleOomage class will be to write a perfect hashCode function. By perfect, we mean that two SimpleOomages may only have the same hashCode if they have the exact same red, green, and blue values.

…but before we write it, fill in the testHashCodePerfect of TestSimpleOomage with code that tests to see if the hashCode function is perfect. Hint: Try out every possible combination of red, green, and blue values and ensure that you never see the same value more than once. Feel free to use any data structure you want.

Run this test and it should fail, since the provided hashCode method is not perfect.

A Perfect hashCode

To make the hashCode perfect, set the USE_PERFECT_HASH variable to true in SimpleOomage and in your hashCode() method, replace return 0 with a new hash code calculation that is perfect. Finally, run TestSimpleOomage and verify that your perfect hashCode method passes your test. Your TestSimpleOomage test might take a few seconds to complete execution.

Evaluating the perfect hashCode in JUnit

Fill in the haveNiceHashCodeSpread(List<Oomage> oomages, int M) method in the OomageTestUtility class so that it returns true if the given Oomages would have a nice spread if thrown into M buckets using their hashCodes. We define a nice spread as:

  • No bucket has fewer than N / 50 oomages.
  • No bucket has more than N / 2.5 oomages.

where N is the number of oomages. In other words, the number of oomages per bucket has to be within the range (N / 50, N / 2.5).

For the purposes of converting an Oomage’s hashCode to a bucket number, you should compute bucketNum = Math.floorMod(o.hashCode(), M), where o is an Oomage. This is the same conversion the provided visualizer uses. Note that a hashCode can be negative, and in Java -7 % 10 is -7, not 3, so using % directly would give you a negative bucket number. Math.floorMod always returns a result between 0 and M - 1. See the FAQ for why we don’t use Math.abs instead.

Fill in haveNiceHashCodeSpread in OomageTestUtility. Once you’ve written this method, try running TestJankyOomage and it should fail. Try running TestNiceSpreadOomage and it should pass.

Now uncomment testRandomOomagesHashCodeSpread in TestSimpleOomage and make sure USE_PERFECT_HASH is true in your SimpleOomage class. Most likely, your hash code will fail this test, even though it is perfect. To understand why, let’s turn to visualization. If by some chance your hash code passes, that’s fine, you should still use the visualizer to see how your hashCode performs visually in the next section.

Evaluating the perfect hashCode Visually

To get a better understanding of how hash tables work, we will use a hash table visualizer. Specifically, we’ve provided a method with the signature visualize(List<Oomage> oomages, int M, double scale) that shows the distribution of the given oomages across the M buckets according to their hashcodes (and scale is a special parameter that controls the size of some aspects of the drawing).

To try it out, run the HashTableVisualizer provided. Your visualization will probably look like this (if your hash code fails the testRandomOomagesHashCodeSpread test from the previous section):

visualizer with everything in two buckets

Or if your hash code is already good enough that everything spreads out nicely, it’ll look like this:

visualizer with a nice spread

If you’re getting a figure similar to the first where everything is in two buckets, here’s why: Even though your hashCode is perfect, it’s always returning a multiple of 5. Try changing M to 9 in HashTableVisualizer, and you should see a nice spread of values. Understanding why this is happening is a great idea.

If you’d like to make your hashCodes work well for any number of buckets, you should ensure that it is not always a multiple of any number. One way to do this is to divide the red, green, and blue values by 5 before computing the hash code.

Experiment With the Visualizer (Optional)

Once you’ve got a nice spread, try out the visualizer with scale = 0.5, N = 2000, M = 100.

Try messing around with N and M and see how the visualizer behaves on your SimpleOomage class. If there isn’t enough room to fit everything on screen, try resetting the scaling factor to a number less than one. Compare the distribution of items for the perfect vs. imperfect vs. default hashCodes. Does what you see match what you expect?

Part B: ComplexOomage

The ComplexOomage class is a more sophisticated beast. Instead of three instance variables representing red, green, and blue values, each ComplexOomage has an entire list of ints between 0 and 255 (not necessarily multiples of 5). This list may be of any length.

This time, you won’t change the ComplexOomage class at all. Instead, your job will be to write tests to find the flaw in the hashCode function.

Evaluating the ComplexOomage hashCode

The provided hashCode is valid, but it does a potentially bad job of distributing items in a hash table.

Start by visualizing the spread of random ComplexOomage objects using the visualizer. Use the randomComplexOomage method to generate random ComplexOomages. You should find that this visual test shows no apparent problem in the distribution of randomComplexOomages.

Also try uncommenting testRandomOomagesHashCodeSpread in TestComplexOomage. You’ll see that it passes testRandomOomagesHashCodeSpread just fine, reinforcing what you just saw in the visualizer. For totally random ComplexOomages, everything is fine.

A Short Detour: How Java Stores an int

To find the flaw, it helps to know a little about how Java stores integers. We haven’t covered this in lecture, so here is the short version.

A Java int is stored as 32 bits, where each bit is a 0 or a 1. These are the “digits” of the number written in base 2 (binary), the same way we write numbers in base 10 with the digits 0 through 9. For example, the number 5 is 101 in binary, because 5 = 1·4 + 0·2 + 1·1. One of the 32 bits is used to record the sign, which is why ints range from -2,147,483,648 (−2³¹) up to 2,147,483,647 (2³¹ − 1).

Two consequences of this matter for us:

  • Multiplying by 256 shifts the bits. In base 10, multiplying by 100 shifts every digit two places to the left and appends two zeros. For example, 713 * 100 gives 71300. In base 2, multiplying by 256 = 2⁸ shifts every bit eight places to the left and appends eight zeros.
  • Arithmetic overflows silently. If a calculation produces a result that needs more than 32 bits, Java does not crash or warn you. It just throws away the bits that don’t fit, keeping only the lowest 32. This is why Integer.MAX_VALUE + 1 is a large negative number, and it is also why hashCode values are often negative. For example, 1000000000 * 4 in Java is -294967296 because of overflow.

Try running Hint.java, which prints the first few powers of 256 as Java computes them. The output may surprise you. Think about what it means for the hashCode method in ComplexOomage, which multiplies by 256 once per item in params.

testWithDeadlyParams

In this case, we need to look at the hashCode to find the problem.

Fill in the test testWithDeadlyParams such that the provided hashCode function fails due to poor distribution of ComplexOomage objects.

Given what we’ve learned in 61B so far, this is a really tricky problem! Use what you learned in the detour above, and remember that Hint.java is there to help.

Your test should not fail due to an IllegalArgumentException.

Once you’ve written this test and ComplexOomage fails it, you’re done with the bonus part of Lab 10!

Fix the hashCode (optional)

Consider how you might change the hashCode method of ComplexOomage so that testWithDeadlyParams passes. Are there other deadly parameters that might strike your hashCode method?

Checkoff

As you work through the lab, check in with your TA as a group to get attendance credit. Your TA will explain how check-ins work in your section.

For your checkoff, show your TA the visualizer running your Lab10Dijkstras from a start node of your choice (see Main above).

You do not need to have everything 100% correct to get credit. Keep working on the lab while you wait for your TA!

Deliverables

There is nothing to submit for this lab. You get credit by checking off with your TA during your lab section.

Files that you need to modify:

  • lab10algorithms/Lab10Dijkstras.java

Bonus (optional):

  • src/SimpleOomage.java
  • src/OomageTestUtility.java
  • tests/TestSimpleOomage.java
  • tests/TestComplexOomage.java