Laboratory

Objectives

to manipulate a Graph ADT using adjacency lists
to start thinking about data structures for assignment 2

Assessment

Deadline: 6 January 2019, 23:59:59
Marks: 3
Submission: give cs2521 lab04

Part 1 should be done individually. Part 2 should be done with your assignment partner.

Setting up

Create a directory for this lab, change into it, and retrieve the files with the fetch command:

2521 fetch lab04

This will have provided you with several files (as you may have guessed by its output). For part 1:

heap_min_ordered.h: Exercise 1, part 1. Do not change this file.
heap_min_ordered.c: Exercise 1, part 1.
test_heap_min_ordered.c: Some simple tests.
heap_min.h: Exercise 1, part 2. Do not change this file.
heap_min.c: Exercise 1, part 2.
test_heap_min.c: Some simple tests.

And for part 2:

places.h: Places “ADT” interface.
places.c: Places “ADT” implementation.
map.h: Map ADT interface.
map.c: Map ADT implementation.
pl.c: Check the Places ADT is working.
euro.c: Print the map of Europe.
conn.c: Simple user for connections.

And a Makefile.

Download all the files.

The provided code contains tags marking unused variables. You should remove these tags as you implement those functions.

Exercise 1: Heap-y Days (1 mark)

This is to be done individually.

(These are two simple questions from past exams. You’ll find them indicative of the nature of the prac exam.)

Write a function heap_min_ordered_p, in the file heap_min_ordered.c, that decides whether a tree-based structure is in min-heap order. In other words: whether it is in heap order, where smaller items have a higher priority. For this question you do not need to check that the tree is complete. Write some tests to check your function.
Write a function heap_min_p, in the file heap_min.c, that decides whether a given array-based heap is in min-heap order. You must assume we have an array-based implementation where the array at index 0 is unused, and that the items in the ‘heap’ begin at index 1.

Exercise 2: The Map of the Fury of Dracula (2 marks)

This is to be done with your assignment 2 partner. (Don’t have one? Find one now!)

A major part of assignment 2 involves moving around Victorian Europe. For the lab this week, we are using one possible representation of the map of Europe, similar to that which will be used in the assignment. The lab represents the map as a graph using an adjacency list representation. The vertices in this graph are places (cities, castles, hospitals and seas), and each is identified by a unique integer value (a location ID). Each vertex is a node containing the location ID, the name of the place (both in full and using a two character abbreviation), and the type of place (LAND or SEA). The edges in the graph are labelled with the kind of transport (ROAD, RAIL, or BOAT) that exists between the places at either end of the edge. Edges are non-directional, and each edge is stored twice (the edge $(v,w)$ is stored in the adjacency lists for $v$ and $w$ ). The supplied graph contains (I hope)[] all of the road, rail and sea connections that appear on the maps of Europe that have been provided for the assignment.

Note that the graph representation we have provided for the lab is only one possibility. You must use this representation for the lab, but you are free to use a different representation in the assignment. This representation is just to get you started, to get you thinking, and also to practice using adjacency lists.

The places.* and map.* files are similar to the ones that will be supplied for The View phase of the assignment. Read these files carefully, to make sure that you understand the interfaces to, and existing implementations of, these ADTs.

For example, the Places ADT defines a number of helper types: LocationID (a unique location ID), PlaceType (whether a place is on land or is a body of water), TransportID (modes of transport between places). It also defines a set of values for each of these types.

For this lab, you will be required to add code to complete the function connections() in map.c. The three programs (pl.c, euro.c and conn.c) are supplied as test-beds for the function that you need to write, and you don’t need to modify these programs. However, it would be useful to read them find out how they invoke the connections() and how they use the function return values.

In our map, we know the following information about each place:

its location ID (a number in the range 0 .. NUM_PLACES-1)
its full name (e.g. “London”, “North Sea” or “Castle Dracula”)
its two-character abbreviation (e.g. “LO”, “NS”, “CD”)
whether it’s located on the land or is a body of water

Places are uniquely identified by their LocationID, and place information is stored in a private array of place structures called PLACES. Users of this ADT do not know about the internal structure of this array; they access information about places via some interface functions:

idToName(int) takes a location ID and returns the place’s full name</li>
idToType(int) takes a location ID and returns the place’s location (LAND or SEA</li>
nameToID(char *) takes a place’s name and returns its location ID</li>
abbrevToID(char *) takes a place’s two-char abbreviation and returns its location ID</tt>

The functions that take a location ID as parameter, check whether the ID is valid and fail an assert if it’s not. The functions that take strings as parameters return a special location ID NOWHERE if the string is not the name or abbreviation of any known place. Strings are matched in a case-sensitive manner: "london" would not be the same as "London".

The program pl (from pl.c) is a test bed for the functions that extract information from the Places table. Some example of how the pl program might be used:

# if the argument is a full place name, it prints the ID
./pl London
London has ID 39
./pl Zagreb
Zagreb has ID 69
# if the argument is an abbreviation, it prints the full name and ID
./pl LO
LO is London (39)
# the quotes are necessary if using names which contain spaces
./pl "North Sea"
North Sea has ID 48
./pl "Castle Dracula"
Castle Dracula has ID 17
# if you don't use quotes, ./pl only sees the first word
./pl Castle Dracula
Invalid place 'Castle'
# using a valid abbreviation
./pl CD
CD is Castle Dracula (17)
# using an invalid abbreviation
./pl XX
Invalid place 'XX'
# using an invalid place name
./pl Hello
Invalid place 'Hello'
# remember that name matching is case-sensitive
./pl london
Invalid place 'london'

In the Map, edges are non-directional and labelled. When the addLink() function in Map.c adds an edge from A to B with transport type T, it also adds an edge from B to A with type T. This reflects the fact that if there is a road from Rome to Florence, then there is also a road from Florence to Rome. Also, you can have multiple edges between a given pair of places if they are labelled with different transport types. This reflects the fact that there may be be both a road and rail link between two cities (e.g. Rome and Florence).

The euro program (from euro.c) displays the links in the Map, although admittedly not in a particularly attractive format. You can use it to check the output from the conn program.

When you come to implement your AIs for the “Fury of Dracula”, you will need functions to answer questions such as “How can I get to X from my current position?”, “What is the quickest way to go from A to B?”, etc. In this lab, you are to implement one simple function of this type which tells you what are the links (if any) between two places.

The function:

int connections (
	Map map,
	LocationID start, LocationID end,
	TransportID ways[]);

uses the Map to work out all of the different types of transport that exist as direct connections between the two specified locations, as well as any sea connections that you could use to move from one to the other. It sets one value in the ways[] array for each connection, and returns the number of connections found (and placed in the array). Naturally, it first checks the validity of its parameters (and fails asserts if they’re not valid).

Notes:

a sea connection involves moving onto the sea, and then moving to the destination; it has connection type BOAT
sea connections (from one port city to another on the same sea) are unusual in that they involve two graph edges: all other connections in this exercise involve a single edge
you are required to find direct edges between the two locations, and also to determine whether the locations are both port cities on the same sea (and count that as a sea connection of type BOAT)
the ways[] array is supplied by the caller, who must allocate sufficient space

Clearly, the maximum number of edges that can exist between two places is determined by the number of transportation types.

Once you have implemented the connections() function, you can test it using the conn program, which takes the names (or abbreviations) of two places and displays a list of all the connections between them. It gets the list by calling the connections() function. Some examples on how to test your connections() function using the conn program are below. Make sure that you conduct more extensive tests than just these (your tutor will ask to see your tests).

# both road and rail ... order doesn't matter
./conn London Manchester
Between London and Manchester ...
Rail connection
Road connection
# only way to get into the Channel from London is by boat
./conn London "English Channel"
Between London and English Channel ...
Boat connection
# from London to rest of Europe is typically via Le Havre
./conn "Le Havre" "English Channel"
Between Le Havre and English Channel ...
Boat connection
# direct road connection but no direct rail
 ./conn Leipzig Hamburg
Between Leipzig and Hamburg ...
Road connection
# direct rail connection but no direct road
./conn Paris Marseilles
Between Paris and Marseilles ...
Rail connection
# port cities are connected to their sea by boat
./conn Marseilles "Mediterranean Sea"
Between Marseilles and Mediterranean Sea ...
Boat connection
# two cities with all three connections
./conn Rome Naples
Between Rome and Naples ...
Rail connection
Road connection
Boat connection
# direct connection between two seas must be by boat
./conn "Black Sea" "Ionian Sea"
Between Black Sea and Ionian Sea ...
Boat connection
# no direct rail/road/sea connection between Munich and Berlin
./conn Munich Berlin
Between Munich and Berlin ...
No direct connection
# no direct connection between London and Castle Dracula ... probably a good thing
./conn London "Castle Dracula"
Between London and Castle Dracula ...
No direct connection

While implementing the above function, you are free to introduce any auxiliary functions that you think are useful. However, these should all be declared static because they are not visible outside the ADTs.

Submitting

You must get the lab marked by your tutor in your lab.

Submit your work with the give command, like so:

give cs2521 lab04 heap_min_ordered.c heap_min.c map.c

Or, if you are working from home, upload the relevant file(s) to the lab04 activity on WebCMS3 or on Give Online.