Tour Guide
1 Dijkstra’s Algorithm
2 Tour Guide (Extra credit)
3 Importing Data
4 Analysis
5 Template Files
6 Handing In
6.1 Initial Test Sweep
6.2 Implementation and Final Tests

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 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) -> 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 Tour Guide (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.

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 tour-guide(tours-list :: List<Tour>,

               start-lat :: Number,

               start-lon :: Number) -> List<String>:

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

tour-guide 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 tour-guide 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, which you can import with

import shared-gdrive("mapdata.arr", "0ByoU3bgU-7hUc2doS0Ftc1dUOGs") as mapdata

contains the following definitions and helper functions:

loc-list :: List<Loc>

represents all of the locations on the Brown campus map that your program will be processing.

tours :: List<Tour>

supplied by the Admissions Office.

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

             latB :: Number, lonB :: Number)

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

fun get-loc(name :: String) -> Loc:

returns the Loc in loc-list with the given name. This is the only way to access a node in the graph as a Loc.

Notice that get-loc only searches the large graph, so if you have tests for a smaller graph, you will have to write your own version of get-loc. See the test sweep file for an example.

4 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 tour-guide function. Show your work, as always!

  3. [If you do the extra credit portion] As is, your tour-guide 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.

5 Template Files

Initial Tests

Implementation (with tests)

6 Handing In

6.1 Initial Test Sweep

As with previous assignments, you will submit an initial test sweep. This is due 11:59 PM, Wednesday, November 26th.

Note that we don’t expect tests for the extra credit tour-guide function in your sweep, but if you decide to implement tour-guide, it would be wise to write sweep-style tests for your own sake. Remember the design recipe!

If you decide to opt-in for the test review, please complete your reviews no later than 11:59 PM, Saturday, November 29th. Again, the review will not include tour-guide.

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

6.2 Implementation and Final Tests

Like the last assignment, you will not be submitting a seperate test file. Again, this does not mean that you will not be graded on your tests!

To submit, return to the Captain Teach assignments page:

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

and click “Next Step” again. This time, upload a zip file containing both your implementation, named tour-guide.arr, and your analysis.