Breadth First Search (BFS) in Python with path backtrace

Breadth First Search (BFS).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 366,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \"\"\"This class represents a node in a graph.\"\"\"\n",
    "    \n",
    "    def __init__(self, label: str=None):\n",
    "        \"\"\"Initialize a new node.\"\"\"\n",
    "        self.label = label\n",
    "        self.children = []\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"Return a string form of this node.\"\"\"\n",
    "        return '{} -> {}'.format(self.label, [child.label for child in self.children])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 367,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fill_tree(root: Node, depth: int, labels: list, breadth: int=2):\n",
    "    \"\"\"\n",
    "    Fill a tree of a certain depth at the given root node.\n",
    "    \n",
    "    Args:\n",
    "      root: the root node to recursively attach children to\n",
    "      depth: the depth of the tree to generate\n",
    "      labels: a list of labels for the nodes\n",
    "      breadth: the number of children for each node\n",
    "    \"\"\"\n",
    "    # the base case of depth 0, return\n",
    "    if depth == 0:\n",
    "        return\n",
    "    # create children nodes and attach them to the root\n",
    "    for _ in range(0, breadth):\n",
    "        root.children.append(Node()) \n",
    "    # name this node\n",
    "    root.label = labels.pop(0)\n",
    "    # recurse over the depth - 1 for each child\n",
    "    for child in root.children:\n",
    "        fill_tree(child, depth - 1, labels, breadth)\n",
    "\n",
    "def tree(depth, breadth=2) -> Node:\n",
    "    \"\"\"\n",
    "    Generate a binary of tree of a certain depth.\n",
    "    \n",
    "    Args:\n",
    "        depth: the number of levels in the graph\n",
    "        breadth: the number of nodes in each level\n",
    "        \n",
    "    Returns: the root node of the graph\n",
    "    \n",
    "    Raises: ValueError if $breadth^{depth} > 52$ (number of available letters for labels)\n",
    "    \"\"\"\n",
    "    labels = list('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')\n",
    "    if breadth**depth > len(labels):\n",
    "        raise ValueError('depth exceeds the number of labels')\n",
    "    root = Node()\n",
    "    fill_tree(root, depth, labels, breadth)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Breadth-First-Search(Graph, root):   \n",
    "    create empty set S\n",
    "    create empty queue Q      \n",
    "\n",
    "    add root to S\n",
    "    Q.enqueue(root)                      \n",
    "\n",
    "    while Q is not empty:\n",
    "        current = Q.dequeue()\n",
    "        if current is the goal:\n",
    "            return current\n",
    "        for each node n that is adjacent to current:\n",
    "            if n is not in S:\n",
    "                add n to S\n",
    "                Q.enqueue(n)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 368,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bfs(root: Node, goal: str) -> list:\n",
    "    \"\"\"\n",
    "    Return the breadth first search path from root to goal\n",
    "    \n",
    "    Args:\n",
    "        root: the starting node\n",
    "        goal: the target nodes label\n",
    "        \n",
    "    Returns: the path from root to goal\n",
    "    \n",
    "    Raises: ValueError if the goal isn't in the graph\n",
    "    \"\"\"\n",
    "    visited = dict()\n",
    "    visited[root] = True\n",
    "    # create a queue of lists (paths)\n",
    "    queue = [[root]]\n",
    "    \n",
    "    def enqueue_node(path, node):\n",
    "        # check for the nodes existance in the visiation table\n",
    "        if node is not None and node not in visited:\n",
    "            # visit the node\n",
    "            visited[node] = True\n",
    "            # add the node to the path\n",
    "            new_path = list(path)\n",
    "            new_path.append(node)\n",
    "            # enqueue the new path\n",
    "            queue.insert(0, new_path)\n",
    "            \n",
    "    # iterate over the items in the queue\n",
    "    while len(queue) > 0:\n",
    "        # get the current path and lead node in the path\n",
    "        path = queue.pop()\n",
    "        current = path[-1]\n",
    "        # ask the node if it's our goal\n",
    "        if current.label == goal:\n",
    "            return path\n",
    "        # enqueue the child nodes\n",
    "        [enqueue_node(path, node) for node in current.children]\n",
    "        \n",
    "    # the goal wasn't found\n",
    "    raise ValueError('goal not in graph')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 369,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "A -> ['B', 'Q']"
      ]
     },
     "execution_count": 369,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = tree(5)\n",
    "root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 370,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[A -> ['B', 'Q'],\n",
       " Q -> ['R', 'Y'],\n",
       " Y -> ['Z', 'c'],\n",
       " c -> ['d', 'e'],\n",
       " d -> [None, None]]"
      ]
     },
     "execution_count": 370,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs(root, 'd')"
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}