Iterative Deepening Depth First Search (IDDFS) in Python with path backtrace.

graph.png

Iterative Deepening Depth First Search (IDDFS).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "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",
    "        \"\"\"\n",
    "        Initialize a new node.\n",
    "        \n",
    "        Args:\n",
    "            label: the string identifier for the node\n",
    "        \"\"\"\n",
    "        self.label = label\n",
    "        self.children = []\n",
    "        \n",
    "    def __lt__(self,other):\n",
    "        \"\"\"\n",
    "        Perform the less than operation (self < other).\n",
    "        \n",
    "        Args:\n",
    "            other: the other Node to compare to\n",
    "        \"\"\"\n",
    "        return (self.label < other.label)\n",
    "    \n",
    "    def __gt__(self,other):\n",
    "        \"\"\"\n",
    "        Perform the greater than operation (self > other).\n",
    "        \n",
    "        Args:\n",
    "            other: the other Node to compare to\n",
    "        \"\"\"\n",
    "        return (self.label > other.label)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        \"\"\"Return a string form of this node.\"\"\"\n",
    "        return '{} -> {}'.format(self.label, self.children)\n",
    "    \n",
    "    def add_child(self, node, cost=1):\n",
    "        \"\"\"\n",
    "        Add a child node to this node.\n",
    "        \n",
    "        Args:\n",
    "            node: the node to add to the children\n",
    "            cost: the cost of the edge (default 1)\n",
    "        \"\"\"\n",
    "        if type(node) is list:\n",
    "            [self.add_child(sub_node) for sub_node in node]\n",
    "            return\n",
    "        edge = Edge(self, node, cost)\n",
    "        self.children.append(edge)\n",
    "    \n",
    "    \n",
    "class Edge(object):\n",
    "    \"\"\"This class represents an edge in a graph.\"\"\"\n",
    "    \n",
    "    def __init__(self, source: Node, destination: Node, cost: int=1, bidirectional: bool=False):\n",
    "        \"\"\"\n",
    "        Initialize a new edge.\n",
    "        \n",
    "        Args:\n",
    "            source: the source of the edge\n",
    "            destination: the destination of the edge\n",
    "            cost: the cost of the edge (default 1)\n",
    "            bidirectional: whether source is accessible (default False)\n",
    "        \"\"\"\n",
    "        self.source = source\n",
    "        self.destination = destination\n",
    "        self.cost = cost\n",
    "        self.bidirectional = bidirectional\n",
    "    \n",
    "    def __repr__(self):\n",
    "        \"\"\"Return a string form of this edge.\"\"\"\n",
    "        return '{}: {}'.format(self.cost, self.destination.label)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "![Graph](./graph.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = Node('A')\n",
    "B = Node('B')\n",
    "C = Node('C')\n",
    "D = Node('D')\n",
    "E = Node('E')\n",
    "F = Node('F')\n",
    "G = Node('G')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A.add_child([B, C, E])\n",
    "B.add_child([A, D, F])\n",
    "C.add_child([G, A])\n",
    "D.add_child(B)\n",
    "E.add_child([F, A])\n",
    "F.add_child([E, B])\n",
    "G.add_child(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "make sure the nodes match the graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A -> [1: B, 1: C, 1: E]\n",
      "B -> [1: A, 1: D, 1: F]\n",
      "C -> [1: G, 1: A]\n",
      "D -> [1: B]\n",
      "E -> [1: F, 1: A]\n",
      "F -> [1: E, 1: B]\n",
      "G -> [1: C]\n"
     ]
    }
   ],
   "source": [
    "_ = [print(node) for node in [A, B, C, D, E, F, G]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "function IDDFS(root)\n",
    "    for depth from 0 to ∞\n",
    "        found ← DLS(root, depth)\n",
    "        if found ≠ null\n",
    "            return found\n",
    "\n",
    "function DLS(node, depth)\n",
    "    if depth = 0 and node is a goal\n",
    "        return node\n",
    "    if depth > 0\n",
    "        foreach child of node\n",
    "            found ← DLS(child, depth−1)\n",
    "            if found ≠ null\n",
    "                return found\n",
    "    return null\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def iddfs(root: Node, goal: str, maximum_depth: int=10):\n",
    "    \"\"\"\n",
    "    Return the IDDFS path from the root node to the node with the goal label.\n",
    "    \n",
    "    Args:\n",
    "        root: the node to start at\n",
    "        goal: the label of the goal node\n",
    "        maximum_depth: the maximum depth to search\n",
    "        \n",
    "    Returns: a list with the nodes from root to goal\n",
    "    \n",
    "    Raises: value error if the goal isn't in the graph\n",
    "    \"\"\"\n",
    "    for depth in range(0, maximum_depth):\n",
    "        result = _dls([root], goal, depth)\n",
    "        if result is None:\n",
    "            continue\n",
    "        return result\n",
    "    \n",
    "    raise ValueError('goal not in graph with depth {}'.format(maximum_depth))\n",
    "\n",
    "def _dls(path: list, goal: str, depth: int):\n",
    "    \"\"\"\n",
    "    Return the depth limited search path from a subpath to the goal.\n",
    "    \n",
    "    Args:\n",
    "        path: the current path of Nodes being taken\n",
    "        goal: the label of the goal node\n",
    "        depth: the depth in the graph to search\n",
    "        \n",
    "    Returns: the path if it exists, none otherwise\n",
    "    \"\"\"\n",
    "    current = path[-1]\n",
    "    if current.label == goal:\n",
    "        return path\n",
    "    if depth <= 0:\n",
    "        return None\n",
    "    for edge in current.children:\n",
    "        new_path = list(path)\n",
    "        new_path.append(edge.destination)\n",
    "        result = _dls(new_path, goal, depth - 1)\n",
    "        if result is not None:\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[D -> [1: B],\n",
       " B -> [1: A, 1: D, 1: F],\n",
       " A -> [1: B, 1: C, 1: E],\n",
       " C -> [1: G, 1: A],\n",
       " G -> [1: C]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iddfs(D, 'G')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "goal not in graph with depth 10",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-0e63d8ce01d0>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0middfs\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mA\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'not a real goal node'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-5-4b0790bb012c>\u001b[0m in \u001b[0;36middfs\u001b[0;34m(root, goal, maximum_depth)\u001b[0m\n\u001b[1;32m     18\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     19\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 20\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'goal not in graph with depth {}'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmaximum_depth\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     21\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     22\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_dls\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mgoal\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mstr\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdepth\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: goal not in graph with depth 10"
     ]
    }
   ],
   "source": [
    "iddfs(A, 'not a real goal node')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reference\n",
    "\n",
    "1.  https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search\n",
    "1.  http://www.geeksforgeeks.org/iterative-deepening-searchids-iterative-deepening-depth-first-searchiddfs/"
   ]
  }
 ],
 "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
}