Disaster Emergency

Background

The Office for the Coordination of Humanitarian Affairs (OCHA) oversees coordination of the United Nations disaster-relief programs. There are a number of different agencies, and navigating the maze of relief providers and locations can be time-consuming. Yet time is of the essence when an emergency occurs.

The OCHA would like to develop a simple way of coordinating the provision of relief supplies as quickly as possible during an emergency situation. They feel this can best be done by maintaining a database of all cities and towns in an area, regardless of their administrative affiliation, noting which ones can provide disaster relief and what sort of relief (food, water, blankets, etc.).

The UN has commissioned you to develop software that will locate the relief centre or centres closest to the site of a distaster specified by the user. The specification for the software is below.

Note that the data structures and algorithms are deliberately not specified, as the OCHA does not know anything about algorithms or data structures. You will need to make choices about the most appropriate algorithms and data structures for the task.

Your task

In this assignment, you will develop a prototype for the software described above, according to the specifications below.

The assignment consists of:

• A text file named design.txt, in which you outline the design decisions you have made, including your choice of data structures and algorithms and your reasons for these choices. Your design.txt file shoule also include your thoughts on improving and/or extending the program, e.g. if you are aware of more efficient data structures and/or algorithms that could be used to advantage, but have not implemented them.
• Your program (prototype software) written in C, including a makefile that compiles your program to make an executable called helpme.

It is strongly suggested that you think about your design carefully and start to write your design.txt document before you start coding. A significant number of marks are allocated to appropriate choice of data structures and algorithms. Thinking about these carefully, before you begin to start coding, can save you hours of false starts.

Hint: Remember that you are looking for transport into the disaster location, not from the disaster area. Think carefully about how you want to set up your data structure(s).

See the sections on Design Notes and Assessment for more about space-time tradeoffs and using data structures not taught in this subject.

This assignment is not staged, but if you are looking for simplifications as a way of helping plan the development of your program, see section on Output for suggested partial solutions.

Your program will:

• Read information from a database, a single file whose name is specified as a command line argument to the program. The database contains identifier numbers and names and for all the cities in the network, and specifies their disaster relief capabilities. The travel time to other towns or cities that can be reached directly from a given city is also in the database. See below for the exact format of this file.
• Prompt the user to give the location of the emergency, which is the name of a town or city.
• Prompt the user for the kind of supplies needed, a single code letter code for each kind of item. The code letters are run together in a string, without spaces (details in section on Keyboard Input). If the user does not specify which kind of supplies they need, then the program should inform the user about the closest centre that can supply any kind of assistance. Note that where a few different kinds of supplies are requested, it may be necessary to supply them from a few different centres.
• Output the nearest centre or centres, as appropriate, the expected travel time to the disaster site (for each centre if there is more than one), and the route(s) to be taken, i.e. through which other towns listed in the database the relief transport must transit.

Database (File) Input

The database file is specified by the single command line argument to the program.

The format of the database file is as follows:

• The first line contains a single integer that tells how many records follow in the rest of the file.
• The records occupy the rest of the file, starting from line 2, and are in the following format, one record per line: hCityIDi|hCityNamei|hReliefTypeAvailablei|hTravelTimei Note that the fields are separated by the pipe or vertical bar ’|’ symbol
• CityID is an integer, in the range of 0 to n − 1, where n is the number of cities or towns in the database. Identifiers are unique.
• CityName is a unique string.
• ReliefTypeAvailable denotes the type of assistance available. Each relief type is coded as a single capital letter, and the field has all the codes concatenated, e.g. BFW for blankets, food, water.
• The character codes are chosen from: – B: blankets – F: food – W: water – D: digging equipment – M: medicine – X: no supplies or assistance available from this town Note that the ReliefTypeAvailable field is never empty; if no relief is available, there will be an X in the field. X is incompatible with any other code.
• TravelTime is a comma separated list of hCityID:TravelTimei pairs, representing all towns that are directly reachable from the city determined by CityID, CityName in fields 1 and 2. Note that the city and its travel time from the source city are separated by a colon ‘:’, and that the city-distance pairs are separated by commas. Travel time is expressed in hours, rather than physical distance, because in the areas the OCHA covers different kinds of transportation might be used, e.g. 4-wheel drive, boat, camel, etc. Note that travel times are not necessarily symmetrical, since e.g. it might take longer to go on a river in one direction, or to find a camel at one endpoint, compared with the other. A link in one direction does not necessarily imply a link in another direction, as sometimes political or physical exigencies result in one-way restrictions.
• An example micro-database follows: 6 3|Gao|X|1:36 0|Timbuktu|BM|1:20 2|Taoudenni|X| 4|Bamako|BMFWD|1:10 1|Mopti|X|0:24,3:36,4:10 5|Niamey|WMF|3:48 This small database file specifies that there are 6 records in the following lines, numbered from 0 to 5, not necessarily in order. Taoudenni (city 2) does not have any supplies and is isolated from other cities. Gao also has no supplies but can reach Mopti (city 1) and can be reached from Niamey (city 5). Timbuktu (city 0) can supply blankets (B) and medicine (M), and can reach city 1 (Mopti) in 20 hours. In this database, while travel from Timbuktu to Mopti takes 20 hours, the reverse direction takes 24 hours, because of river currents. Also in this database, it is possible to travel from Niamey (city 5) to Gao (city 3) in 48 hours, but it is not possible to travel in the opposite direction, due to border tensions. Note that it is possible to send things from Bamako (4) to Gao (3) and Timbuktu (0), but only via Mopti (1). A request for water W from Timbuktu, could be fulfilled from Niamey or Bamako, with the shortest travel time being from Bamako (10+24 = 34 hours vs. 48+36+24 = 108 hrs).

For the purposes of this assignment, you can assume that the data are well-formatted, the input file is not empty, city/town ID numbers are unique, and travel times are integers.

Keyboard Input

• Once the user has invoked the helpme program with the name of a valid database file, your program will prompt the user to give the location of the emergency, which is the name of a town or city.
• Once the user has input the name of a town is input, prompt the user to input one or more characters to indicate what kind of resource they require. The characters are chosen (in any order) from the following:
• – B: blankets – F: food – W: water – D: digging equipment – M: medicine The resource characters are input as a string, e.g. BFW, or FBW, or D, etc.

Sample program invocation, prompts, and keyboard input:

./helpme WestAfricaDatabase
> Please enter the location of the disaster:
Gao
>What kinds of supplies do you need?
MF

How would this request be best fulfilled using the micro-database above?

Output

To earn full marks, your program will output, for each of the requested resources:

• the resource (code or name),
• the closest centre (name and ID),
• the expected time is will take to receive the supplies,
• the route the supplies will take, through which cities (ID and name).

For example, in response to a disaster in Medellin, and a request for blankets and food, the desired output might be:

B 203 Cebu 10 hrs
203 Cebu
107 Danao
207 Bogo
17 Medellin

F 407 Argao 16 hrs
407 Argao
513 Carcar
203 Cebu
107 Danao
207 Bogo
17 Medellin

It is not necessary to follow this output format exactly, as long as all the information is there, and in a readable form. The order of the output is not important, as long as it is easily readable.

All output must be written to stdout.

While the data in the database is well-formatted, your program is expected to handle the following situations gracefully:

• The disaster at a place not in the database.
• A disaster in a city that is in the database but not reachable from any of the disaster relief centres in the database.
• Some or all of the requested resources are not available.

Whenever a request cannot be fulfilled, your program should output a message to that effect. Where it is possible to partially fulfill the request, your program should output the partial result, along with a message indicating that this is only a partial fulfillment of the request.

Partial Programs

There are more basic versions of the program that will earn partial marks.

For example, in its most basic form, the program will output only the CityID for the closest centre that can supply relief of any kind, and the expected time of arrival of supplies at the disaster location, e.g.: 203 36 hrs, (to indicate that some type of (unspecified) relief can be received from the centre in city 203, and it is expected to arrive in 10 hours).

A more developed program can will take in the requests for various supplies and output the type of supply, the city number for the centre and travel time, e.g.:

B 203 10 hrs
F 407 16 hrs
W 507 10 hrs
D 507 10 hrs

One possible extension

You are not required to think about saving petrol, i.e. trying to make sure that multiple centres are on the same route whenever possible. However, you may certainly sketch out an approach to this kind of solution in your design.txt file and/or implement a solution that would do this.

You are encouraged to extend the functionality of the program wherever you see the opportunity as long as you document what you are doing and your justification, and as long as the program input interfaces remain as specified. If you wish to make an improvement that involves changing the interfaces, you must discuss this with the lecturer first.

Design Notes

Document your design decisions in a text file named design.txt, which you will submit along with your program files. The design.txt file should record an outline of your program, and should justify your choice of particular data structures and algorithms. Assumptions, limitations, or places where there is room for improvement (and why this would be improvement) should also be in this file.

You should comment on the time and space efficiency of your program, mention any limitations not already mentioned in the code documentation, and suggest feasible extensions to the program.

Note that you may legitimately choose to use multiple data structures and/or extra space in the interests of simplicity or efficiency.

If you did not complete the entire specification, your design notes should indicate clearly what part(s) of the specification you did complete.