Lab 11: Graph Data Structures Implement the Graph ADT with two data structures: Graph_ES edge set...

  

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}}