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
-
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?...
-
Downtown Bancshares has 40.000 shares of $8 par common stock outstanding. Suppose Downtown declares and distributes a 16% stock dividend when the market value of its stock is $20 per share. 1....
-
Audiophonics Limited manufactures and sells high-quality and durable ear buds for personal use. Cost data for the product are as follows: Variable costs per unit: Direct materials $12 Direct labour...
-
What is a motion for judgment on the pleadings?
-
According to The Wall Street Journal, Mitsubishi Motors recently announced a major restructuring plan in an attempt to reverse declining global sales. Sup-pose that as part of the restructuring plan...
-
Express 1x dx as a limit of Riemann sums.
-
Given the following sketches, generate an Excel spreadsheet: 1) Count the total degrees of freedom in the sketch. 2) Count the constraints 3) Provide the number of dimensions that are necessary to...
-
As a small business owner, you have been given information that an employee has been stealing from your inventory. After reviewing the security footage you also realize that other employees also...
-
Liquidation Basis of Accounting: Working Backwards Guadeloupe Company is in the process of liquidating, and is using the liquidation basis of accounting. Its beginning and ending statements of net...
-
Event Marketing (Theory) - Define the role/importance of event marketing - Forms of event marketing strategies - Event marketing stakeholders Please also include the references thank you
-
An entity has P8,000,000 income before considering bonus and taxes. According to the terms of bonus arrangement, 12% of the income is to be set aside for distribution among the employees. Assume a...
-
Cardinal Company is considering a five-year project requiring a $2,812,000 investment in equipment with a useful life of five years and no salvage value. The company's discount rate is 16%. The...
-
Firm IBM is in a currency swap that was initiated several years ago. According to the swap, IBM receives 8% in sterling and pays 10% in dollar annually , plus the exchange of the principles at...
-
Assume that the MPS is .25 in an economy that has an aggregate supply curve with a slope of 1. Also, suppose that the price level is flexible downward. A decrease in investment spending of $10...
-
On July 1, 2011, Flashlight Corporation sold equipment it had recently purchased to an unaffiliated company for $480,000. The equipment had a book value on Flashlights books of $390,000 and a...
-
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?
-
a. What responsibility does the auditor have when he believes material errors or irregularities may exist? b. What are the possible effects of the foregoing on the auditor's standard report?
-
Watts and Williams, a firm of certified public acccountants, audited the accounts of Sampson Skins, Inc., a corporation that imports and deals in fine furs. Upon completion of the examination the...
-
a. Can an examination made in accordance with generally accepted auditing standards be relied upon to detect illegal acts? Why or why not? b. What are the possible effects of illegal acts on the...
Study smarter with the SolutionInn App