{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Infinite Graphs\n",
"\n",
"Sometimes you'll encounter infinite graphs. For example, if webpages are nodes, and links are edges, the Internet is an infinite graph. This is literal, as some pages may be generated on the fly (imagine a calendar: the Jan 2021 page may have a link to the Feb 2021 page, and so on forever).\n",
"\n",
"We can use DFS or BFS to search for a path between two nodes in such a graph. To avoid scenarios where an infinite series of nodes is explored before nearer children, we'll focus on BFS for this document.\n",
"\n",
"Regular BFS searches until the todo queue is exhausted, but modifications that only search a fixed number of nodes or to a fixed depth may be appropriate for infinite graphs.\n",
"\n",
"BFS has another use beyond finding paths: if the algorithm starts and we're only aware of one node (or a subset of nodes) in the graph, searching out from there can help us discover new nodes. In the webpages example, maybe the algorithm knows only a single starting URL, but it can discover the URLs of other pages by following links.\n",
"\n",
"Rather than use the Internet for the coding examples here, we'll have a made-up graph over which we'll search. It is structured like this:\n",
"\n",
"1. there are an infinite number of nodes, each corresponding to an integer\n",
"2. a node X0 (for example, 890) will have an edge to X2 (for example 892). Furthermore, X1 will have an edge to X3, X2 will have an edge to X4, X3 will have an edge to X0, and X4 will have an edge to X1\n",
"3. a node X0 will also have an edge to (X+10)0\n",
"\n",
"This graph is infinite, so we will not represent it using a Node class. Instead, all we need to do BFS is a function that tells us the children of a given node (given the above description, the function will need to separate that first digit from the rest. We can do that with the mod operator:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12\n",
"3\n"
]
}
],
"source": [
"node = 123\n",
"prefix = node // 10\n",
"digit = node % 10\n",
"print(prefix)\n",
"print(digit)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following function tells us the children for any given node number in our infinite graph."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[893]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def get_children(node):\n",
" children = []\n",
" prefix = node // 10\n",
" digit = node % 10\n",
" if digit < 5:\n",
" children.append(prefix * 10 + (node + 2) % 5)\n",
" if digit == 0:\n",
" children.append(node + 10)\n",
" return children\n",
"\n",
"get_children(891)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[672, 680]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"get_children(670)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now use `get_children` to start at a given node (say 1) and run BFS until we discover 30 nodes (or run out of nodes to explore). We'll also have a graph dict that keeps track of the nodes and edges we discover."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"visit 1\n",
"visit 3\n",
"visit 0\n",
"visit 2\n",
"visit 10\n",
"visit 4\n",
"visit 12\n",
"visit 20\n",
"visit 14\n",
"visit 22\n",
"visit 30\n",
"visit 11\n",
"visit 24\n",
"visit 32\n",
"visit 40\n",
"visit 13\n",
"visit 21\n",
"visit 34\n",
"visit 42\n",
"visit 50\n",
"visit 23\n",
"visit 31\n",
"visit 44\n",
"visit 52\n",
"visit 60\n",
"[0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34, 40, 41, 42, 44, 50, 52, 54, 60, 62, 70]\n"
]
}
],
"source": [
"start_node = 1\n",
"todo = deque([start_node])\n",
"discovered = {start_node}\n",
"graph = {} # key: parent node, val: list of children\n",
"\n",
"while len(todo) > 0 and len(discovered) < 30:\n",
" node = todo.popleft()\n",
" print(\"visit\", node)\n",
" children = get_children(node)\n",
" graph[node] = children\n",
" for child in children:\n",
" if not child in discovered:\n",
" todo.append(child)\n",
" discovered.add(child)\n",
" \n",
"print(sorted(discovered))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we like, we can also use Graphviz to visualize the nodes and edges we found:"
]
},
{
"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": [
"from graphviz import Digraph\n",
"\n",
"g = Digraph()\n",
"\n",
"for parent in graph:\n",
" g.node(str(parent))\n",
" for child in graph[parent]:\n",
" g.edge(str(parent), str(child))\n",
" \n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above is of coures a finite subset of the nodes and edges in our graph. If we wanted to, we could replace `< 30` with a much number larger to run the algorithm longer and discover new nodes. The graph is infinite, after all!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion\n",
"\n",
"In this reading, we learned that the BFS algorithm doesn't need a complete graph represented by `Node` objects to work. It just needs a way (such as a function or method) to tell us what children each node has. Before, we just used BFS to search for paths between a pair of nodes, but in this more general form, we can use it to discover new nodes that we didn't know existed, just by exploring out from a starting node. We also saw that BFS can work with an infinite graph, though it probably makes sense to bound how many nodes are searched, to avoid an infinite loop."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}