On this page:
1 Dijkstra’s Algorithm
2 Campus Tour (Extra Credit)
3 Importing Data
4 Testing
5 Analysis
6 Built-Ins
7 Template Files
8 Handing In

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 Set<DLoc>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 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)) -> Set<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. 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.

Tours will be represented by the Tour type. A Tour stores the name of a tour and a list of its stops’ names:

data Tour:

  | tour(name :: String, stops :: List<String>)

end

The Admissions Office wants a program that provides the following tour-calculating function:

fun campus-tour(tours-list :: List<Tour>,

                start-lat :: Number,

                start-lon :: Number,

                get-loc :: (String -> Loc)) -> List<String>:

where the output is a list of strings indicating the names of each stop on the calculated tour.

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.

5 Analysis

You should also hand in an analysis document addressing the following questions:
  1. Analyze the worst-case running time of your dijkstra function. Show your work, as always!

  2. [If you do the extra credit portion] Analyze the worst-case running time of your campus-tour function. Show your work, as always!

  3. [If you do the extra credit portion] As is, your campus-tour always visits nearest unvisited selected stop. Is this optimal? That is, does this algorithm create the shortest path visiting all the selected tour stops? If so, explain why this is true. If not, provide a counter-example.

Provide your analysis in terms of the size of the graph.

6 Built-Ins

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

7 Template Files

Implementation Code

Final Tests

8 Handing In

To submit, return to the Captain Teach assignments page:

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