In this lab, you'll get practice with depth-first search and breadth-first search with some interactive exercises.
Start a new notebook on your virtual machine, then paste+run this code in a cell (you don't need to read it):
from IPython.core.display import display, HTML
from graphviz import Digraph
class test_graph:
def __init__(self):
self.nodes = {}
self.traverse_order = None # in what order were nodes checked?
self.next_guess = 0
self.colors = {}
def node(self, name):
name = str(name).upper()
self.nodes[name] = Node(self, name)
def edge(self, src, dst):
src, dst = str(src).upper(), str(dst).upper()
for name in [src, dst]:
if not name in self.nodes:
self.node(name)
self.nodes[src].children.append(self.nodes[dst])
def _repr_svg_(self):
g = Digraph(engine='neato')
for n in self.nodes:
g.node(n, fillcolor=self.colors.get(n, "white"), style="filled")
children = self.nodes[n].children
for i, child in enumerate(children):
g.edge(n, child.name, penwidth=str(len(children) - i), len="1.5")
return g._repr_svg_()
def dfs(self, src, dst):
src, dst = str(src).upper(), str(dst).upper()
self.traverse_order = []
self.next_guess = 0
self.colors = {}
self.visited = set()
self.path = self.nodes[src].dfs(dst)
display(HTML("now call .visit(???) to identify the first node explored"))
display(self)
def bfs(self, src, dst):
src, dst = str(src).upper(), str(dst).upper()
self.traverse_order = []
self.next_guess = 0
self.colors = {}
self.path = self.nodes[src].bfs(dst)
display(HTML("now call .visit(???) to identify the first node explored"))
display(self)
def visit(self, name):
name = str(name).upper()
if self.traverse_order == None:
print("please call dfs or bfs first")
if self.next_guess == len(self.traverse_order):
print("no more nodes to explore")
return
self.colors = {}
for n in self.traverse_order[:self.next_guess]:
self.colors[n] = "yellow"
if name == self.traverse_order[self.next_guess]:
display(HTML("Correct..."))
self.colors[name] = "yellow"
self.next_guess += 1
else:
display(HTML("<b>Oops!</b> Please guess again."))
self.colors[name] = "red"
display(self)
if self.next_guess == len(self.traverse_order):
if self.path == None:
display(HTML("You're done, there is no path!"))
else:
seq = input("What path was found? [enter nodes, comma separated]: ")
seq = tuple(map(str.strip, seq.upper().split(",")))
if seq == tuple(map(str.upper, self.path)):
print("Awesome!!!")
else:
print("actually, expected was: ", ",".join(self.path))
class Node:
def __init__(self, graph, name):
self.graph = graph
self.name = name
self.children = []
def __repr__(self):
return "node %s" % self.name
def dfs(self, dst):
if self.name in self.graph.visited:
return None
self.graph.traverse_order.append(self.name)
self.graph.visited.add(self.name)
if self.name == dst:
return (self.name, )
for child in self.children:
childpath = child.dfs(dst)
if childpath:
return (self.name, ) + childpath
return None
def backtrace(self):
nodes = []
node = self
while node != None:
nodes.append(node.name)
node = node.back
return tuple(reversed(nodes))
def bfs(self, dst):
added = set()
todo = [self]
self.back = None
added.add(self.name)
while len(todo) > 0:
curr = todo.pop(0)
self.graph.traverse_order.append(curr.name)
if curr.name == dst:
return curr.backtrace()
else:
for child in curr.children:
if not child.name in added:
todo.append(child)
child.back = curr
added.add(child.name)
return NonePaste the following to a cell:
g = test_graph()
g.edge(1, 2)
g.edge(4, 3)
g.edge(1, 3)
g.edge(2, 4)
gIt should look something like this:
Node 1 has two children: nodes 2 and 3. The thicker line to node 2
indicates node 2 is in the children list before node 3.
Let's do a DFS from node 1 to 3. Paste the following:
g.dfs(1, 3)You should see something like this:
Try calling the visit function with
g.visit(1)The visited node should look like this:
Keep making g.visit(????) calls until you complete the depth first search.
Once the target node is reach, you'll be prompted to enter the path from source to destination. Do so and type enter to check your answer:
Paste+run the following:
g = test_graph()
g.edge(1, 2)
g.edge(4, 3)
g.edge(1, 3)
g.edge(2, 4)
g.bfs(1, 3)Paste+run the following (same graph structure as last time, but you'll visit the nodes in a different order):
g = test_graph()
for i in range(5):
g.edge(i, i+1)
g.edge(i, 6)
g.edge(6, i)
g.dfs(0, 4)Then change dfs to bfs and try again.
g = test_graph()
for i in range(0, 4, 2):
g.edge(i, i+2)
g.edge(i+1, i+3)
g.edge(i, i+1)
g.edge(4, 5)
g.bfs(2, 1)Design a problem yourself, then try it out.
# designed by anonymous
g = test_graph()
????
g.????(????, ????)If you are willing to let us share your example with other students, please upload it here:
https://forms.gle/twNV29hGaJ8YB8mC8
You can replace "anonymous" with your name if you'd like credit, or leave it as is for more privacy.