Depth First Search (DFS) in Python with path backtrace. Iterative and recursive solutions.

Depth First Search (DFS).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 170,
   "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": 171,
   "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": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "A -> ['B', 'Q']"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = tree(5)\n",
    "root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterative\n",
    "\n",
    "```\n",
    "procedure DFS-iterative(G,v):\n",
    "    let S be a stack\n",
    "    S.push(v)\n",
    "    while S is not empty\n",
    "        v = S.pop()\n",
    "        if v is not labeled as discovered:\n",
    "            label v as discovered\n",
    "            for all edges from v to w in G.adjacentEdges(v) do \n",
    "                S.push(w)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def iterative_dfs(root: Node, goal: str) -> list:\n",
    "    \"\"\"\n",
    "    Return the depth first search path from root to gaol.\n",
    "    \n",
    "    Args:\n",
    "        root: the starting node for the search\n",
    "        goal: the goal node for the search\n",
    "        \n",
    "    Returns: a list with the path from root to goal\n",
    "    \n",
    "    Raises: ValueError if goal isn't in the graph\n",
    "    \"\"\"\n",
    "    # create a dictionary of visited nodes\n",
    "    visited = dict()\n",
    "    visited[root] = True\n",
    "    # create a stack of the nodes to visit\n",
    "    stack = [[root]]\n",
    "    \n",
    "    def push_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",
    "            stack.append(new_path)\n",
    "    \n",
    "    # iterate over the nodes in the graph\n",
    "    while len(stack) > 0:\n",
    "        # get the current path and lead node in the path\n",
    "        path = stack.pop()\n",
    "        current = path[-1]\n",
    "        # if the lead node is the goal, return the path\n",
    "        if current.label == goal:\n",
    "            return path\n",
    "        [push_node(path, child) for child in current.children]\n",
    "        \n",
    "    # if we've reached the point the goal couldn't be found\n",
    "    raise ValueError('goal not in the graph')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[A -> ['B', 'Q'],\n",
       " Q -> ['R', 'Y'],\n",
       " Y -> ['Z', 'c'],\n",
       " c -> ['d', 'e'],\n",
       " e -> [None, None]]"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iterative_dfs(root, 'e')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursive\n",
    "\n",
    "```\n",
    "procedure DFS(G,v):\n",
    "    label v as discovered\n",
    "    for all edges from v to w in G.adjacentEdges(v) do\n",
    "        if vertex w is not labeled as discovered then\n",
    "            recursively call DFS(G,w)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def recursive_dfs(root: Node, goal: str) -> list:\n",
    "    \"\"\"\n",
    "    Return the depth first search path from root to gaol.\n",
    "    \n",
    "    Args:\n",
    "        root: the starting node for the search\n",
    "        goal: the goal node for the search\n",
    "        \n",
    "    Returns: a list with the path from root to goal\n",
    "    \n",
    "    Raises: ValueError if goal isn't in the graph\n",
    "    \"\"\"\n",
    "    path = _dfs([root], goal, dict())\n",
    "    if path is None:\n",
    "        raise ValueError('goal not in graph')\n",
    "    return path\n",
    "\n",
    "def _dfs(path: list, goal: str, visited: dict) -> list:\n",
    "    \"\"\"\n",
    "    Perform a Depth First Search step.\n",
    "    \n",
    "    Args:\n",
    "        path: the current path of nodes\n",
    "        goal: the goal node label\n",
    "        visited: the dictionary of visited nodes\n",
    "    \"\"\"\n",
    "    current = path[-1]\n",
    "    # if this is the goal, return the path\n",
    "    if current.label == goal:\n",
    "        return path\n",
    "    # visit this node\n",
    "    visited[current] = True\n",
    "    # generate a list of unvisited children and iterate over it\n",
    "    unvisited = [child for child in current.children if child not in visited]\n",
    "    for child in unvisited:\n",
    "        # generate a new path and recursively call\n",
    "        new_path = list(path)\n",
    "        new_path.append(child)\n",
    "        sub_path = _dfs(new_path, goal, visited)\n",
    "        # make sure the sub path is valid before returning\n",
    "        if sub_path is not None:\n",
    "            return sub_path\n",
    "        else:\n",
    "            continue\n",
    "    # the search couldn't find the goal\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[A -> ['B', 'Q'],\n",
       " Q -> ['R', 'Y'],\n",
       " Y -> ['Z', 'c'],\n",
       " c -> ['d', 'e'],\n",
       " e -> [None, None]]"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recursive_dfs(root, 'e')"
   ]
  }
 ],
 "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
}