Tour Guide

No doubt you remember the campus tour—the walking backwards, the explanation of meal plans, the intramural sports speech.... It’s a fine tradition, but the admissions department is running out of willing volunteers. That’s where you come in: you’ve been asked to write a program to calculate tours for campus visitors.

1 Dijkstra’s Algorithm

The map data you receive will contain many sites that are not tour stops, such as intersections and intermediate landmarks. All map sites, together with the paths between them, form a graph. To go from one tour stop to another, your program should be able to find the shortest path from any point in this graph to every other point in the graph.

In this assignment you will implement Dijkstra’s algorithm using the Loc type to represent points in the map of Brown’s campus. A Loc includes its name and location, as well as its neighbors and the distances in meters to those neighbors. Every location will have a unique, unambiguous name. A DLoc represents the result of a shortest-path search for a point in the graph. It contains the location of the point, the length of the shortest path to that point, and the name of the previous location in that path. The Loc and DLoc types are defined as follows:

data Loc:

| loc(name :: String,

latitude :: Number,

longitude :: Number,

neighbors :: List<String>,

distances :: List<Number>)

end

data DLoc:

| root(site :: Loc)

| dloc(site :: Loc, dist :: Number, prev :: String)

end

All instances of dloc and root are relative to the starting point of a shortest-path search (see below).

Your program should take in a Loc representing the starting point for your path, and get-loc :: (String -> Loc), which is a function to fetch a Loc by name. In other words, get-loc is your way of accessing information from the graph about locations, as is further explained in Importing Data. Your program should return a List<DLoc> indicating the shortest total distance from the starting point to each location on the map of Brown’s Campus, as well as the previous stop in the shortest path to each location. Use the root case of DLoc to represent the starting point of your shortest-path-search. Your implementation of Dijkstra’s algorithm should have the following contract:

fun dijkstra(start :: Loc, get-loc :: (String -> Loc)) -> List<DLoc>:

Your implementation should run in \(O([s \rightarrow s \cdot \log s])\) time, where \(s\) is the number of vertices in the graph. Note that a complete graph (with an edge between every pair of vertices) would have \((s \cdot (s-1))/2\) edges, making this impossible. However, graph representations of real maps are not so densely connected, and you may assume that each vertex has only some constant number of neighbors.

2 Campus Tour (Extra Credit)

In addition to finding the shortest path between points, you may extend your program for extra credit to be able to find a path through lists of predefined “tours”, such as a “Campus Art Tour” or a “Freshman Dorm Tour”. These tours will be supplied by the Admissions Office. Even if a stop appears multiple times in the list, it only needs to be visited once.

These tours have no fixed order. Your program should simply move toward the closest unvisited stop in the provided list of tours, even if this results in tours being interleaved.

campus-tour produces a list of location names to walk through, ordered from first to last (including intermediate sites like street corners), to complete the given tours according to the specifications above. Since the user might not begin their tour standing at a site on the map, your campus-tour should first find the site closest to the starting position, and then continue to the nearest selected tour stop. Remember, you will be computing a single path that visits all stops in all the selected tours. Keep in mind that if you aren’t given any tours or the tours you are given contain no locations, you don’t have to go anywhere, so make sure your output reflects this.

3 Importing Data

The support code for this assignment contains the map data for Brown’s campus, as well as additional support code you need to write Tour Guide. Links to shared copies of the support code have been provided for you.

In addition to the Loc and Tour data types described above, the file mapdata.arr contains the following definitions and helper functions:

fun get-dist(latA :: Number, lonA :: Number,

latB :: Number, lonB :: Number) -> Number

takes the latitude and longitude of two locations, and returns the approximate distance in meters between them.

fun get-loc-maker(loc-list :: List<Loc>) -> (String -> Loc)

takes a List<Loc> and returns a function (which we call get-loc) that can be supplied to dijkstra or campus-tour. We guarantee that this generated function runs in \(O([s \rightarrow 1])\) where \(s\) is the number of vertices in the graph.To create a get-loc with this performance, the support code uses a library named string-dict. This uses hashing, which is described in the textbook. Note, however, that you are not permitted to use string-dict. See an example in the template file for proper usage.

Below are actual map data for Brown’s campus. You are welcome to play around with these data in the REPL and use them in your tests. However, you should not use these data in your implementation because we might use different graphs when grading.

brown-loc-list :: List<Loc>

represents all of the locations on the Brown campus map that your program will be processing. You could supply this list to get-loc-maker to obtain a get-loc function, which may be used as an argument for dijkstra or campus-tour.

brown-tours :: List<Tour>

supplied by the Admissions Office.

4 Analysis

5 Built-Ins

In addition to the allowed functions in the general guidelines, you can also use sets.

6 Template Files

Implementation Code

Final Tests

7 Handing In

To submit, return to the Captain Teach assignments page:

https://www.captain-teach.org/brown-cs019/assignments/