8 Assignment

Please hand in one print out of a text file containing all the solutions you have attempted. Your code should be well laid out and have comments.

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:

1. stationsOfMap:tube -> set(station); The set of stations on the map.

   Hint:

   stationsOfMap(nil) <=
   stationsOfMap((x,y,z)::m) <=
   

2. stationsOfLine:line X tube -> set(station); The set of stations on a line on the map.

   Hint:

   stationsOfLine(s,nil) <=
   stationsOfLine(s,(x,y,z)::m) <=
   

3. linesOfStation:station X tube -> set(line); The set of lines a station is on.
4. graphOfMap: tube -> graph(station); the graph of all the stations, throwing away information about which lines the stations are on.
5. nextStationsOfStation:station X tube -> set(station); The set of next stations to a station.
6. Here is a function cfp for 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.

   Using 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.

7. Write a function:

   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 empty otherwise it should return a set containing a single line.

8. Write a function:

   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 list(station).

9. Using cfp or 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.

10. Add information to your system about which stations have disabled access write a function which finds all routes between stations where the changes (if any) are at points with disabled access.

    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));