CSC270 Data Structures and Techniques, Spring 1998

Assignment 2: Graph Representation

Due: Friday February 27 at 4:00 pm.
Worth: 12%

The problem

The purpose of this assignment is to teach you how to represent a
graph in C. It will also help you to get comfortable with pointers,
dynamic allocation and modules in C. You have to maintain information
of roads connecting cities. From time to time, roads are closed or
opened, and we would like to have a program to insert and remove edges
in the graph of cities. In addition, we may receive inquiries about
shortest connection between two cities given the particular situation
of the roads at the time of the inquiry, and about printing the
information in the graph.

You are provided with a `skeleton program' and will have to write code
for the bodies of several functions.  Copy the files to your own
directory:

    % cd
    % cp -r /u/jstewart/270/hwk2 .

                                 ^--- don't forget the period!

Compile and test the skeleton program:

    % make
    ...
    % a2 < testfile

Note that the results make no sense. That is because the code for the
different functions still has to be written in the program. We just
did some dummy assignments in order to test the output; your task is
to provide the correct code for the functions.

Programming

Read and understand the complete program. Implement the functions
findShortestPath, insertEdge, removeEdge, and printRoadMap.  You do
not need to add code outside those functions, but you may do so if you
wish and if you document your additions. In any case, YOU CANNOT
CHANGE THE INPUT/OUTPUT.  Do not change the I/O statements or you'll
lose marks.  Give good comments in your code, including a comment
above each of the functions.

Testing

Test your program with `testfile'.  In addition, test your program
with another test file that you create.  Call your own file `mytests'
and put it in the your hwk2 directory.  Choose tests that make a
thorough checking of your program.  Capture the screen output by
executing

    % a2 < mytests > mytests-output

Handing In

1. Make a hardcopy of the program files that you modified.
2. Make a hardcopy of your `mytests'.  
3. Make a hardcopy of `mytests-output'.  Write in pen on the
   hardcopy, beside each tests, a brief explanation of why the
   test is relevant

Put these into an ENVELOPE.  Tape the cover page (provided below) to
the envelope.  Seal the envelope with a single piece of tape that the
tutors will find easy to remove.

The tutor will compile and run your program.  Make sure that the
following commands work before submitting your program.

    % cd ~/hwk2
    % make clean
    % make
    % a2 < testfile
    % a2 < mytests
   
Your programs must also be submitted electronically by the deadline.
Name your own test file `mytests' and execute exactly these commands:

  % cd
  % cd hwk2
  % make clean
  % submit -N a2 csc270h *

You may, if you wish, also submit a README file that the tutor will
read.  You will lose marks if you don't follow these submission
instructions exactly.

------------------------------------------------------------------------

COVER SHEET FOR ASSIGNMENT 2


    CDF account name:

    Surname:

    Given Name(s):

    Student Number:

    TA's name:

    Tutorial location:

 
I declare that this assignment is my own work and is submitted in
accordance with the University of Toronto Code of Behavior on Academic
Matters, the Code of Student Conduct, and the guidelines for avoiding
plagiarism described in the course syllabus.
 
I discussed this assignment with the following people:





 
Signature

------------------------------------------------------------------------

GRADING
 
Program

        insertEdge                                     / 5
        removeEdge                                     / 5
        createGraph                                    / 5
        findShortestPath                               / 5
        printRoadMap                                   / 5

        Programming style                              / 5

        Tutor's compilation and tests                  / 10

        Coverage, relevance, and explanation
        of your own tests                              / 10
 
                                                ----------- 

Total                                                  / 50