PLEASE WRITE IN PYTHON

In this assignment you will be creating a graph from an input data file called graph.txt. The first line in that file will be a single integer v. This number will denote the number of vertices to follow. The next v lines will be the labels for the vertices. There will be one label to a line. Assume that the labels are unique. The next line after the labels for vertices will be a single number e. This number will denote the number of edges to follow. There will be one edge per line. Each edge will be of the form - fromVertex, toVertex, and weight. If the weight is not given, assign a default weight of 1 to that edge. After the list of edges there will be a label for the starting vertex. This will be the starting vertex for both the Depth First Search and Breadth First Search. After that there will be two cities and you will have to delete the edges connecting the two cities and print the adjacency matrix. Then there will be a single city and you will delete this vertex and all edges from and to this vertex. You will print the list of vertices and and the adjacency matrix showing all edges from it and all edges to it have been deleted.

Here is the outline of the code that we developed in class that you will be modifying. You can add an Edge class if you want to. You will be adding the following functions to the Graph class and the following test cases to your main program.

def Graph (object): # get index from vertex label def getIndex (self, label): # get edge weight between two vertices # return -1 if edge does not exist def getEdgeWeight (self, fromVertexLabel, toVertexLabel): # get a list of immediate neighbors that you can go to from a vertex # return empty list if there are none def getNeighbors (self, vertexLabel): # get a copy of the list of vertices def getVertices (self): # delete an edge from the adjacency matrix def deleteEdge (self, fromVertexLabel, toVertexLabel): # delete a vertex from the vertex list and all edges from and # to it in the adjacency matrix def deleteVertex (self, vertexLabel): def main(): # test depth first search # test breadth first search # test deletion of an edge # test deletion of a vertex main() 

graph.txt:

12 Seattle San Francisco Los Angeles Denver Kansas City Chicago Boston New York Atlanta Miami Dallas Houston 46 0 1 1 0 3 1 0 5 1 1 0 1 1 2 1 1 3 1 2 1 1 2 3 1 2 4 1 2 10 1 3 0 1 3 1 1 3 2 1 3 4 1 3 5 1 4 2 1 4 3 1 4 5 1 4 7 1 4 8 1 4 10 1 5 0 1 5 3 1 5 4 1 5 6 1 5 7 1 6 5 1 6 7 1 7 4 1 7 5 1 7 6 1 7 8 1 8 4 1 8 7 1 8 9 1 8 10 1 8 11 1 9 8 1 9 11 1 10 2 1 10 4 1 10 8 1 10 11 1 11 8 1 11 9 1 11 10 1 Houston Seattle San Francisco Dallas 

Outline Code:

class Stack (object): def __init__ (self): self.stack = [] # add an item to the top of the stack def push (self, item): self.stack.append ( item ) # remove an item from the top of the stack def pop (self): return self.stack.pop() # check what item is on top of the stack without removing it def peek (self): return self.stack[len(self.stack) - 1] # check if a stack is empty def isEmpty (self): return (len(self.stack) == 0) # return the number of elements in the stack def size (self): return (len(self.stack)) class Queue (object): def __init__ (self): self.queue = [] def enqueue (self, item): self.queue.append (item) def dequeue (self): return (self.queue.pop(0)) def isEmpty (self): return (len (self.queue) == 0) def size (self): return len (self.queue) class Vertex (object): def __init__ (self, label): self.label = label self.visited = False # determine if vertex was visited def wasVisited (self): return self.visited # determine the label of the vertex def getLabel (self): return self.label # string representation of the label def __str__(self): return str (self.label) ''' class Edge (object): def __init__ (self, fromVertex, toVertex, weight): self.u = fromVertex self.v = toVertex self.weight = weight # comparison operators def __lt__ (self, other): def __le__ (self, other): def __gt__ (self, other): def __ge__ (self, other): def __eq__ (self, other): def __ne__ (self, other): ''' class Graph (object): def __init__ (self): self.Vertices = [] self.adjMat = [] # checks if a vertex label already exists def hasVertex (self, label): nVert = len (self.Vertices) for i in range (nVert): if (label == (self.Vertices[i]).label): return True return False # add a vertex with given label def addVertex (self, label): if not self.hasVertex (label): self.Vertices.append (Vertex (label)) # add a new column in the adjacency matrix for new Vertex nVert = len (self.Vertices) for i in range (nVert - 1): (self.adjMat[i]).append (0) # add a new row for the new Vertex in the adjacency matrix newRow = [] for i in range (nVert): newRow.append (0) self.adjMat.append (newRow) # add weighted directed edge to graph def addDirectedEdge (self, start, finish, weight = 1): self.adjMat[start][finish] = weight # add weighted undirected edge to graph def addUndirectedEdge (self, start, finish, weight = 1): self.adjMat[start][finish] = weight self.adjMat[finish][start] = weight # return an unvisited vertex adjacent to v def getAdjUnvisitedVertex (self, v): nVert = len (self.Vertices) for i in range (nVert): if (self.adjMat[v][i] > 0) and (not (self.Vertices[i]).wasVisited()): return i return -1 # does a depth first search in a graph def dfs (self, v): # create a stack theStack = Stack() # mark the vertex as visited and push on the stack (self.Vertices[v]).visited = True print (self.Vertices[v]) theStack.push (v) while (not theStack.isEmpty()): # get an adjacent unvisited vertex u = self.getAdjUnvisitedVertex (theStack.peek()) if (u == -1): u = theStack.pop() else: (self.Vertices[u]).visited = True print (self.Vertices[u]) theStack.push(u) # stack is empty reset the flags nVert = len (self.Vertices) for i in range (nVert): (self.Vertices[i]).visited = False # does a breadth first search in a graph def bfs (self, v): # create a queue theQueue = Queue () # mark the vertex as visited and enqueue (self.Vertices[v]).visited = True print (self.Vertices[v]) theQueue.enqueue (v) while (not theQueue.isEmpty()): # get the vertex at the front v1 = theQueue.dequeue() # get an adjacent unvisited vertex v2 = self.getAdjUnvisitedVertex (v1) while (v2 != -1): (self.Vertices[v2]).visited = True print (self.Vertices[v2]) theQueue.enqueue (v2) v2 = self.getAdjUnvisitedVertex (v1) # queue is empty reset the flags nVert = len (self.Vertices) for i in range (nVert): (self.Vertices[i]).visited = False def main(): # Create Graph object cities = Graph() # Open file for reading inFile = open ("./graph.txt", "r") # Read the vertices numVertices = int ((inFile.readline()).strip()) print (numVertices) for i in range (numVertices): city = (inFile.readline()).strip() print (city) cities.addVertex (city) # Read the edges numEdges = int ((inFile.readline()).strip()) print (numEdges) for i in range (numEdges): edge = (inFile.readline()).strip() print (edge) edge = edge.split() start = int (edge[0]) finish = int (edge[1]) weight = int (edge[2]) cities.addDirectedEdge (start, finish, weight) # Read the starting vertex for dfs, bfs, and shortest path startVertex = (inFile.readline()).strip() print (startVertex) # Close file inFile.close() # print the adjacency matrix nVert = len (cities.Vertices) for i in range (nVert): for j in range (nVert): print (cities.adjMat[i][j], end = " ") print() print () # Do depth first search from Houston print ("Depth First Search from Houston") cities.dfs (11) print() # Do breadth first search from Houston print ("Breadth First Search from Houston") cities.bfs (11) main()