CPSC 349 Assignment IO Specifications

General Specs

    Input
    1. There will be one input file per graph; the same file will be used for both part A and part B.
    2. The input file will consist of a graph specification, followed by "?" on a line by itself, then a series of city pairs, followed by "?" on a line by itself.
    3. The graph specification will consist of a sequence of weighted edges, each on a separate line. A weighted edge will be specified by its two endpoint cities, separated by a space, followed by another space, then an integer from 0 to 99, inclusive, indicating the weight (length) of the edge. City names will not contain spaces, or any character other than [a-z] or [A-Z].
    4. There will be at most one edge directly connecting any two cities.
    5. The city pairs following the first "?" delimiter are to be used as start and end points for the shortest path you are to find in part A. Each pair of cities will appear on a separate line.
    Output
    1. For each shortest path you find in part A, you are to print the sequence of cities reached by following the path you have found, separated by a space. Each path should be printed on a separate line.
    2. After the last (end) city in the path, print a space followed by an integer indicating the length of the path you have found.
    3. If the start and end cities are the same, its name need only by printed once.
    4. If there is no path between the start and end city, print an error message on a separate line that contains the text "error"*, then progress to the next pair of cities.
    5. The minimum spanning tree you find in part B will consist of an unweighted graph specification. This will consist of a set of edges that look the same as the input, except that they contain no edge weights.
    6. The edges may appear in any order, and an edge from A to B, may appear as either "A B" or "B A".
    7. If there is no minimum spanning tree (i.e.: the graph provided is not connected), then print "no spanning tree possible" and terminate the program.
    8. If there is more than one minimum spanning tree in part B, or more than one shortest path between any pair of cities in part A, you only need specify one of them.
    9. If the graph contains an error (i.e.: it does not meet the specification provided above), then print an error message containing the text "error"* and terminate the program. This applies to both part A and part B.

Examples

    1. Alberta
    Students in my sections should recognize this as the same example I have drawn on the board a number of times.
    Input file: input1.txt
    Graph:
    Output file for part A: output1A.txt
    Output file for part B: output1B.txt

    2. Australia
    An example of a non-connected graph.
    Input file: input2.txt
    Graph:
    Output file for part A: output2A.txt
    Output file for part B: output2B.txt

Format Checker

    To check that your programs display output in the correct format before you submit them, please use this utility.


* Note that the "error:" text may also read "Program error:" as displayed by hugs when you use the "error" directive. If you are using GHC(i), this will read "a.out:" (or whatever the name of your executable is) instead of "Program error:"—this is also fine. Note this is useful if the entire graph contains an error and you are aborting the program. This is NOT useful if you are reporting no path from one city to another; to get full marks, you should be able to progress to the next pair of cities. Find some better way to handle this case.

<-- Back to the main CPSC349 page