| Sample | Sample Final Exam | COMP2521 |
In the q3 directory is an implementation of a simple non-directed and non-weighted Graph ADT, along with a main program to test it. The ADT contains functions to create, build, remove and display graphs. Graphs are represented using an adjacency matrix, and each edge appears twice in the matrix (both (v,w) and (w,v)). Vertices are simply integer values in the range 0..N-1, where N is the number of vertices.
When graphs are used to represent networks such as the Web, it is often important to know which vertices are connected to many other vertices. We will call such vertices "well-connected". In our context (of quite small graphs), a vertex is well-connected if it has edges to at least two other vertices.
The Graph ADT contains an incomplete function to generate an ordered sequence of well-connected vertices in a graph:
Connects *wellConnected(Graph g, int *n)
Your task for this question is to complete the implementation of the wellConnected() function. This function takes a graph and a pointer n to an integer variable, computes a sequence of well-connected vertices, and sets *n to a count of the number of well-connected vertices. The sequence consists of pairs (vertex,#conns), where #conns is a count of the edges incident on the vertex. The sequence is arranged in descending of the #conns values; where multiple vertices have the same #conns, the pairs are arranged in ascending order of the vertices. The pairs are implemented as an array of Connects structures; Connects is defined in Graph.h. You can see examples of what these sequences look like in the expected output files under the tests directory.
The main() function (in main.c), builds a graph, then displays details of the graph, and then computes and displays the sequence of well-connected vertices. The graph data is read from the X.in files in the tests directory. If you want a better idea of what the wellConnected() function produces, look at how its results are used in the main() function. Note that, as supplied, the wellConnected() function always says that there are zero well-connected vertices and the main program prints an appropriate message based on this.
The q3 directory itself contains the following:
You compile and test the q3 program using the following commands:
$ make q3 # build the q3 program $ check q3 # apply the tests in the tests directory to the q3 program
You can find out more about the behaviour of the q3 program by looking at the files in the tests directory. The files named tX are test scripts. Each test script has a corresponding file tX.exp which contains the expected output from running that test. If you want to run the tests individually, use commands like:
$ sh tests/t1
You can add debugging code to main.c or Graph.c but make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all of the tests. You can add any auxiliary functions to Graph.c that you think are necessary.
Once you are satisfied with your program, submit it using the command:
$ submit q3
This will make a copy of the Graph.c file from the q3 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. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using inputs which are different to the examples in the q3/tests directory.