Kotlin

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.

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

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:

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`String`

s. 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!

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.