RecursiveClassInstances.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursive Object-oriented Programming\n",
    "The Python script that follows illustrates how to grow a binary tree graph using a recursive method in a user-defined object class.  This example serves to elucidate an algorithmic approach for building (binary) decision trees.\n",
    "\n",
    "## Code overview:\n",
    "* Each instance of the class `binaryNode()` contains the following attributes:\n",
    "\n",
    "    * `.ID`: the hex value of the current instance (self) of `binaryNode()` in memory.\n",
    "    \n",
    "    * `.depth`: the recursion-depth of current node (instance); test value for recursion termination.\n",
    "    \n",
    "    * `.parentID` : the hex memory value of the parent instance that called the current instance.\n",
    "    \n",
    "    * `.parentEdge`: edge-type (`'left'` or `'right'`) connecting the current node to its parent instance.\n",
    "    \n",
    "    * `.leftChild`: contains the child node along the left edge or `None` if current node is a leaf.\n",
    "    \n",
    "    * `.rightChild`: contains the child node along the right edge or `None` if current node is a leaf.\n",
    "    \n",
    "2. Method `grow(self, depthLimit)` self-calls to initialize (recursive) instances of `binaryNode()` until the specified recursion-depth (`depthLimit`) is reached. \n",
    "\n",
    "3. Intrinsic method `__str__` builds the output string used to illustrate the graph structure of the `binaryNode` object.\n",
    "\n",
    "4. Method `Mapper(self, nodeMap)` takes a list as input and appends a dict of IDs of nodes and their local lineage for all nodes in the tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define binary tree-node class.  Class comprised of a node initialization function, \n",
    "# a recursive method to expand the tree using sub-trees, and an intrinsic __str__ \n",
    "# method to report tree contents and branching structure.\n",
    "class binaryNode():\n",
    "    \n",
    "    # Initialization definition for each node instance\n",
    "    def __init__(self, depth, parentID=None, parentEdge=None,\n",
    "                 leftChild=None, rightChild=None):\n",
    "        \n",
    "        self.ID = hex(id(self)) # Hex value of this current instance of binaryNode\n",
    "        \n",
    "        self.depth = depth # attribute for testing recursion termination condition\n",
    "        \n",
    "        self.parentID = parentID # Hex value of the particular instance of \n",
    "                                 # binaryNode that generated this instance\n",
    "        \n",
    "        self.parentEdge = parentEdge # used in reporting here. In decsion trees, \n",
    "                                     # this attribute could record the upstream \n",
    "                                     # split condition that prompted initialization \n",
    "                                     # of this current node.\n",
    "        \n",
    "        self.leftChild = leftChild # attribute to contain left-edge child node.\n",
    "                                   # remains 'None' if terminal node.\n",
    "        \n",
    "        self.rightChild = rightChild # attribute to contain right-edge child node.\n",
    "                                     # remains 'None' if terminal node.\n",
    "        \n",
    "    # Method to grow tree by recursively appending left and right child sub-trees \n",
    "    # until the specified depth limit is reached.\n",
    "    def grow(self, depthLimit):\n",
    "        \n",
    "        childDepth = self.depth + 1 # child nodes will be one level deeper than \n",
    "                                    # current node level\n",
    "        \n",
    "        # initialize left-edge child node\n",
    "        self.leftChild = binaryNode(childDepth, parentID=self.ID, parentEdge='left')\n",
    "        \n",
    "        # initialize right-edge  child node\n",
    "        self.rightChild = binaryNode(childDepth, parentID=self.ID, parentEdge='right')\n",
    "                    \n",
    "        if childDepth < depthLimit:  # Termination condition for recursive function call \n",
    "            \n",
    "            self.leftChild.grow(depthLimit) # recursive function call to expand left-child\n",
    "            \n",
    "            self.rightChild.grow(depthLimit) # recursive function call to expand right-child\n",
    "            \n",
    "        else:\n",
    "            \n",
    "            pass # recursion exit channel\n",
    "        \n",
    "    # Recursive method to report tree structure as a string; indentation indicates \n",
    "    # recursion-depth of node in the tree.\n",
    "    def __str__(self):\n",
    "        \n",
    "        # report attributes and identity of current node\n",
    "        nodeStr = '  ' * (self.depth) + 'Node ' + self.ID + \\\n",
    "            ' at depth: {self.depth}'.format(self=self)  \n",
    "        \n",
    "        # if it exists, append the type of edge ('left' or 'right') that links this\n",
    "        # current node to its parent node.\n",
    "        if self.parentEdge is not None:\n",
    "            nodeStr = nodeStr + ', ParentID: {self.parentID}, Parent Edge: {self.parentEdge}'.format(self=self)\n",
    "    \n",
    "        # if child nodes exist, self-call to report them.  If not, pass.\n",
    "        if self.leftChild is not None: \n",
    "            nodeStr = nodeStr + '\\n' + self.leftChild.__str__()\n",
    "            \n",
    "        if self.rightChild is not None:\n",
    "            nodeStr = nodeStr + '\\n' + self.rightChild.__str__()\n",
    "        \n",
    "        # return full string description of tree\n",
    "        return(nodeStr)\n",
    "    \n",
    "    def FindParentNode(self, binaryNodeInst):\n",
    "        \n",
    "        self_id = hex(id(self))\n",
    "        \n",
    "        if binaryNodeInst is not None:\n",
    "            \n",
    "            if (hex(id(binaryNodeInst.leftChild)) == self_id or \n",
    "                hex(id(binaryNodeInst.rightChild)) == self_id):\n",
    "                \n",
    "                return hex(id(binaryNodeInst))\n",
    "        \n",
    "            else:\n",
    "                \n",
    "                outList = [self.FindParentNode(binaryNodeInst.leftChild), \n",
    "                           self.FindParentNode(binaryNodeInst.rightChild)]\n",
    "                outList = [val for val in outList if val is not None]\n",
    "    \n",
    "                if outList:\n",
    "                    return outList[0]\n",
    "                else:\n",
    "                    return\n",
    "            \n",
    "        else:\n",
    "            \n",
    "            return\n",
    "        \n",
    "    def Mapper(self, NodeMap):\n",
    "        \n",
    "        if self.parentID:\n",
    "            parentID = self.parentID\n",
    "        else:\n",
    "            parentID = None\n",
    "            \n",
    "        if self.leftChild:\n",
    "            leftChildID = self.leftChild.ID\n",
    "        else:\n",
    "            leftChildID = None\n",
    "                \n",
    "        if self.rightChild:\n",
    "            rightChildID = self.rightChild.ID\n",
    "        else:\n",
    "            rightChildID = None\n",
    "                \n",
    "        MapDict = {\n",
    "                   'nodeID': self.ID, \n",
    "                   'parentID': parentID, \n",
    "                   'leftChildID': leftChildID,\n",
    "                   'rightChildID': rightChildID\n",
    "                  }\n",
    "            \n",
    "        NodeMap.append(MapDict)\n",
    "            \n",
    "        if leftChildID:\n",
    "            NodeMap.extend(self.leftChild.Mapper([]))\n",
    "\n",
    "        if rightChildID:\n",
    "            NodeMap.extend(self.rightChild.Mapper([]))\n",
    "                \n",
    "        return NodeMap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grow a tree and report\n",
    "With our `binaryNode` class now defined, we can generate a tree with two commands.  First, we will initialize a single node instance, `rootNode`, with depth zero--the root node of the tree.  Second, we will call the `rootNode.grow()` method to recursively append subtrees, starting from `rootNode`, to a depth of `3`.  The resultant tree can be viewed with the `print()` command where extent of indentation represents the recursion-depth of each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node 0x7fe2dcb0c860 at depth: 0\n",
      "  Node 0x7fe2dcb0c048 at depth: 1, ParentID: 0x7fe2dcb0c860, Parent Edge: left\n",
      "    Node 0x7fe2dcb0c8d0 at depth: 2, ParentID: 0x7fe2dcb0c048, Parent Edge: left\n",
      "      Node 0x7fe2dcb0cac8 at depth: 3, ParentID: 0x7fe2dcb0c8d0, Parent Edge: left\n",
      "      Node 0x7fe2dcb0c978 at depth: 3, ParentID: 0x7fe2dcb0c8d0, Parent Edge: right\n",
      "    Node 0x7fe2dcb0c9b0 at depth: 2, ParentID: 0x7fe2dcb0c048, Parent Edge: right\n",
      "      Node 0x7fe2dcb0c9e8 at depth: 3, ParentID: 0x7fe2dcb0c9b0, Parent Edge: left\n",
      "      Node 0x7fe2dcb0c780 at depth: 3, ParentID: 0x7fe2dcb0c9b0, Parent Edge: right\n",
      "  Node 0x7fe2dcb0c898 at depth: 1, ParentID: 0x7fe2dcb0c860, Parent Edge: right\n",
      "    Node 0x7fe2dcb0cb00 at depth: 2, ParentID: 0x7fe2dcb0c898, Parent Edge: left\n",
      "      Node 0x7fe2dcb0ca58 at depth: 3, ParentID: 0x7fe2dcb0cb00, Parent Edge: left\n",
      "      Node 0x7fe2dcb0cb38 at depth: 3, ParentID: 0x7fe2dcb0cb00, Parent Edge: right\n",
      "    Node 0x7fe2dcb0c7f0 at depth: 2, ParentID: 0x7fe2dcb0c898, Parent Edge: right\n",
      "      Node 0x7fe2dcb0cbe0 at depth: 3, ParentID: 0x7fe2dcb0c7f0, Parent Edge: left\n",
      "      Node 0x7fe2dcb0cc88 at depth: 3, ParentID: 0x7fe2dcb0c7f0, Parent Edge: right\n"
     ]
    }
   ],
   "source": [
    "# Initialize root node from which to grow tree graph.\n",
    "rootNode = binaryNode(0)\n",
    "\n",
    "# Grow a four-level deep tree.\n",
    "rootNode.grow(3)\n",
    "\n",
    "# Illustrate tree structure \n",
    "print(rootNode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nested sub-trees are of same class as root\n",
    "Below we see that a child node a couple of levels below root (level 2) forms a sub-tree with the same attributes and methods. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    Node 0x7fe2dcb0c9b0 at depth: 2, ParentID: 0x7fe2dcb0c048, Parent Edge: right\n",
      "      Node 0x7fe2dcb0c9e8 at depth: 3, ParentID: 0x7fe2dcb0c9b0, Parent Edge: left\n",
      "      Node 0x7fe2dcb0c780 at depth: 3, ParentID: 0x7fe2dcb0c9b0, Parent Edge: right\n"
     ]
    }
   ],
   "source": [
    "print(rootNode.leftChild.rightChild)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<method-wrapper '__repr__' of binaryNode object at 0x7fe2dcb0c048>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rootNode.leftChild.__repr__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x7fe2dcb0c048'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(id(rootNode.leftChild))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dumbFunc(ass):\n",
    "    return \n",
    "\n",
    "def notAsDumbFunc(ass):\n",
    "    return ass, dumbFunc(ass)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, None)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "notAsDumbFunc(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dumbFunc(4) != None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, None]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[5, None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x7fe2dcb0c048'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rootNode.leftChild.rightChild.FindParentNode(rootNode)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x7fe2dcb0c9e8'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(id(rootNode.leftChild.rightChild.leftChild))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rootNode.leftChild.rightChild.rightChild.leftChild == None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "Map = rootNode.Mapper([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'nodeID': '0x7fe2dcb0c860',\n",
       "  'parentID': None,\n",
       "  'leftChildID': '0x7fe2dcb0c048',\n",
       "  'rightChildID': '0x7fe2dcb0c898'},\n",
       " {'nodeID': '0x7fe2dcb0c048',\n",
       "  'parentID': '0x7fe2dcb0c860',\n",
       "  'leftChildID': '0x7fe2dcb0c8d0',\n",
       "  'rightChildID': '0x7fe2dcb0c9b0'},\n",
       " {'nodeID': '0x7fe2dcb0c8d0',\n",
       "  'parentID': '0x7fe2dcb0c048',\n",
       "  'leftChildID': '0x7fe2dcb0cac8',\n",
       "  'rightChildID': '0x7fe2dcb0c978'},\n",
       " {'nodeID': '0x7fe2dcb0cac8',\n",
       "  'parentID': '0x7fe2dcb0c8d0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0c978',\n",
       "  'parentID': '0x7fe2dcb0c8d0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0c9b0',\n",
       "  'parentID': '0x7fe2dcb0c048',\n",
       "  'leftChildID': '0x7fe2dcb0c9e8',\n",
       "  'rightChildID': '0x7fe2dcb0c780'},\n",
       " {'nodeID': '0x7fe2dcb0c9e8',\n",
       "  'parentID': '0x7fe2dcb0c9b0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0c780',\n",
       "  'parentID': '0x7fe2dcb0c9b0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0c898',\n",
       "  'parentID': '0x7fe2dcb0c860',\n",
       "  'leftChildID': '0x7fe2dcb0cb00',\n",
       "  'rightChildID': '0x7fe2dcb0c7f0'},\n",
       " {'nodeID': '0x7fe2dcb0cb00',\n",
       "  'parentID': '0x7fe2dcb0c898',\n",
       "  'leftChildID': '0x7fe2dcb0ca58',\n",
       "  'rightChildID': '0x7fe2dcb0cb38'},\n",
       " {'nodeID': '0x7fe2dcb0ca58',\n",
       "  'parentID': '0x7fe2dcb0cb00',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0cb38',\n",
       "  'parentID': '0x7fe2dcb0cb00',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0c7f0',\n",
       "  'parentID': '0x7fe2dcb0c898',\n",
       "  'leftChildID': '0x7fe2dcb0cbe0',\n",
       "  'rightChildID': '0x7fe2dcb0cc88'},\n",
       " {'nodeID': '0x7fe2dcb0cbe0',\n",
       "  'parentID': '0x7fe2dcb0c7f0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None},\n",
       " {'nodeID': '0x7fe2dcb0cc88',\n",
       "  'parentID': '0x7fe2dcb0c7f0',\n",
       "  'leftChildID': None,\n",
       "  'rightChildID': None}]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 11]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "randNodePick = Map[random.randint(0, len(Map)-1)]['nodeID']\n",
    "[i for i in range(0,len(Map)) if Map[i]['parentID'] == randNodePick]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x7fe2dcb0cb38'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Map[random.randint(0, len(Map)-1)]['nodeID']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'nodeID': '0x7fe2dcb0ca58',\n",
       " 'parentID': '0x7fe2dcb0cb00',\n",
       " 'leftChildID': None,\n",
       " 'rightChildID': None}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Map[10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'nodeID': '0x7fe2dcb0cb38',\n",
       " 'parentID': '0x7fe2dcb0cb00',\n",
       " 'leftChildID': None,\n",
       " 'rightChildID': None}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Map[11]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'nodeID': '0x7fe2dcb0cb00',\n",
       " 'parentID': '0x7fe2dcb0c898',\n",
       " 'leftChildID': '0x7fe2dcb0ca58',\n",
       " 'rightChildID': '0x7fe2dcb0cb38'}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Map[9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}