e. (6 marks) Hence write the following Java method in class GraphApplic as a modification of...

Transcribed Image Text:

e. (6 marks) Hence write the following Java method in class GraphApplic as a modification of a breadth- first traversal, to add up all the distances from source vertex v to every other vertex within a single connected component. public Integer sumDistances (Integer v) { // PRE: v is the id of a vertex in the graph; distances have been calculated from v using calcDistances () // POST: Sums all distances from v to every other vertex in a connected component } In the graph above, sumDistances (100) would return 9; the table below shows the indi- vidual distances. vertex u vertex v distance d(u, v) 100 100 100 100 100 (total) 60 A As A; Page 11 2 public Boolean moreCentral (Integer v, Integer u) { // PRE: v, u are the ids of vertices in the graph 2 3 9 Include the code for the whole function in your submission. f. (4 marks) A vertex v is considered MORE CENTRAL to a graph than a vertex u if the sum of all distances from v to every other vertex is smaller than the sum of all distances from u to every other vertex. Using any functions defined above, write the following Java method in class GraphApplic. // POST: Returns True if v is more central than u, False otherwise } Note that the method will return false if u and have the same sums of distances. In the graph above, vertex 100 is more central than vertex A, as the sum of all distances for the former is 9, and for the latter is 13. SECTION B (3 QUESTIONS, 86 MARKS) Question 6. [32 marks in total] For this question, assume the definition of Java graph classes used in lectures and given in the Appendix. You may make use of any functions given in these classes. 100 60 A A As } 40 A A A3 A a. (4 marks) Consider the undirected graph above. Replace the vertices labelled A. Ag according to the UNIQUESINGLEDIGIT representation of your own student number, as described above in Question 1. Then give the adjacency list representation for the graph. Page 10 vertex u vertex v 40 40 As b. (8 marks) Consider the undirected graph you obtained from replacing A... As with numbers in a. above. Give the breadth-first traversal of the connected component containing vertex 40, starting from vertex 40. At any vertex where there is a choice of edge you should choose the next vertex to be visited based on ascending order. 50 c. (3 marks) Define the DISTANCE d(u, v) between two vertices u and in a graph as being the minimal number of edges between them. The distance from a vertex to itself is 0; if the graph is not connected, and there is no path between the vertices u and v, the distance is 0. In the example graph above, the following are some example distances. 40 50 70 70 A A7 70 distance d(u, v) 0 1 3 A7 2 What is the distance from vertex 40 to vertex 70? d. (7 marks) Write the following Java method in class GraphApplic as a modification of a breadth- first traversal, to label each vertex with its distance from source vertex v within a single connected component. You can assume that the Vertex class contains an attribute dist for storing this value, and methods set Dist() and getDist() for accessing it. Include the code for the whole function in your submission. public void calcDistances (Integer v) { // PRE: v is the id of a vertex in the graph // POST: Calculates and stores distance between v, all other vertices // in a connected component; distances are stored in each vertex e. (6 marks) Hence write the following Java method in class GraphApplic as a modification of a breadth- first traversal, to add up all the distances from source vertex v to every other vertex within a single connected component. public Integer sumDistances (Integer v) { // PRE: v is the id of a vertex in the graph; distances have been calculated from v using calcDistances () // POST: Sums all distances from v to every other vertex in a connected component } In the graph above, sumDistances (100) would return 9; the table below shows the indi- vidual distances. vertex u vertex v distance d(u, v) 100 100 100 100 100 (total) 60 A As A; Page 11 2 public Boolean moreCentral (Integer v, Integer u) { // PRE: v, u are the ids of vertices in the graph 2 3 9 Include the code for the whole function in your submission. f. (4 marks) A vertex v is considered MORE CENTRAL to a graph than a vertex u if the sum of all distances from v to every other vertex is smaller than the sum of all distances from u to every other vertex. Using any functions defined above, write the following Java method in class GraphApplic. // POST: Returns True if v is more central than u, False otherwise } Note that the method will return false if u and have the same sums of distances. In the graph above, vertex 100 is more central than vertex A, as the sum of all distances for the former is 9, and for the latter is 13. SECTION B (3 QUESTIONS, 86 MARKS) Question 6. [32 marks in total] For this question, assume the definition of Java graph classes used in lectures and given in the Appendix. You may make use of any functions given in these classes. 100 60 A A As } 40 A A A3 A a. (4 marks) Consider the undirected graph above. Replace the vertices labelled A. Ag according to the UNIQUESINGLEDIGIT representation of your own student number, as described above in Question 1. Then give the adjacency list representation for the graph. Page 10 vertex u vertex v 40 40 As b. (8 marks) Consider the undirected graph you obtained from replacing A... As with numbers in a. above. Give the breadth-first traversal of the connected component containing vertex 40, starting from vertex 40. At any vertex where there is a choice of edge you should choose the next vertex to be visited based on ascending order. 50 c. (3 marks) Define the DISTANCE d(u, v) between two vertices u and in a graph as being the minimal number of edges between them. The distance from a vertex to itself is 0; if the graph is not connected, and there is no path between the vertices u and v, the distance is 0. In the example graph above, the following are some example distances. 40 50 70 70 A A7 70 distance d(u, v) 0 1 3 A7 2 What is the distance from vertex 40 to vertex 70? d. (7 marks) Write the following Java method in class GraphApplic as a modification of a breadth- first traversal, to label each vertex with its distance from source vertex v within a single connected component. You can assume that the Vertex class contains an attribute dist for storing this value, and methods set Dist() and getDist() for accessing it. Include the code for the whole function in your submission. public void calcDistances (Integer v) { // PRE: v is the id of a vertex in the graph // POST: Calculates and stores distance between v, all other vertices // in a connected component; distances are stored in each vertex

Answer rating: 100% (QA)

Heres the modified code for the sumDistances method and the moreCentral method in the GraphApplic cl... View the full answer