Software Dev. & Problem Solving II Graphs & Breadth-First Search Goals of the Assignment Practice using...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Software Dev. & Problem Solving II Graphs & Breadth-First Search Goals of the Assignment Practice using graphs and searches with graphs. This assignment will require the Graph interface and the Vertex and AdjacencyGraph classes implemented during class as well as the implementation of the BFS algorithm. JUnit unit testing is not expected for this assignment. Read this document in its entirety before asking for help from the course staff. The following terminologies will be used in the assignment: Background Let G be a graph, and A and B be two vertices in G. We have learned that BFS can be used to find one of the shortest paths from A to B. We will call such a path a BFS path. distance (A, B) is the number of edges along a BFS path from A to B. distance (A) is the maximum distance of A to any vertices in G. That is distance (A) = max{distance (A, X), for any vertex X in G} A vertex C is called a center of G if distance (C) A Activities 1. Add the following getter to your AdjacencyGraph class. protected Map getVertices() { return vertices; ii. B } 2. Open and examine the provided file named ConcentericGraph.java. a. In the constructor, initialize centers and graph: i. e. H iii. The same vertex may appear on multiple lines in the file. You only add each value to the graph once. iv. If an IOException occurs while trying to read a graph, you may rethrow it. b. Complete the distanceMap (start) method where you compute distance (start, X), for each element X. Create a hash map that maps each element X (String) to distance (start, X), and returns it. You are not allowed to use the bf Path method you wrote in the lecture. Though bf Path can solve this problem easily, using it whenever you compute the distance of each X from start would be very inefficient. Instead, consider using the hash map along with BFS. Your constructor should read files named "connected_*.txt" in the data directory of your repository. Take a moment to examine the text files. Each line represents an adjacency list where the first value is a vertex in the graph, and the remaining values are the vertices to which it is connected. For example, the line "A, B, C" indicates that vertex A is connected to both vertex B and vertex C. Assume that the connections between neighbors are undirected'. c. Complete the distance (start) method where you compute distance (start) and return it. d. Complete the radius () method where you comp and return it. the radius of this graph Now you are ready to complete search Centers () that sets the centers of the graph. If there are multiple centers, you need to filter them to only include the ones that have the most neighbors. There could be still multiple centers of the graph after filtering. f. (10% bonus credit) Override the toString method that returns a concentric view of the graph. Refer to the sample output in the next section. Hint: Use BFS starting from centers to build a string representation. 3. Sample One public static void main(String[] args) throws IOException { ConcentricGraph cGraph = new ConcentricGraph("data/connected_3.txt");//example System.out.println("Distance of each vertex from A:"); } System.out.println(cGraph.distanceMap("A")); System.out.println("distance (A): +cGraph.distance("A")); System.out.println("Graph radius: " +cGraph.radius()); System.out.println("Graph Centers: " + cGraph.getCenters()); System.out.println("Concentric Graph: " + cGraph); // Bonus credit Distance of each vertex from A: {A=0, B=1, C=1, D=2, E=2, F=3, G=4, H=2} distance (A): 4 Graph radius: 2 Graph Centers: [D, E] Concentric Graph: Ring 0: [D, E] Ring 1: [C, F, B] Ring 2: [H, A, G] 4. Sample Two public static void main(String[] args) throws IOException { ConcentricGraph cGraph = new ConcentricGraph("data/connected_usa.txt"); System.out.println("Distance of each state from New York: "); System.out.println(cGraph.distanceMap ("New York")); System.out.println("distance (New York): " + cGraph.distance("New York")); System.out.println("Graph radius: " +cGraph.radius()); System.out.println("Graph Centers: " + cGraph.getCenters()); System.out.println("Concentric Graph: " + cGraph); // Bonus Credit Distance of each state from New York: {North Carolina=4, Indiana=3, Wyoming=6, Utah=7, Arizona=7, Montana=6, Kentucky-3, Kansas=5, California=8, Delaware=2, Florida=6, Pennsylvania=1, Mississippi-5, Iowa-5, Illinois-4, Texas=6, Connecticut=1, Georgia=5, Maryland=2, Virginia=3, Idaho=7, Vermont=1, Oregon=8, Maine=3, Tennessee-4, Oklahoma=5, Alabama=5, Arkansas=5, South Carolina-5, Washington-8, Nebraska=5, West Virginia=2, Arkanssas-6, Massachusetts=1, Colorado-6, Missouri=4, North Dakota=5, Wisconsin-4, Nevada=8, New York=0, Rhode Island=1, South Dakota=5, Minnesota=4, New Jersey=1, Michigan=3, New Mexico=6, New Hampshire=2, Louisiana=6, Ohio=2} distance (New York): 8 Graph radius: 6 Graph Centers: Concentric Graph: Software Dev. & Problem Solving II Graphs & Breadth-First Search Goals of the Assignment Practice using graphs and searches with graphs. This assignment will require the Graph interface and the Vertex and AdjacencyGraph classes implemented during class as well as the implementation of the BFS algorithm. JUnit unit testing is not expected for this assignment. Read this document in its entirety before asking for help from the course staff. The following terminologies will be used in the assignment: Background Let G be a graph, and A and B be two vertices in G. We have learned that BFS can be used to find one of the shortest paths from A to B. We will call such a path a BFS path. distance (A, B) is the number of edges along a BFS path from A to B. distance (A) is the maximum distance of A to any vertices in G. That is distance (A) = max{distance (A, X), for any vertex X in G} A vertex C is called a center of G if distance (C) A Activities 1. Add the following getter to your AdjacencyGraph class. protected Map getVertices() { return vertices; ii. B } 2. Open and examine the provided file named ConcentericGraph.java. a. In the constructor, initialize centers and graph: i. e. H iii. The same vertex may appear on multiple lines in the file. You only add each value to the graph once. iv. If an IOException occurs while trying to read a graph, you may rethrow it. b. Complete the distanceMap (start) method where you compute distance (start, X), for each element X. Create a hash map that maps each element X (String) to distance (start, X), and returns it. You are not allowed to use the bf Path method you wrote in the lecture. Though bf Path can solve this problem easily, using it whenever you compute the distance of each X from start would be very inefficient. Instead, consider using the hash map along with BFS. Your constructor should read files named "connected_*.txt" in the data directory of your repository. Take a moment to examine the text files. Each line represents an adjacency list where the first value is a vertex in the graph, and the remaining values are the vertices to which it is connected. For example, the line "A, B, C" indicates that vertex A is connected to both vertex B and vertex C. Assume that the connections between neighbors are undirected'. c. Complete the distance (start) method where you compute distance (start) and return it. d. Complete the radius () method where you comp and return it. the radius of this graph Now you are ready to complete search Centers () that sets the centers of the graph. If there are multiple centers, you need to filter them to only include the ones that have the most neighbors. There could be still multiple centers of the graph after filtering. f. (10% bonus credit) Override the toString method that returns a concentric view of the graph. Refer to the sample output in the next section. Hint: Use BFS starting from centers to build a string representation. 3. Sample One public static void main(String[] args) throws IOException { ConcentricGraph cGraph = new ConcentricGraph("data/connected_3.txt");//example System.out.println("Distance of each vertex from A:"); } System.out.println(cGraph.distanceMap("A")); System.out.println("distance (A): +cGraph.distance("A")); System.out.println("Graph radius: " +cGraph.radius()); System.out.println("Graph Centers: " + cGraph.getCenters()); System.out.println("Concentric Graph: " + cGraph); // Bonus credit Distance of each vertex from A: {A=0, B=1, C=1, D=2, E=2, F=3, G=4, H=2} distance (A): 4 Graph radius: 2 Graph Centers: [D, E] Concentric Graph: Ring 0: [D, E] Ring 1: [C, F, B] Ring 2: [H, A, G] 4. Sample Two public static void main(String[] args) throws IOException { ConcentricGraph cGraph = new ConcentricGraph("data/connected_usa.txt"); System.out.println("Distance of each state from New York: "); System.out.println(cGraph.distanceMap ("New York")); System.out.println("distance (New York): " + cGraph.distance("New York")); System.out.println("Graph radius: " +cGraph.radius()); System.out.println("Graph Centers: " + cGraph.getCenters()); System.out.println("Concentric Graph: " + cGraph); // Bonus Credit Distance of each state from New York: {North Carolina=4, Indiana=3, Wyoming=6, Utah=7, Arizona=7, Montana=6, Kentucky-3, Kansas=5, California=8, Delaware=2, Florida=6, Pennsylvania=1, Mississippi-5, Iowa-5, Illinois-4, Texas=6, Connecticut=1, Georgia=5, Maryland=2, Virginia=3, Idaho=7, Vermont=1, Oregon=8, Maine=3, Tennessee-4, Oklahoma=5, Alabama=5, Arkansas=5, South Carolina-5, Washington-8, Nebraska=5, West Virginia=2, Arkanssas-6, Massachusetts=1, Colorado-6, Missouri=4, North Dakota=5, Wisconsin-4, Nevada=8, New York=0, Rhode Island=1, South Dakota=5, Minnesota=4, New Jersey=1, Michigan=3, New Mexico=6, New Hampshire=2, Louisiana=6, Ohio=2} distance (New York): 8 Graph radius: 6 Graph Centers: Concentric Graph:
Expert Answer:
Related Book For
Integrated Accounting
ISBN: 978-1285462721
8th edition
Authors: Dale A. Klooster, Warren Allen, Glenn Owen
Posted Date:
Students also viewed these programming questions
-
The Grand Marriott Hotel is a large mid-range hotel in Miami. Part of its quality management practices is to inspect guest rooms immediately after house staff have finished cleaning. A sample of 50...
-
Shamrock Company is considering the purchase of a new machine. The invoice price of the machine is $149,000, freight charges are estimated to be $3,700, and installation costs are expected to be...
-
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...
-
A certain apple bruises if a net force greater than 9 . 5 N is exerted on it . Would a 0 . 1 3 k g apple be likely to bruise if it falls 1 . 8 m and stops after sinking 0 . 0 5 m into the grass?...
-
Verify that |z= |z|2| of for (a) z = 2 - 4i (b) z = - 3 + 5i
-
A B D E F G H J K M N R 72 73 74 75 71 QUESTION 3 - FINANCING OPTIONS THE US COMPANY HAS VARIOUS OPTIONS TO FINANCE THIS ACQUISITION FOR ITS EXACT USD AMOUNT OPTION 1: A LOAN AT 7%, MATURITY 4 YEARS,...
-
Many extraction systems are partially miscible at high concentrations of solute but close to immiscible at low solute concentrations. At relatively low solute concentrations both McCabe-Thiele and...
-
On January 8, the end of the first weekly pay period of the year, Regis Company's payroll register showed that its employees earned $22,760 of office salaries and $65,840 of sales salaries....
-
Same Exercise as Week 10 for large cities- this time, profile two smaller cities- under 100,000 of population. Choose any city in America, but make sure the cities are in different states. Show the...
-
The Capital-Ideas Company is in its development stage and is deciding how to formally organize its business venture. The founder, Rolf Lee, is considering organizing as either a proprietorship or a...
-
(a) Find the five-number summary, and (b) draw a box-and-whisker plot of the data. 388 6 2 9 87 9 6 9 3 1 6 2 9 8779 O (a) Min = |(Simplify your answer.)
-
What strategies are most effective in optimizing organizational skills within high-complexity environments, and how do these strategies affect overall productivity and efficiency ?
-
(1). Please convert the following MIPS code shown below into C code. add $to, $0, $0 add St2, SO, SO addi Ss0, $0, 3 labell: slt St1, St0,Ss0 beq St1, SO, label2 addi St2, St2, 2 addi St0, St0, 1 j...
-
Morpeth Ltd. began 2020 with retained earnings of $12 million. Revenues during the year were $37 million and expenses totalled $26 million. Morpeth declared dividends of $8 million. What was the...
-
A diving board is held by two pillars (see image below). The board is 2.4 m long and has a total mass of 8 kg. The pillars are separated by a distance d = 0.9 m. What is the force on the second...
-
How to create a relational model from DDL statements and how you save a relational model design.?
-
Explain using a search tree why the cut in the following program has no effect on the solutions found to the query ancestor(X,bob). Does the cut improve the efficiency at all? Why or why not?...
-
Make an argument that Williams had a right to delay the closing until after August 1.
-
What information is contained on the Cash Payments Journal report?
-
What assumption does the computer make when generating the inventory valuation (LIFO) report?
-
How can a company improve its working capital?
-
The first column in Table 8-5 lists transaction amounts that have been summed to obtain a batch total. Assume that all data in the first column are correct. Columns a through d contain batch totals...
-
The Moose Wings Cooperative Flight Club owns a number of airplanes and gliders. It serves fewer than 2,000 members, who are numbered sequentially from the founder, Tom Eagle (0001), to the newest...
-
Use the following data to calculate the effects of different backup approaches. Which approach would you recommend? Why? Consider the time required to backup, the amount of media that must be...
Study smarter with the SolutionInn App