Deadline: 11:59pm Tuesday 2nd February 2016
Total Marks: 3
You may do this lab in pairs
Part 5: Chapters 17-18
Change into your lab06 directory and run the following command:
cp /home/cs1927/public_html/16x1/labs/lab07/files/* .
Note the "." at the end of the command, meaning "into the current directory". If you've done the above correctly, you should find the following files now in the directory:
| Makefile | a file to control compilation |
| countries.data | a file containing graph data |
| Graph.h | A graph ADT interface |
| Graph.c | An adjacency matrix implementation of a graph |
| graphClient.c | A graph ADT client program |
Make the files and check that they all compile and see what the program does.
It should be run as such:
./graphClient countries.data
The countries.data file specifies the connectivity of all the vertices of the graph. The data should represent an undirected, unweighted graph. The first line of the data file will indicate the number of vertices in the graph - V. The following V lines represent the edge data for each vertex. Note: Each edge may be represented twice eg 0 1 and 1 0 will exist.
Below the edge data is information about each vertex. Each vertex has a label, this is the name of a country. It also has other information such as the capital of the country and its population. In the supplied graphClient.c program, this extra vertex information is read in from the file, but is NOT actually stored anywhere.
For this task you must:
Store the information about each vertex in the graph. For this you will need to add another function to the graph interface that sets the data for a given vertex in the graph. You must also implement this function. To implement the function you will need to modify the graphRep struct so it can actually store this data. You should then actually call your new function inside the graphClient.c file at the appropriate location.
You should also implement the function
char * getVertexLabel(Graph g, Vertex v);
This should return the name of the country associated with the given vertex.
V=10, E=11 China-USA China-Brazil China-Bangladesh China-Nigeria China-Japan China-Australia China-Austria USA-China USA-Indonesia USA-Bangladesh Indonesia-USA Brazil-China Brazil-Pakistan Brazil-Bangladesh Pakistan-Brazil Bangladesh-China Bangladesh-USA Bangladesh-Brazil Nigeria-China Japan-China Australia-China Austria-China
NOTE: This will be very similar to the showGraph function, with one or two minor modifications.
0: China Beijing 1306313800
Use this function to implement the showData(Graph g) function that prints out vertex information for all vertices in the graph in vertex id order. You should get
0: China Beijing 1306313800 1: USA Washington 295734100 2: Indonesia Jakarta 241973900 3: Brazil Brasilia 186112800 4: Pakistan Islamabad 162419900 5: Bangladesh Dhaka 144319600 6: Nigeria Abuja 128772000 7: Japan Tokyo 127417200 8: Australia Canberra 20090400 9: Austria Vienna 8184700
Make your graphClient program and run it. Now under the TASK1 section you should get output
V=10, E=11 0-1 0-3 0-5 0-6 0-7 0-8 0-9 1-0 1-2 1-5 2-1 3-0 3-4 3-5 4-3 5-0 5-1 5-3 6-0 7-0 8-0 9-0 TASK 1 V=10, E=11 China-USA China-Brazil China-Bangladesh China-Nigeria China-Japan China-Australia China-Austria USA-China USA-Indonesia USA-Bangladesh Indonesia-USA Brazil-China Brazil-Pakistan Brazil-Bangladesh Pakistan-Brazil Bangladesh-China Bangladesh-USA Bangladesh-Brazil Nigeria-China Japan-China Australia-China Austria-China 0: China Beijing 1306313800 1: USA Washington 295734100 2: Indonesia Jakarta 241973900 3: Brazil Brasilia 186112800 4: Pakistan Islamabad 162419900 5: Bangladesh Dhaka 144319600 6: Nigeria Abuja 128772000 7: Japan Tokyo 127417200 8: Australia Canberra 20090400 9: Austria Vienna 8184700
For this task you need to implement the function:
void dfSearch2(Graph g,Vertex * dfsOrdered);and an associated function:
void dfsR2(Graph g,Edge e, Vertex * dfsOrdered);These functions will be the same as dfSearch and dfsR except the dfsR2 will record each vertex in dfsOrdered as it is visited for the first time.
For example: In this graph a dfs would visit nodes in the order
0 1 2 5 3 4 6 7 8 9This should be the content of the dfsOrdered array when the dfSR2 function has completed.
The graph client calls dfSearch2 and then uses the dfsOrdered array to print out the vertexData for the vertices in DFS order.
When this is implemented properly the output for TASK 2 should be
TASK 2 0: China Beijing 1306313800 1: USA Washington 295734100 2: Indonesia Jakarta 241973900 5: Bangladesh Dhaka 144319600 3: Brazil Brasilia 186112800 4: Pakistan Islamabad 162419900 6: Nigeria Abuja 128772000 7: Japan Tokyo 127417200 8: Australia Canberra 20090400 9: Austria Vienna 8184700
In the previous example we print out the nodes is DFS order of when they are discovered. This prints out information for each node exactly once.
However if we wanted to visit the countries in this order by flying only along valid edges, we would need to fly back to certain countries (ie backtrack) at times.
For example if we start at China and do a DFS we would go to the USA then Indonesia. From Indonesia there are no flights other than a flight back to the USA. So we need to back track to the USA. From USA we can visit (or discover) bangladesh etc.
In this task you need to write a function in the client program called:
Edge getNextFlight(Graph g, Vertex * dfsOrdered,int *nDiffCountries ,Vertex currCountry);
This function should return the next edge that corresponds to the next flight in a DFS flight through all the countries given a current location (currCountry).
The input is the graph, the array which contains the order in which vertices were discovered in the dfs. The next input is the st array. This array shows the predecessor of each vertex in the DFS. This is useful for backtracking. The nDiffCountries is a counter that keeps track of how many vertices from the dfsOrdered array have been processed. This variable should be incremented when appropriate.
Once you have successfully completed this function and have uncommented the line in graphClient.c that calls getNextFlight, your output for TASK 3 should look like:
TASK 3 Flying all over the world Flight 1 China USA Flight 2 USA Indonesia Flight 3 Indonesia USA Flight 4 USA Bangladesh Flight 5 Bangladesh Brazil Flight 6 Brazil Pakistan Flight 7 Pakistan Brazil Flight 8 Brazil Bangladesh Flight 9 Bangladesh USA Flight 10 USA China Flight 11 China Nigeria Flight 12 Nigeria China Flight 13 China Japan Flight 14 Japan China Flight 15 China Australia Flight 16 Australia China Flight 17 China AustriaYou should also make sure that you free the st and pre arrays appropriately to avoid memory leaks. You should show your tutor your valgrind output to demonstrate you have done this properly.
1927 classrun 16x1 give lab07 Graph.h Graph_AdjMatrix.c graphClient.c Makefile