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 LocPath 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 LocPath types are defined as follows:

data Loc:

| loc(name :: String,

latitude :: Number,

longitude :: Number,

neighbors :: List<String>,

distances :: List<Number>)

end

data LocPath:

| root(site :: Loc)

| loc-path(site :: Loc, dist :: Number, prev :: String)

end

All instances of loc-path 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 Set<LocPath>You are welcome to work with lists within your program and convert the output to a set at the end. You may assume that converting a list to a set runs in \(O([m \rightarrow m])\) time, where \(m\) is the number of elements in the list. 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 LocPath 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)) -> Set<LocPath>:

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. You may also assume that any graph representation of map data will be undirected and connected.

It is important to note that your implementation of this function will not use the latitude or longitude stored in the Loc. The algorithm should calculate the shortest path based solely on the distances list.

2 Campus Tour

In addition to finding the shortest path between points, extend your program 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. At the same time, regardless of how many times it appears in the list, is it also possible to visit a stop more than once if necessary.

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. Furthermore, it should move towards the closest unvisited stop using the shortest path possible.

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 actual map data for Brown’s campus. You are welcome to play with the Brown 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.

The support code has more than just the data. 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. See an example in the template file for proper usage.

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>

A list of tours supplied by the Admissions Office for use in Tour Guide.

4 Testing

For implementations of Dijkstra’s algorithm, we will use the distances part of the data definition of Loc. For your test cases, do not worry about making latitude and longitude absolutely precise. Just have good test coverage of different values for distances. Look up the “within” predicates for testing in the documentation. While your implementation should not use brown-loc-list or brown-tours, they may be helpful for testing as well as exploration.

5 Analysis

6 Built-Ins

7 Template Files

Early Tests

Implementation

Final Tests

8 Handing In

Early Tests

Final