{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Data Structures for Search\n",
"\n",
"In the previous reading, we introduced breadth-first search (BFS); when searching for a path between two nodes, BFS (in contrast to DFS) finds the shortest one, if one exists at all.\n",
"\n",
"A key detail of the BFS strategy is a TODO list of work to be done (that is, nodes to be visited). A loop keeps popping nodes from the front of the list (and visiting them), then adding new nodes discovered in the process to the end of the list. The search is done when the list is empty, or a path is found. Our prior use of lists for the TODO list was inneficient; in this reading, we'll think more broadly about TODO lists and how to use efficient alternatives to lists.\n",
"\n",
"A data structure to which we only append to the end and from which we only remove items from the front is called a *queue*, or sometimes FIFO (First-In First-Out) queue. There are three patterns with special names that are worth remembering:\n",
"\n",
"**queue**\n",
"* add to the end\n",
"* remove from the front\n",
"\n",
"**stack**\n",
"* add to the end\n",
"* remove from the end\n",
"\n",
"**priority queue**\n",
"* add items anywhere\n",
"* remove smallest/largest\n",
"\n",
"**Fun fact:** if the queue in the BFS algorithm were replaced with a stack, it wouldn't be BFS anymore; perhaps surprisingly, the resulting search algorithm would be a non-recursive DFS search."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It's often a bad idea, but Python lists case be used with all three patterns:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"todo = [\"E\", \"B\", \"A\", \"D\", \"C\"]\n",
"\n",
"# queue\n",
"todo.append(\"F\") # end\n",
"x = todo.pop(0) # front\n",
"\n",
"# stack\n",
"todo.append(\"G\") # end\n",
"x = todo.pop(-1) # front\n",
"\n",
"# priority queue\n",
"todo.append(\"H\") # end\n",
"todo.sort()\n",
"x = todo.pop(-1) # smallest"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Given your knowledge of what list operations are fast (constant time) and slow (for example, linear time or worse), which of the above patterns will be efficient?\n",
"\n",
"Only the stack pattern is efficient, as making changes (pops/appends) at the end of a list is fast. The queue pattern is slow: popping from the front is an O(N) operation. The priority queue pattern is even worse: sorting is generally an O(N log N) operation.\n",
"\n",
"We'll now discuss more efficient options for queues and priority queues.\n",
"\n",
"## Queue Pattern and `deque`\n",
"\n",
"The Python deque (double-edged queue) data structure is efficient when used as either a stack or a queue. You can easily convert a list to a deque, and you can append to a deque as you would a list. One minor difference: instead of `L.pop(0)`, we'll use `dq.popleft()`."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"deque(['B', 'A', 'D', 'C', 'F'])"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from collections import deque\n",
"\n",
"todo = deque([\"E\", \"B\", \"A\", \"D\", \"C\"])\n",
"\n",
"# queue\n",
"todo.append(\"F\") # end\n",
"x = todo.popleft() # front\n",
"\n",
"todo"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can use the deque type instead of lists to make the TODO queue for our BFS implementation more efficient. The following shows our BFS code from last reading, with just three changes (indicated in the comments) necessary to switch from using a list to using a deque:\n",
"\n",
"* `# CHANGE 1: import it`\n",
"* `# CHANGE 2: deque instead of list`\n",
"* `# CHANGE 3: .popleft instead of .pop(0)`"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"from graphviz import Graph, Digraph"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"from collections import deque # CHANGE 1: import it\n",
"\n",
"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_xml_svg()\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",
" todo = deque([self]) # CHANGE 2: deque instead of list\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",
" curr = todo.popleft() # CHANGE 3: .popleft instead of .pop(0)\n",
"\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) # NON-CHANGE 4: append is the same\n",
" child.back = curr\n",
" self.graph.visited.add(child.name)\n",
"\n",
" return None\n",
" \n",
"def backtrace(self, node):\n",
" nodes = []\n",
" while node != None:\n",
" nodes.append(node)\n",
" node = node.back\n",
" return tuple(reversed(nodes))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(node A, node C, node Z)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"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.edge(\"E\", \"Z\")\n",
"g.edge(\"C\", \"Z\")\n",
"g.edge(\"B\", \"A\")\n",
"g.find(\"A\", \"Z\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Same result, but it will be faster for large graphs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Priority Queue Pattern and `heapq`\n",
"\n",
"A* (\"A-start\") is an important AI search algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm that we won't learn in CS 320 (take CS 540 if you're interested).\n",
"\n",
"Instead of using a *queue* to decide the order in which to visit nodes, a *priority queue* is used.\n",
"\n",
"To see why we would want this, let's look at a motivating case. Consider this graph:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"E\")\n",
"g.edge(\"A\", \"D\")\n",
"g.edge(\"D\", \"E\")\n",
"g.edge(\"A\", \"E\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are three paths from A to E:\n",
"1. A, B, C, E\n",
"2. A, E\n",
"3. A, D, E\n",
"\n",
"Which path will DFS choose? Which will BFS choose?\n",
"\n",
"\n",
" ANSWER\n",
" DFS will choose (1), BFS will choose (2)\n",
"\n",
"\n",
"Now what if we're trying to navitage between to points, and some roads/edges are longer than others:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"A\", \"B\", label=\"distance=1\")\n",
"g.edge(\"B\", \"C\", label=\"distance=1\")\n",
"g.edge(\"C\", \"E\", label=\"distance=1\")\n",
"g.edge(\"A\", \"D\", label=\"distance=1\")\n",
"g.edge(\"D\", \"E\", label=\"distance=1\")\n",
"g.edge(\"A\", \"E\", label=\"distance=100\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Which path do you prefer? Unless you like the scenic route, presumably A,D,E -- the one than neither BFS or DFS chooses.\n",
"\n",
"We need to base the order we explore nodes on distance. Rather than popping from the front or end of `todo`, we want to pop closest first. A priority queue is a structure that lets us do this.\n",
"\n",
"Python's heapq functions can accomplish this: https://docs.python.org/3/library/heapq.html. It doesn't need a special structure; it can cleverly arrange items in an underlying list to do this.\n",
"\n",
"Let's try it:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"QUEUE: [1, 3, 5, 4]\n",
"1\n",
"3\n",
"4\n",
"QUEUE: [5]\n",
"QUEUE: [2, 5]\n",
"2\n",
"5\n"
]
}
],
"source": [
"from heapq import heappush, heappop\n",
"\n",
"prioq = [] # regular list\n",
"\n",
"heappush(prioq, 4)\n",
"heappush(prioq, 3)\n",
"heappush(prioq, 5)\n",
"heappush(prioq, 1)\n",
"\n",
"print(\"QUEUE:\", prioq)\n",
"\n",
"print(heappop(prioq))\n",
"print(heappop(prioq))\n",
"print(heappop(prioq))\n",
"\n",
"print(\"QUEUE:\", prioq)\n",
"heappush(prioq, 2)\n",
"print(\"QUEUE:\", prioq)\n",
"\n",
"print(heappop(prioq))\n",
"print(heappop(prioq))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"See how the smallest item remaining is always what you get with `heappop`?\n",
"\n",
"You could logically accomplish the same by sorting the list each time before you want to do `.pop(0)`, but that would be WAY slower.\n",
"\n",
"With the heapq implementation of priority queue, adding and removing items has O(log N) complexity (https://en.wikipedia.org/wiki/Binary_heap#Summary_of_running_times). In contrast, sorting before each pop would have complexity O(N log N). Ouch!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion\n",
"\n",
"There are many ways to techniques for searching through a graph for a value or a path that vary in terms of which nodes are explored first and the extra data structures needed to keep track of work to be done. This simplest is probably recursive DFS (depth-first search); that one is also very memory efficient for graphs that branch out quickly but are not very deep.\n",
"\n",
"Unfortunately, DFS isn't good at finding short paths. BFS (breadth-first search) is guaranteed to find the shorter path. On the other hand, it tends to be harder to implement, and the data structure used to keep track of work to be done can require a lot of memory.\n",
"\n",
"We also learned about three patterns for keeping track of nodes to explore, and efficient data structures for each pattern:\n",
"* stack (can be used for non-recursive DFS) -- a regular Python list makes a good stack (deque is also a good option)\n",
"* queue (used for BFS) -- dequeue is efficient\n",
"* priority queue (used for A*, which we don't cover in CS 320) -- using heapq to add/remove items in a regular Python list is a good option"
]
}
],
"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
}