Lab 11: Graph Data Structures Implement the Graph ADT with two data structures: Graph_ES edge set...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Lab 11: Graph Data Structures Implement the Graph ADT with two data structures: Graph_ES edge set Graph_AS adjacency set Note: you can find partial or full solutions for this lab in the textbook and video lectures for this module. Avoid external resources during lab; do your best to figure things out with you and your partner. Feel free to access these resources afterwards if you do not finish during. Graph Each graph you implement should support the following ADT Magic Metohds init(V, E) -initializes with optional sets of vertices V and edges E len iter returns the number of vertices in the graph -iterates over all vertices in graph Non-magic Methods add_vertex(v) - adds vertex v to graph remove_vertex(v) -removes vertex v from graph - raise a KeyError if v is not in graph add_edge(e) adds edge e to graph (assume e is a 2-tuple) remove_edge(e) removes edge e from graph (assume e is a 2-tuple) - raise a KeyError if e is not in graph neighbors (v) -returns an iterable collection of neighbors of vertex v - Running time: Examples * O(m), Graph_ES (m is the number of edges in the graph) * O(1), Graph_AS (time to return an iterator does not depend on the number of neighbors) Examples Any examples below are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own tests, and think carefully about edge cases. >>> from lab11 import * >>> # 1 2 3 >>> vs = {1,2,3} >>> es {(1,2), (2,1), (2,3), (3,2)} >>> g = Graph ES (vs, es) >>> assert len(g) == 3 >>> verts = set() >>> for v in vs: verts.add(v) >>> assert verts VS >>> nbrs {2:set()} >>> for n in g._neighbors (2): nbrs [2].add(n) >>> assert nbrs (2:13, 1}} Lab 11: Graph Data Structures Implement the Graph ADT with two data structures: Graph_ES edge set Graph_AS adjacency set Note: you can find partial or full solutions for this lab in the textbook and video lectures for this module. Avoid external resources during lab; do your best to figure things out with you and your partner. Feel free to access these resources afterwards if you do not finish during. Graph Each graph you implement should support the following ADT Magic Metohds init(V, E) -initializes with optional sets of vertices V and edges E len iter returns the number of vertices in the graph -iterates over all vertices in graph Non-magic Methods add_vertex(v) - adds vertex v to graph remove_vertex(v) -removes vertex v from graph - raise a KeyError if v is not in graph add_edge(e) adds edge e to graph (assume e is a 2-tuple) remove_edge(e) removes edge e from graph (assume e is a 2-tuple) - raise a KeyError if e is not in graph neighbors (v) -returns an iterable collection of neighbors of vertex v - Running time: Examples * O(m), Graph_ES (m is the number of edges in the graph) * O(1), Graph_AS (time to return an iterator does not depend on the number of neighbors) Examples Any examples below are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own tests, and think carefully about edge cases. >>> from lab11 import * >>> # 1 2 3 >>> vs = {1,2,3} >>> es {(1,2), (2,1), (2,3), (3,2)} >>> g = Graph ES (vs, es) >>> assert len(g) == 3 >>> verts = set() >>> for v in vs: verts.add(v) >>> assert verts VS >>> nbrs {2:set()} >>> for n in g._neighbors (2): nbrs [2].add(n) >>> assert nbrs (2:13, 1}}
Expert Answer:
Answer rating: 100% (QA)
The images you provided describe an assignment for implementing graph data structures in Python specifically a Graph Abstract Data Type ADT with two d... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these computer network questions
-
Who are the parties and what does each party seek to accomplish? What are the facts of the case? What is the difference between an annulment and a divorce and why might an annulment be preferred....
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
(i) Write down the linear program relaxation for the vertex cover problem and solve the linear program. [6 marks] (ii) Based on the solution of the linear program in (b)(i), derive an integer...
-
What is the probability that the number X of successes in the personnel managers sample of 100 employees in question 10 will be 48 or more?
-
What is meant by aggregation? Why is aggregation important for macroeconomic analysis?
-
A horizontal circular plate is suspended as shown from three wires which are attached to a support at D and form 30 angles with the vertical. Knowing that the z component of the force exerted by wire...
-
. Effect of decisions on ratios (Learning Objective 4) Betsy Ross Flag Companys long-term debt agreements make certain demands on the business. For example, Ross may not purchase treasury stock in...
-
The following client- prepared bank reconciliation is being examined by Zachary Kallick, CPA, during the examination of the financial statements of Simmons Company. Required: Items (a) through (e)...
-
Exercise 4 - 9 ( Algo ) Preparing closing entries and a post - closing trial balance LO P 2 Following are accounts and year - end adjusted balances of Cruz Company as of December 3 1 . \ table [ [...
-
Vulcan Flyovers offers scenic overflights of Mount Saint Helens. Data concerning the company's operations in July appear below: Vulcan Flyovers Operating Data For the Month Ended July 31 Flights (g)...
-
The following MINITAB output presents a confidence interval for the difference between two proportions. a. Compute the point estimate of p1 p2. b. Fill in the blanks: We are _____________ confident...
-
Imagine you are a finance manager and you have the choice between two candidates to fill a vacant financial accounting position. One candidate has five years more experience including a stint at a...
-
As a finance manager with a vacancy on the accounting team, who would be more valuable to you: a data analyst, a business analyst, a data scientist, an accountant with deep accounting experience, or...
-
The following MINITAB output presents a confidence interval for the difference between two proportions. a. Compute the point estimate of p1 p2. b. Fill in the blanks: We are _____________ confident...
-
The IPSASB identifies citizens as primary users of GPFRs. Is it reasonable to assume that citizens actually read GPFRs produced by public sector entities? If not, does it still make sense to design...
-
A project has the following cash flows. Assume an interest rate of 8%. What is the Equivalent Annual Annuity (EAA)? Year. Cash Flow 0 -$1,742 1 $1,044 2 $856 3 $892 4 $768 Note: Enter your answer...
-
Before the latest financial crisis and recession, when was the largest recession of the past 50 years, and what was the cumulative loss in output over the course of the slowdown?
-
On December 31, 20x7, the stockholders equity section of Tsang Companys balance sheet appeared as follows: The following are selected transactions involving stockholders equity in 20x8: On January 4,...
-
Recording Purchase and Sales Transactions} Raymond Company and Geeslin Company both use a perpetual inventory system. The following transactions occurred during the month of January: Jan. 1 Raymond...
-
Inventory Costing Methods} Refer to the information for Tyler Company above and assume the company uses a perpetual inventory system. \section*{Required:} Calculate ending inventory and cost of goods...
Study smarter with the SolutionInn App