Homework 5: Grapphle Maps

Setup and Handin

In order to set up the homework, download the stencil from here. To hand in, hand in the following files on Gradescope:

  • Directions.scala
  • DirectionsTestSuite.scala
  • README.txt

IntelliJ setup

It should be possible to open up the assignment folder and run it, just as you did for project 3.

Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our hours schedule here.

The Assignment

The goal of the assignment is to get you some practice working with two of the graph algorithms we’ve discussed in class: breadth-first search and Dijkstra’s algorithm. We’ve provided you with a class, MapGraph, that implements a (undirected) graph where the nodes are locations and the edges are a way of getting between two locations. Each edge has a kind (for instance, “car”, “walk”, or “train”), a cost (in dollars), and a time (in minutes). This class is in MapGraph.scala. In your functions you will want to use the incidentEdges function, which takes a node and returns all of the edges. Each edge is an object with from, to, time, and cost fields.

The bottom of Directions.scala has an example of a MapGraph for Doug’s routes to two excellent falafel establishments–East Side Pockets in Providence and Oasis in Brooklyn.

We’d like you to write 4 functions, each of which takes a MapGraph and uses either breadth-first search or Dijkstra’s algorithm.

walkable

The walkable function takes in a MapGraph and two locations and returns a Boolean. It should return true if it’s possible to get between the locations via “walk” edges, and false otherwise. You should implement this function using breadth-first search.

reachableForFree

The reachableForFree function takes in a MapGraph and a location and returns a list of all of the locations that are reachable via only 0-cost edges. The order of this list does not matter. You should implement this function using breadth-first search.

minCost

The minCost function takes in a MapGraph and two locations and returns the minimum cost of getting between those two locations. You should implement this function using Dijkstra’s algorithm, with the following modification.

Priority queues

In class, we implemented Dijkstra’s algorithm using a set of nodes we planned on visiting. This had the drawback that each time we decided which node to visit next, we had to look at the whole set in order to find the node with the smallest cost.

A priority queue is a data type that tracks a collection of elements, each of which is associated with a particular priority. It supports operations to insert an element with a given priority (or update the priority of an element that’s already in the collection) and to remove and return the element with the lowest priority. These operations can be implemented efficiently–that is, in such a way that we can avoid scanning the whole collection to find the element with the lowest priority.

We have provided a priority queue implementation in PriorityQueue.scala. You will need the following operations:

  • You can create an empty priority queue like this: val queue: PriorityQueue[String] = new PriorityQueue()
  • You can insert a location into the priority queue, or update the cost of a node that is already in the queue, like this: queue.insert(node, priority)
  • You can get the node with the lowest priority like this: val node = queue.removeMin(). This also removes the node from the queue.

You should use a priority queue in place of the visit set from class. You should call queue.insert whenever you update the cost of a node (i.e., when you’re either encountering a node for the first time or are updating its cost because you have found a better path).

For more examples of priority queue usage, see the test suite in src/test/scala/PriorityQueueSuite.scala. If you’re interested in how it’s implemented, you can read about binary heaps here.

minTime

The minTime function takes in a MapGraph and two locations and returns the minimum time that it takes to get between those two locations. This function should be very similar to minCost!

Testing

You should write tests for all of your functions in DirectionsSuite.scala. As always, you should write enough tests so that you are confident that your functions are correct!

README

In your README.txt, please include answers to the following questions:

  • Did you discuss this assignment with any other students? Please list their cs logins.
  • How many late days are you using on this assignment?