e. (6 marks) Hence write the following Java method in class GraphApplic as a modification of...
Fantastic news! We've Found the answer you've been seeking!
Question:
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
Expert Answer:
Related Book For
Smith and Roberson Business Law
ISBN: 978-0538473637
15th Edition
Authors: Richard A. Mann, Barry S. Roberts
Posted Date:
Students also viewed these programming questions
-
What is visual hierarchy? How would you define visual hierarchy? Why do you have to consider visual hierarchy when you visualize data?
-
What is wrong with this Java code? I am trying to run a java applet with the garden.jpg picture in the background. It runs for me without the background image. import java.applet.Applet; import...
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
In each case, verily that the points P and Q lie on the line. x = 4 - t P(2, 3, -3), Q(-1, 3, -9) y = 3 z = 1 - 2t
-
The formula gives the monthly mortgage payment M on a home loan of P dollars at interest rate r, where n is the total number of payments (12 times the number of years). The cost of a house is...
-
The directors of Helena Beauty Products Ltd have been presented with the following abridged financial statements: Required: Using six ratios, comment on the profitability (three ratios) and...
-
explain the barriers to individual and organizational learning, and
-
Buscemi Products, Inc., desires an after-tax income of $500,000. It has fixed costs of $2,500,000, a unit sales price of $300, and unit variable costs of $150, and is in the 40% tax bracket....
-
8. Use the substitution 1.; = I and 1: = y + 13 to rewrite the following integral in terms of n and 1: and use this to calculate the integral 1 mzs 33:5 dds: [Jigs 20{y+m)e y
-
Arrow Hospitality prepares adjustments monthly and showed the following at September 30, 2023: Additional information available for the month ended September 30, 2023: a. Interest of $162 had accrued...
-
please explain asap thnku. 1. A company specialises in printing advertising leaflets and is in-the-process of preparing its price list. The most popular requirement is for a folded leaflet made from...
-
. Consider a direct-mapped cache design for a byte-addressable memory. The processor accesses 32- bit word from the cache using the following bits of the 32-bit address: Tag Index Offset i). 31-10...
-
Negotiation can be very time consuming; however, most organizations will typically have a certain procedures in place in order to move through the negotiation process. A Model for Negotiating...
-
A Walmart supplier's demand forecasting team estimates that the demand for jeans is on average 600 pairs per month with a standard deviation of 255 pairs. They assume that the demand is distributed...
-
Explain the meaning of these two phrases: "the balance of probabilities" and "beyond a reasonable doubt." In what type of case will each phrase be used? 13/ Describe four different results that an...
-
Question 11 The following figures have been extracted from the financial statements of KND Ltd: Book Value of Current Assets $45 million and Current Liabilities $34.75 million 11% Debentures: $27...
-
! Required information [The following information applies to the questions displayed below.] The bookkeeper at Jefferson Company has not reconciled the bank statement with the Cash account, saying,...
-
Question 2 For an n x n matrix A = form) via (aij)
-
Sims contracted in writing to sell Blake one hundred electric motors at a price of $100 each, freight prepaid to Blakes warehouse. By the contract of sale, Sims expressly warranted that each motor...
-
Jacobs, owner of a farm, entered into a contract with Earl Walker in which Walker agreed to paint the buildings on the farm. As authorized by Jacobs, Walker acquired the paint from Jones with the...
-
Lile, an insurance broker who handled all insurance for Tempo Co., purchased a fire policy from Insurance Company insuring Tempo Co.s factory against fire in the amount of $1.5 million. Before the...
-
In the 2010 Wells Report, what was the third most common way of detecting fraud? a. Tips b. Internal audits c. External audits d. By accident e. Reports from the police
-
According to the 2010 Wells Report, the most costly form of fraud was: a. Asset misappropriations b. Fraudulent disbursements c. Check tampering d. Fraudulent financial statements e. Bribery and...
-
Charles Moon, the managing director of your client Neptune plc, is negotiating with a view to Neptune plc acquiring the entire share capital of Sirius Group Ltd ('Sirius'). He has informed you that...
Study smarter with the SolutionInn App