{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Search Paths\n",
"\n",
"In the last reading, we learned about how to check whether there is a path from node A to node B.\n",
"\n",
"In this reading, we'll do additional things:\n",
"\n",
"1. return the path (a list of nodes) found instead of just True/False\n",
"2. learn BFS, an alternative to DFS that is guaranteed to find the shortest path"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from graphviz import Graph, Digraph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Review\n",
"\n",
"Let's revisit the graph search from the end of the last reading (only change is addition of `__repr__`):"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd079488790>"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"class mygraph:\n",
" def __init__(self):\n",
" self.nodes = {}\n",
" \n",
" def node(self, name):\n",
" self.nodes[name] = Node(self, name)\n",
" \n",
" def edge(self, src, dst):\n",
" for name in [src, dst]:\n",
" if not name in self.nodes:\n",
" self.node(name)\n",
" self.nodes[src].children.append(self.nodes[dst])\n",
" \n",
" def _repr_svg_(self):\n",
" g = Digraph()\n",
" for n in self.nodes:\n",
" g.node(n)\n",
" for child in self.nodes[n].children:\n",
" g.edge(n, child.name)\n",
" return g._repr_image_svg_xml()\n",
" \n",
" def find(self, src, dst):\n",
" self.visited = set()\n",
" return self.nodes[src].find(dst)\n",
"\n",
"class Node:\n",
" def __init__(self, graph, name):\n",
" self.graph = graph\n",
" self.name = name\n",
" self.children = []\n",
" \n",
" def __repr__(self):\n",
" return \"node %s\" % self.name\n",
" \n",
" def find(self, dst):\n",
" if self.name in self.graph.visited:\n",
" return False\n",
" self.graph.visited.add(self.name)\n",
"\n",
" if self.name == dst:\n",
" return True\n",
" for child in self.children:\n",
" if child.find(dst):\n",
" return True\n",
" return False\n",
"\n",
"g = mygraph()\n",
"g.node(\"A\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"B\")\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"False\n",
"True\n",
"False\n"
]
}
],
"source": [
"print(g.find(\"A\", \"A\"))\n",
"print(g.find(\"A\", \"B\"))\n",
"print(g.find(\"B\", \"D\"))\n",
"print(g.find(\"B\", \"A\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Getting the Path\n",
"\n",
"Rather than just determine if there is a path, let's output what it is. We'll modify the `find` method. If there's a path, it should return it as a list (or tuple!) of nodes traversed. If there is not a path, it should return None.\n",
"\n",
"The logic works like this: if the X node is a child of the W node, and we've found an `(X,Y,Z)` path, then `(W,X,Y,Z)` is also a valid path. On line 11, we're using tuple concatenation to create a new tuple based on the one the child found, but with the parent added to the beginning."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd07948ab20>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def find_v2(self, dst):\n",
" if self.name in self.graph.visited:\n",
" return None\n",
"\n",
" if self.name == dst:\n",
" return (self.name, )\n",
"\n",
" for child in self.children:\n",
" path = child.find(dst)\n",
" if path != None:\n",
" return (self.name, ) + path\n",
"\n",
" return None\n",
"\n",
"# monkey patching lets us redefine a method in\n",
"# a class, without recreating the whole class\n",
"# (not a recommended practice, but means we don't\n",
"# need to show the complete new version of Node)\n",
"Node.find = find_v2\n",
"\n",
"g = mygraph()\n",
"g.node(\"A\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"B\")\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"path = g.find(\"A\", \"B\")\n",
"print(path)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"('C', 'D', 'B')\n"
]
}
],
"source": [
"path = g.find(\"C\", \"B\")\n",
"print(path)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Multiple Paths\n",
"\n",
"What if there are multiple paths? Which will we return?"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd07948a940>"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = mygraph()\n",
"g.edge(\"A\", \"E\")\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"E\")\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('A', 'E')"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.find(\"A\", \"E\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nice, it found the shortest one! But what if we build the same graphs, but adding the edges in a different order?"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd079490130>"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = mygraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"E\")\n",
"g.edge(\"A\", \"E\") # we used to add this first, now last\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"('A', 'B', 'C', 'D', 'E')"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.find(\"A\", \"E\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Yuck! If Google Maps gave me these directions for getting from city A to E, then I might just switch to Apple Maps.\n",
"\n",
"The search pattern we're using is known as \"depth first search\", or DFS. It explores one child completely (including all that child's descendents) before checking if the other children know a path.\n",
"\n",
"The alternative to DFS is BFS, or \"breadth first search\". This algorithm will explore all children before exploring grandchildren, before exploring great grandchildren, etc.\n",
"\n",
"The algorithm for BFS is not recursive, but many find it less intuitive that recursive DFS. The strategy is to keep a \"TODO\" list of all nodes that need to be visited. The list is used as a *queue*, meaning the first nodes added to the list will be the first ones visited. When a child is explored, we generally discover grandchildren, but rather than explore those grandchildren immediately (as in DFS), we add those grandchildren to the end of the TODO queue, to be processed eventually after the other children.\n",
"\n",
"Let's try it:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd079490220>"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def find_bfs(self, dst):\n",
" # the first node to explore is the starting point\n",
" todo = [self]\n",
"\n",
" # keep looping while there are unexplored nodes\n",
" while len(todo) > 0:\n",
" print(\"TODO:\", todo)\n",
" curr = todo.pop(0) # pop from beginning\n",
"\n",
" print(\"VISITING:\", curr)\n",
" if curr.name == dst:\n",
" return True\n",
" else:\n",
" for child in curr.children:\n",
" if not child.name in self.graph.visited:\n",
" todo.append(child) # add to end\n",
" self.graph.visited.add(child.name)\n",
"\n",
" # nothing left to check, and we haven't already returned True\n",
" return False\n",
"\n",
"Node.find = find_bfs\n",
"\n",
"g = mygraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"A\", \"C\")\n",
"g.edge(\"B\", \"D\")\n",
"g.edge(\"B\", \"E\")\n",
"g.edge(\"C\", \"F\")\n",
"g.edge(\"C\", \"G\")\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"TODO: [node A]\n",
"VISITING: node A\n",
"TODO: [node B, node C]\n",
"VISITING: node B\n",
"TODO: [node C, node D, node E]\n",
"VISITING: node C\n",
"TODO: [node D, node E, node F, node G]\n",
"VISITING: node D\n",
"TODO: [node E, node F, node G]\n",
"VISITING: node E\n",
"TODO: [node F, node G]\n",
"VISITING: node F\n",
"TODO: [node G]\n",
"VISITING: node G\n"
]
},
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.find(\"A\", \"G\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cool! We're searching one level at a time. But did you notice we lost some functionality? We aren't keeping track of how we got to the final node. There are often multiple ways to reach a node, so we should add a `back` attribute to backtrack how we got there."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd0794b5760>"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def backtrace(self, node):\n",
" nodes = []\n",
" while node != None:\n",
" nodes.append(node)\n",
" node = node.back\n",
" return tuple(reversed(nodes))\n",
"\n",
"def find_bfs_v2(self, dst):\n",
" # the first node to explore is the starting point\n",
" todo = [self]\n",
" self.back = None\n",
" self.graph.visited.add(self.name)\n",
"\n",
" # keep looping while there are unexplored nodes\n",
" while len(todo) > 0:\n",
" print(\"TODO:\", todo)\n",
" curr = todo.pop(0) # pop from beginning\n",
"\n",
" print(\"VISITING:\", curr)\n",
" if curr.name == dst:\n",
" return backtrace(self, curr)\n",
" else:\n",
" for child in curr.children:\n",
" if not child.name in self.graph.visited:\n",
" todo.append(child)\n",
" self.graph.visited.add(child.name)\n",
"\n",
" # remember we found child via curr\n",
" # (will help us backtrack later!)\n",
" child.back = curr\n",
" \n",
" # nothing left to check, and we haven't already returned True\n",
" return None\n",
"\n",
"Node.find = find_bfs_v2\n",
"\n",
"g = mygraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"A\", \"C\")\n",
"g.edge(\"B\", \"D\")\n",
"g.edge(\"B\", \"E\")\n",
"g.edge(\"C\", \"F\")\n",
"g.edge(\"C\", \"G\")\n",
"g"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"TODO: [node A]\n",
"VISITING: node A\n",
"TODO: [node B, node C]\n",
"VISITING: node B\n",
"TODO: [node C, node D, node E]\n",
"VISITING: node C\n",
"TODO: [node D, node E, node F, node G]\n",
"VISITING: node D\n",
"TODO: [node E, node F, node G]\n",
"VISITING: node E\n",
"TODO: [node F, node G]\n",
"VISITING: node F\n",
"TODO: [node G]\n",
"VISITING: node G\n"
]
},
{
"data": {
"text/plain": [
"(node A, node C, node G)"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.find(\"A\", \"G\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's make a tougher test case, with the following:\n",
"1. cycles\n",
"2. short and long paths to the same target"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.mygraph at 0x7fd0794b5760>"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.edge(\"E\", \"Z\")\n",
"g.edge(\"C\", \"Z\")\n",
"g.edge(\"B\", \"A\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now there are two A-to-Z paths:\n",
"* A,B,E,Z\n",
"* A,C,Z\n",
"\n",
"We ought to find the second one!"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"TODO: [node A]\n",
"VISITING: node A\n",
"TODO: [node B, node C]\n",
"VISITING: node B\n",
"TODO: [node C, node D, node E]\n",
"VISITING: node C\n",
"TODO: [node D, node E, node F, node G, node Z]\n",
"VISITING: node D\n",
"TODO: [node E, node F, node G, node Z]\n",
"VISITING: node E\n",
"TODO: [node F, node G, node Z]\n",
"VISITING: node F\n",
"TODO: [node G, node Z]\n",
"VISITING: node G\n",
"TODO: [node Z]\n",
"VISITING: node Z\n"
]
},
{
"data": {
"text/plain": [
"(node A, node C, node Z)"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.find(\"A\", \"Z\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Just what we wanted."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have lots of experience using data structures like lists and dicts to keep track of data. But data structures can also be used to keep track work that a program needs to do. This strategy is used by BFS and many other systems.\n",
"\n",
"Although more complicated to implement, BFS guarantees the shortest path will be found (in contrast to DFS). Of course, significant memory might be required to maintain the queue of nodes to visit if the graph is large. Depending on the shape of the graph, this memory expense may be greater or less than the memory needed for the stack frames necessarly during a recursive depth-first search."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}