Question 2 (10 marks)

In the q2 directory, you will find the following files/directories:

• hasPath.c: the only file you need to modify and submit. You will also find the supporing header file hasPath.h
• autotest: simple auto testing script, important:
  • This script only tests simple cases, you need to extensively test your program for a wide range of test cases.
  • It is possible that this script may not be able to properly handle your program. You need to manually test your program (if required, without autotest script) in order to make sure that it satisfies the requirements.
• Graph.h and Graph.o: an implementation of a simple Graph ADT, similar to (but not the same as) the one you used in your lab exercises. Please open and read Graph.h for the available functions for this question. Please note that Graph.c is NOT available for this exam.
• testHasPath.c: the program to test your function.The program reads graph data (and other inpt data) from stdin, calls the function you implement hasPath, and outputs the answer to stdout. You must carefully study how your function is tested by testHasPath.c. You can find out more about the behaviour of the testHasPath program by looking at the files testHasPath.c, autotest and the files in the tests directory. The files named tX.in are input files for the test program testHasPath and the corresponding expected output are in tX.exp.
• Makefile: to build the required files.
• tests: the directory containing input (*.in) and expected output (*.exp) files for few simple test cases.

Your task for this question is to implement the function int hasPath(Graph g, int s, int d) in the file hasPath.c. The function hasPath takes three arguments: a graph g, source node s and destination node d. The function returns 1 if there a path from s to d, returns 0 otherwise.

int hasPath(Graph g, int s, int d);

You can compile and test your function using the following commands:

$ make    # builds the required program testHasPath
$ ./autotest  # apply all the tests in the tests directory to the program testHasPath
$ ./autotest <test-number>   # apply only one given test case from the tests directory to the program testHasPath

You can find out more about the behaviour of the testHasPath program by looking at the files testHasPath.c, autotest and the files in the tests directory. The files named tX.in are input files for the test program testHasPath and the corresponding expected output are in tX.exp.

If you want to run say test case 2, use the following command:

$ ./autotest 2  

If you want to run all the sample test cases provided, use the following command:

$ ./autotest   

After you run the tests, additional files will appear in the tests directory: tX.out contains the output (from your function) of running test tX.

IMPORTANT: You can add debugging code to hasPath.c or testHasPath.c if you want, however, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests. You can also add any auxiliary functions to hasPath.c that you think are necessary.

Once you are satisfied with your program, submit it using the command:

$ submit q2

This will make a copy of the hasPath.c file from the q2 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that your final submission compiles without any errors or warnings.

Testing:

If you guess a possible answer/output and pass a test, you will not be awarded marks. Your program must properly solve the task discussed above.

$ re-start <question-dir>

$ re-start q2