Also upload file to directory on igor. (Name to be give out in class.)
Deadline: Friday 1 April 2011. 4pm.
Study The London Underground Map. Given
type string == list(char); type station==string; type line==string; type tube == list(station X station X line);for representing the tube map. For example:
m:tube; m <= [("kings cross","caledonian road","picadilly"),("kings cross","angel","northern"), ("kings cross","russell square","picadilly")];
Throughout this exercise, assume that there is at most one line directly connecting every two stations. So, for example since king's cross and caledonian road are directly connected by the picadilly line they cannot be directly connected by any other line.
Write the following functions which evaluate:
stationsOfMap:tube -> set(station);The set of stations on the map.
stationsOfMap(nil) <= stationsOfMap((x,y,z)::m) <=
stationsOfLine:line X tube -> set(station);The set of stations on a line on the map.
stationsOfLine(s,nil) <= stationsOfLine(s,(x,y,z)::m) <=
linesOfStation:station X tube -> set(line);The set of lines a station is on.
graphOfMap: tube -> graph(station);the graph of all the stations, throwing away information about which lines the stations are on.
nextStationsOfStation:station X tube -> set(station);The set of next stations to a station.
cfpfor finding the set of all cycle free paths in a graph.
use set; use moresetops; type graph(alpha) == set(alpha X alpha); nexts: alpha X graph(alpha) -> set(alpha); nexts(x,g) <= if g=empty then empty else let ((a,y),g1) == choose(g) in if a=x then y & nexts(x,g1) else nexts(x,g1); allEndingWithOut:alpha X graph(alpha) -> graph(alpha); allEndingWithOut(x,g) <= if g=empty then empty else let ((a,y),g1) == choose(g) in if y=x then allEndingWithOut(x,g1) else (a,y) & allEndingWithOut(x,g1); cfp: graph(alpha) -> alpha -> set(list(alpha)); cfp g x <= let g1 == allEndingWithOut(x,g) in let n == nexts(x,g1) in [x] & mapset( lambda y => (x::y) & empty, mapset(cfp g1 ,n ));Try it out on some graphs.
cfp or otherwise write a function
shortestRoutes: tube X station X station -> set(list(station));for finding the set of shortest routes between two stations.
linesConnecting: tube X station X station -> set(line);which finds the set of lines which directly connect two stations. (if the stations are not directly connected in the tube map (i.e. one stop apart), this function should return
emptyotherwise it should return a set containing a single line.
numberOfchanges: tube X list(station) -> num;;Which counts the number of times a traveller would have to change on a route of directly connected stations represented by a
cfpor otherwise write a function:
bestRoute: tube X station X station -> set(list(station));for finding the set of routes between stations which have the minimum number of changes.
To do this you could define new types:
type dstation == station X boolean; ! true means disabled access type disabledTupe == list(dstation X dtstation X line);and
disabledRoutes: disabledTube X station X station -> set(list(station));
alternatively you could assume a function:
hasAccess: station -> boolean;
and then your main function will be of type:
disabledRoutes: (station -> boolean) X station X station -> set(list(station));