MP3: Restaurant Graphs and Hashing

Created By: Geoffrey Challen
/ Updated: 2021-11-29

As we continue MP3 we'll work on a task that requires us to apply both what we know about graphs and what we know about hashing. The restaurant preferences data actually forms a graph, and to complete the next test you'll need to traverse it. And there is also a bit of hashing-related work to do as well.

Sets and Hashing

Before we discuss how to treat the related restaurants like a graph, let's examine an important connection between Java sets and hashing.

Traversing the Restaurant Graph

Today's task continues work on our RelatedRestaurants class. Previously you completed getRelated, which used the data parsed from the preferences.csv file to establish relationships between restaurants. Two restaurants were related if they appeared in the same users list of preferences, and the strength of their relationship was determined by the number of times that they appeared together.

Viewed another way, this data forms a graph, where nodes are restaurants, and edges determined by the existince of a relationship between two restaurants. Note that this graph is:

  • undirected: since if A appears in the same preference list as B then B also appears with A
  • weighted: with the weights corresponding to the strength of the relationship between two connected restaurants
  • not necessarily connected: since it's possible that there are restaurants that are not related to any other restaurant, or clusters of connected restaurants that are not connected to any other cluster

To pass testGetConnectedTo you'll need to traverse this graph of related restaurants to count the number of restaurants within a two-hop neighborhood of a given starting point. However, as a twist, you should only consider nodes to be connected if they have a weight greater than 1! Let's discuss how to do this visually first:

Discuss how the restaurant relationships form a undirected weighted graph, how to traverse it, and how to avoid edges with low weights. This explanation should be language agnostic!

As a more complete description of your task, you should complete a new method getConnectedTo on your existing RelatedRestaurants class as follows. getConnectedTo should take a String containing a restaurant ID and return a Set<Restaurant>. The set should contain all restaurants that are within two hops of the starting restaurant when the restaurant relationships are considered as a graph. You should also not consider edges with a weight of one—so only pairs of restaurants that appear in two or more lists together are considered connected for the purposes of this problem. If the restaurant ID passed to getConnectedTo is not valid, you should throw an IllegalArgumentException.

You'll probably want to review the lessons on graphs, and the practice problem that we completed that is fairly similar. A few other notes:

  • The set should not contain the passed restaurant ID
  • You'll probably want to use your existing getRelated method, since the map it returns represents the neighbors of a given restaurant and the weights of the connections
  • You may need to add code to your existing constructor to help solve this problem
  • Note that the return type is Set<Restaurant>, but the starting point and the keys in the map returned by getRelated are Strings. A reasonable approach computes a Set<String> containing restaurant IDs first and then converts it into a Set<Restaurant>.
  • You should review the walkthrough on sets and hashing above, and will probably need to add some code to your Restaurant class

This is the final algorithmic challenge on the machine project. Good luck!

No Homework Today

As a reminder, on lessons where we focus on the machine project we will not assign a homework problem! However, the lesson will usually focus on helping you complete a particular part of the MP test suite, and so we encourage you to spend time on that in lieu of a homework problem.

Today your goal should be to complete the second MP3 test case: testGetConnectedTo.

If you get stuck, find us for help on the help site or forum.