Here is my code so far:

#HW #4

#Due Date: 07/27/2018, 11:59PM EST

#Name: Kannan Ramanathan

class Node:

def __init__(self, value):

self.value = value

self.next = None

def get_value(self):

return self.value

def get_next(self):

return self.next

def set_value(self,new_value):

self.value = new_value

def set_next(self,new_next):

self.next = new_next

def __str__(self):

return "Node({})".format(self.value)

__repr__ = __str__

class Stack:

def __init__(self):

self.top = None

self.__size__ = 0

def __str__(self):

temp = self.top

x = ''

x += 'Top: {} '.format(temp)

x += 'Stack: '

while temp:

x += '{} '.format(temp.get_value())

temp = temp.get_next()

return x

__repr__ = __str__

def push(self,item):

n = Node(item)

if self.top == None:

self.top = n

self.__size__ += 1

return

n.set_next(self.top)

self.top = n

self.__size__ += 1

def pop(self):

if self.top == None:

return 'Stack is empty'

x = self.top

self.top = self.top.next

self.__size__ -= 1

return x

def peek(self):

return self.top

def isEmpty(self):

return self.top == None

def size(self):

return self.__size__

class Vertex:

def __init__(self,value):

self.value = value

self.connectedTo = {}

def addNeighbor(self,node,weight=1):

self.connectedTo[node] = weight

def __str__(self):

return str(self.value) + ': ' + str([x.value for x in self.connectedTo])

class Graph:

def __init__(self):

self.vertList = {}

def __iter__(self):

return iter(self.vertList.values())

def getVertex(self,key):

if key in self.vertList:

return self.vertList[key]

else:

return None

def addVertex(self,key):

new_node = Vertex(key)

self.vertList[key] = new_node

return new_node

def addEdge(self,frm,to,weight=1):

if frm not in self.vertList:

new_node = self.addVertex(frm)

if to not in self.vertList:

new_node = self.addVertex(to)

self.vertList[frm].addNeighbor(self.vertList[to], weight)

def dfs(self, start):

visited = [False]*(len(self.vertList))

visited[0] = True

for i in range(len(self.vertList)):

if visited[i] == False:

self.vertList[i] = self.dfs(i)

else:

i -= 1

return(self.vertList)

Instructions: The work in this assignment must be completed alone Use the starter code provided on this CANVAS assignment. Do not change the function names or given started code on your script The file name must be HW4.py (incorrect name files will get a -10 point deduction) When any function returns an error, it must be a string containing "erro Do not include test code outside any function in the upload. Remove all your testing code before uploading your file. That includes user-defined input - Goal: In module 5, we discussed the Graph data structure. Since the graph is a non-linear structure, there is no unique traversal. Nodes can be found using Breadth-First Search (visit the sibling nodes before visiting the child nodes) and Depth-first search (visit the child nodes before visiting the sibling nodes) Based on the implementation of the Graph data structure discussed during the hands-on video lecture (provided in the starter code) 1. Create the method dfs(start). This method takes the key of the starting node and performs Depth-first search in an instance of the class Graph. This method must return a list that contains the order in which the nodes where access during the search (following alphabetical order when discovering node) 2. You must ensure your stack from LAB 9 works properly, as you must use that stack to produce your result. If you don't use the stack. your will not receive credit for the assignment Grading Notes: A random instance of the Graph class (directed or undirected) will be created and the dfs method will be called on 4 different starting nodes for 25 pts each. Make sure you use the Graph data structure provided in the starter code, otherwise, no credit will be given. Vertices and edges will be provided on alphabetical order, so the final result should be only the one provided by following alphabetical order EXTRA CREDIT: 20 pts, added regardless of the maximum 100 Modify the dfs method so it produces the traversal following the alphabetical order even if the vertices and edges are provided in a random order. Extra credit will be provided only if your code passes all test cases