"

We often want to solve problems that are expressible in terms of a traversal or search over a graph. One of the goals of a graph traversal is to find all nodes reachable from a given node. In an undirected graph we can follow all edges in both directions; in a directed graph we follow only out-edges. The purpose of the assignment is not only to enhance your programming skills but also your homework percentage. About this assignment: ? This is an optional all or nothing assignment, which means the only grade you can get is 0 or 100 (no partial credit). Make sure your code runs in the environment we set up during HW0. Submission must run in a Python 3+ environment. No code will be debugged, so if it does not run/work, grade is 0. ? While you can ask for guidance to the instructor and the TAs, you cannot share any of your code with your classmates. Any plagiarism detected in this assignment will result in an F as a final grade. ? If the code does not meet the requirements specified in this assignment, the grade will be 0. ? If your code gets 100, you can replace your lowest homework score with that grade. However, the homework replacement policy will no longer apply to your homework grades. For example, if your current scores are 100, 70, 80, 100, 90, 100, the replacement policy lets you to have 100, 80, 80, 100, 90, 100. If you decide to do this assignment and get 100 your new scores are 100, 100, 80, 100, 90, 100, but you are no longer eligible for the replacement policy! (if you get a 0 in this assignment, the replacement policy applies) Instructions: In class, 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). We also discussed how a graph implementation can be used to compute the shortest path using Dijkstra's algorithm. Based on the code we did in class (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

2. You must ensure your stack from LAB 10 works properly, as you must use that stack to produce your result (refer to the slides on how the stack helps you to keep track of the nodes during the traversal) 3. Create the method dijkstra(start). This method takes the key of the starting node and runs Dijkstra's algorithm in an instance of the class Graph. The method returns a dictionary with the value of the shortest path from the starting node to every other node reachable from start.

Notes: - To you follow the alphabetical convention for DFS, you have two options: 1) provide the vertices in alphabetical order and add the edges in alphabetical order or 2) provide vertices and edges in random order and sort them in your method. - You are free to add method that might help you to achieved the stated goal"

Code given so far is:

"

from LAB11 import *

class Node:

def __init__(self,value):

self.value = value

self.connectedTo = {}

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

self.connectedTo[nbr] = weight

def getConnections(self):

return self.connectedTo.keys()

def getValue(self):

return self.value

def getWeight(self,nbr):

return self.connectedTo[nbr]

def __str__(self):

return str(self.value) + ' is adjacent to ' + str([x.value for x

in self.connectedTo])

class Graph:

def __init__(self):

self.vertList = {}

self.numVertices = 0

def getVertex(self,key):

if key in self.vertList:

return self.vertList[key]

else:

return None

def addVertex(self,key):

self.numVertices = self.numVertices + 1

new_node = Node(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 bfs(self,start):

begin=self.getVertex(start)

seen=[begin.value]

visited=[]

q=Queue()

q.enqueue(begin)

while not q.isEmpty():

node = q.dequeue()

visited.append(node.value)

for neighbour in node.connectedTo:

if neighbour.value not in seen:

seen.append(neighbour.value)

q.enqueue(neighbour)

return visited

#'Graph' object is not iterable, thus we use the special method

__iter__ to provide an

# iterable definition that Pyhton can understand

def __iter__(self):

return iter(self.vertList.values())

if __name__ == '__main__':

print("GRAPH #1")

g=Graph()

g.addVertex('A')

g.addVertex('B')

g.addVertex('C')

g.addVertex('D')

g.addVertex('E')

g.addVertex('F')

g.addEdge('A','B')

g.addEdge('A','D')

g.addEdge('A','G')

g.addEdge('B','A')

g.addEdge('B','E')

g.addEdge('B','F')

g.addEdge('C','F')

g.addEdge('D','A')

g.addEdge('D','F')

g.addEdge('E','B')

g.addEdge('E','G')

g.addEdge('F','B')

g.addEdge('F','C')

g.addEdge('F','D')

g.addEdge('G','A')

g.addEdge('G','E')

for v in g:

print(v)

for v in g:

for w in v.getConnections():

print("Edge: ({}, {}) with weight = {}".format(v.getValue(),

w.getValue(), v.getWeight(w)))

print(" GRAPH #2")

my_graph=Graph()

my_graph.addVertex('A')

my_graph.addVertex('B')

my_graph.addVertex('C')

my_graph.addVertex('D')

my_graph.addVertex('E')

my_graph.addEdge('A','C',12)

my_graph.addEdge('A','D',60)

my_graph.addEdge('B','A',10)

my_graph.addEdge('C','B',20)

my_graph.addEdge('C','D',32)

my_graph.addEdge('E','A',7)

for v in my_graph:

print(v)

for v in my_graph:

for w in v.getConnections():

print("Edge: ({}, {}) with weight = {}".format(v.getValue(),

w.getValue(), v.getWeight(w)))"