The following class will be used to represent vertices in your graph. A vertex has an identifier, and it can also have a set of attributes.

class Vertex:

def __init__(self,id):

self.attributes = {}

self.attributes['id'] = id

def __str__(self):

return str(self.attributes)

def new_copy(self):

return Vertex(self.attributes['id'])

def set(self,key,value):

self.attributes[key] = value

def get(self,key):

return self.attributes[key]

Your library will provide undirected graphs. You may not change the name of the class, but you can change its inheritance, and you will need to add methods.

Implement the methods for the following class

class DirectedGraph(Graph):

pass

Both kinds of graphs should have an API that allows us to create new graphs.

PROBLEM 1: Implement a method 'add_vertex' that takes a vertex as an input and adds it to the graph.

PROBLEM 2: Implement an 'add_edge' method that takes two vertices and adds an edge between them in the graph. For example, your implementation should work with the following codes.

def create_graph_1():

G = UndirectedGraph()

for i in ['r','s','t','u','v','w','x','y']:

G.add_vertex(Vertex(i))

for (v1,v2) in [('v','r'),('r','s'),('s','w'),

('w','t'),('w','x'),('t','x'),

('t','u'),('x','u'),('x','y'),('u','y')]:

G.add_edge(G.id_to_v[v1],G.id_to_v[v2])

return G

G1 = create_graph_1()

def create_graph_2():

G = DirectedGraph()

for i in ['u','v','w','x','y','z']:

G.add_vertex(Vertex(i))

for (v1,v2) in [('u','x'),('u','v'),('x','v'),('v','y'),

('y','x'),('w','y'),('w','z'),('z','z')]:

G.add_edge(G.id_to_v[v1],G.id_to_v[v2])

return G

G2 = create_graph_2()

def create_graph_3():

G = DirectedGraph()

for i in ['u','v','w','x','y','z']:

G.add_vertex(Vertex(i))

for (v1,v2) in [('u','x'),('u','v'),('v','y'),

('y','x'),('w','y'),('w','z')]:

G.add_edge(G.id_to_v[v1],G.id_to_v[v2])

return G

G3 = create_graph_3()

Note 2 important things. First, the methods add_vertex and add_edge do not return a new graph, instead they update the graph in-place. Second, in the graph implementation, you need to work with vertex objects, and not their identifier. It means that to interface with the graph, the graph needs to provide a dictionary 'id_to_v' that keeps track of which identifier corresponds to which vertex.

PROBLEM 3: Implement the id_to_v