\" We often want to solve problems that are expressible in terms of a traversal
ID: 3714174 • Letter: #
Question
"
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)))"
Explanation / Answer
#First you need to import your Stack class
#im assuming its named as My_Stack change to whatever you have named it
from My_Stack import Stack
# Add the following fucntions in your graph class
def dfs(self,start):
begin = self.getVertex(start)
seen = [begin.value]
visited = []
st = Stack()
st.push(begin)
while not st.size()==0:
current_vertex = st.peek()
st.pop()
visited.append(current_vertex.value)
connections = current_vertex.getConnections()
for neighbor in connections:
if not neighbor in seen:
st.push(self.getVertex(neighbor))
seen.append(neighbor)
return visited
def dijsktra(graph, start):
visited = {start: 0}
path = {}
current_vertex = self.getVertex(start)
while not len(visited)==self.numVertices:
min_node = None
for node in self.vertList.keys():
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
current_weight = visited[min_node]
for neighbor in self.getVertex(min_node).getConnections():
weight = current_weight + min_node.getWeight(neighbor)
if neighbor not in visited or weight<visited[neighbor]:
visited[neighbor] = weight
return visited
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.