Intro_to_MonteCarlo_4_RecommendationSystems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agent-Based Monte-Carlo Simulation\n",
    "\n",
    "We have an ant sitting in one corner of a cube wireframe.\n",
    "\n",
    "The ant takes exactly 1 minute to crawl from one end of the wire to the other.  At each vertex of the cube, it has an equal probability of going down either one of the wires.\n",
    "\n",
    "What is the probability distribution of the time it will take the ant to crawl from where it is the vertex on the opposite end of the cube?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is what it looks like:  http://prntscr.com/80168r\n",
    "\n",
    "A network.  The ant is sitting at Node 1 and needs to get to Node 8 following the routing rules at each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import datetime\n",
    "import random\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "from matplotlib import pyplot as plt\n",
    "import igraph\n",
    "from igraph import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IGRAPH U--- 0 0 --\n",
      "+ attr: date (g)\n",
      "2015-08-02\n"
     ]
    }
   ],
   "source": [
    "## Define the graph:\n",
    "cube = Graph()\n",
    "cube[\"date\"] = datetime.date.today()\n",
    "print cube\n",
    "print cube[\"date\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IGRAPH U--- 8 0 --\n",
      "+ attr: date (g)\n"
     ]
    }
   ],
   "source": [
    "cube.add_vertices(8)\n",
    "print cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IGRAPH U--- 8 0 --\n",
      "+ attr: date (g), beenthere (v)\n"
     ]
    }
   ],
   "source": [
    "cube.vs[\"beenthere\"] = (\"Now\", \"No\", \"No\", \"No\", \"No\", \"No\", \"No\", \"Endpoint\")\n",
    "print cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IGRAPH U--- 8 12 --\n",
      "+ attr: date (g), beenthere (v)\n",
      "+ edges:\n",
      "0 -- 1 3 5   2 -- 1 3 7   4 -- 3 5 7   6 -- 1 5 7\n",
      "1 -- 0 2 6   3 -- 0 2 4   5 -- 0 4 6   7 -- 2 4 6\n"
     ]
    }
   ],
   "source": [
    "cube.add_edges ([(0,1),(0,5),(0,3), (1,6), (1,2),  (2,7), (2,3), (3,4), (4,5), (4,7), (5,6), (6,7)])\n",
    "print cube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IGRAPH UN-- 8 12 --\n",
      "+ attr: date (g), beenthere (v), name (v)\n",
      "+ edges (vertex names):\n",
      "1 -- 2, 4, 6   3 -- 2, 4, 8   5 -- 4, 6, 8   7 -- 2, 6, 8\n",
      "2 -- 1, 3, 7   4 -- 1, 3, 5   6 -- 1, 5, 7   8 -- 3, 5, 7\n",
      "['Now', 'No', 'No', 'No', 'No', 'No', 'No', 'Endpoint']\n"
     ]
    }
   ],
   "source": [
    "cube.vs[\"name\"] = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\"]\n",
    "print cube\n",
    "print cube.vs[\"beenthere\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"350pt\" height=\"350pt\" viewBox=\"0 0 350 350\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-0\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.75 0 L 1.75 -8.75 L 8.75 -8.75 L 8.75 0 Z M 1.96875 -0.21875 L 8.53125 -0.21875 L 8.53125 -8.53125 L 1.96875 -8.53125 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 5.214844 0 L 3.984375 0 L 3.984375 -7.839844 C 3.6875 -7.558594 3.296875 -7.273438 2.816406 -6.992188 C 2.335938 -6.707031 1.90625 -6.496094 1.523438 -6.359375 L 1.523438 -7.546875 C 2.210938 -7.867188 2.8125 -8.257813 3.328125 -8.722656 C 3.84375 -9.179688 4.207031 -9.625 4.421875 -10.0625 L 5.214844 -10.0625 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 7.046875 -1.183594 L 7.046875 0 L 0.421875 0 C 0.414063 -0.296875 0.460938 -0.582031 0.566406 -0.855469 C 0.734375 -1.304688 1.003906 -1.746094 1.375 -2.1875 C 1.746094 -2.621094 2.285156 -3.128906 2.988281 -3.703125 C 4.074219 -4.597656 4.808594 -5.304688 5.195313 -5.828125 C 5.574219 -6.347656 5.765625 -6.839844 5.769531 -7.308594 C 5.765625 -7.792969 5.589844 -8.203125 5.246094 -8.539063 C 4.894531 -8.871094 4.441406 -9.039063 3.882813 -9.042969 C 3.285156 -9.039063 2.8125 -8.863281 2.460938 -8.507813 C 2.105469 -8.152344 1.925781 -7.660156 1.921875 -7.035156 L 0.65625 -7.164063 C 0.742188 -8.105469 1.066406 -8.824219 1.632813 -9.320313 C 2.195313 -9.8125 2.953125 -10.058594 3.910156 -10.0625 C 4.867188 -10.058594 5.628906 -9.792969 6.191406 -9.261719 C 6.75 -8.726563 7.03125 -8.066406 7.035156 -7.28125 C 7.03125 -6.878906 6.949219 -6.484375 6.789063 -6.097656 C 6.621094 -5.707031 6.347656 -5.296875 5.96875 -4.871094 C 5.585938 -4.441406 4.953125 -3.855469 4.074219 -3.109375 C 3.332031 -2.488281 2.859375 -2.066406 2.652344 -1.847656 C 2.4375 -1.621094 2.265625 -1.402344 2.132813 -1.183594 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.585938 -2.644531 L 1.820313 -2.808594 C 1.957031 -2.109375 2.195313 -1.609375 2.539063 -1.300781 C 2.875 -0.992188 3.289063 -0.835938 3.78125 -0.839844 C 4.355469 -0.835938 4.84375 -1.039063 5.246094 -1.441406 C 5.640625 -1.839844 5.839844 -2.335938 5.84375 -2.933594 C 5.839844 -3.496094 5.65625 -3.960938 5.289063 -4.332031 C 4.917969 -4.695313 4.449219 -4.878906 3.882813 -4.882813 C 3.648438 -4.878906 3.359375 -4.832031 3.015625 -4.742188 L 3.152344 -5.824219 C 3.230469 -5.816406 3.296875 -5.8125 3.351563 -5.8125 C 3.875 -5.8125 4.34375 -5.949219 4.765625 -6.222656 C 5.179688 -6.496094 5.390625 -6.914063 5.394531 -7.484375 C 5.390625 -7.933594 5.238281 -8.308594 4.933594 -8.605469 C 4.628906 -8.898438 4.234375 -9.046875 3.753906 -9.050781 C 3.273438 -9.046875 2.875 -8.894531 2.554688 -8.597656 C 2.234375 -8.292969 2.027344 -7.84375 1.941406 -7.246094 L 0.710938 -7.464844 C 0.859375 -8.289063 1.203125 -8.925781 1.734375 -9.382813 C 2.265625 -9.832031 2.929688 -10.058594 3.726563 -10.0625 C 4.273438 -10.058594 4.773438 -9.941406 5.234375 -9.710938 C 5.691406 -9.472656 6.042969 -9.152344 6.289063 -8.75 C 6.53125 -8.339844 6.65625 -7.910156 6.65625 -7.457031 C 6.65625 -7.023438 6.539063 -6.628906 6.308594 -6.273438 C 6.074219 -5.917969 5.730469 -5.636719 5.277344 -5.429688 C 5.867188 -5.289063 6.328125 -5.003906 6.65625 -4.574219 C 6.984375 -4.140625 7.148438 -3.601563 7.148438 -2.960938 C 7.148438 -2.082031 6.828125 -1.339844 6.191406 -0.734375 C 5.550781 -0.125 4.746094 0.175781 3.773438 0.179688 C 2.890625 0.175781 2.160156 -0.0820313 1.582031 -0.605469 C 1 -1.128906 0.667969 -1.808594 0.585938 -2.644531 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 4.523438 0 L 4.523438 -2.398438 L 0.179688 -2.398438 L 0.179688 -3.527344 L 4.75 -10.023438 L 5.757813 -10.023438 L 5.757813 -3.527344 L 7.109375 -3.527344 L 7.109375 -2.398438 L 5.757813 -2.398438 L 5.757813 0 Z M 4.523438 -3.527344 L 4.523438 -8.046875 L 1.386719 -3.527344 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.582031 -2.625 L 1.875 -2.734375 C 1.96875 -2.101563 2.1875 -1.628906 2.539063 -1.3125 C 2.882813 -0.996094 3.304688 -0.835938 3.800781 -0.839844 C 4.390625 -0.835938 4.890625 -1.058594 5.304688 -1.507813 C 5.710938 -1.953125 5.917969 -2.546875 5.921875 -3.289063 C 5.917969 -3.984375 5.71875 -4.539063 5.328125 -4.949219 C 4.929688 -5.351563 4.414063 -5.554688 3.78125 -5.558594 C 3.382813 -5.554688 3.027344 -5.464844 2.707031 -5.285156 C 2.386719 -5.105469 2.132813 -4.871094 1.953125 -4.585938 L 0.800781 -4.738281 L 1.769531 -9.882813 L 6.753906 -9.882813 L 6.753906 -8.710938 L 2.753906 -8.710938 L 2.214844 -6.015625 C 2.816406 -6.433594 3.445313 -6.644531 4.109375 -6.644531 C 4.980469 -6.644531 5.71875 -6.339844 6.324219 -5.734375 C 6.921875 -5.128906 7.222656 -4.351563 7.226563 -3.398438 C 7.222656 -2.492188 6.960938 -1.707031 6.433594 -1.046875 C 5.789063 -0.234375 4.910156 0.167969 3.800781 0.171875 C 2.886719 0.167969 2.140625 -0.0820313 1.566406 -0.59375 C 0.988281 -1.101563 0.660156 -1.78125 0.582031 -2.625 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-6\">\n",
       "<path style=\"stroke:none;\" d=\"M 6.964844 -7.566406 L 5.742188 -7.472656 C 5.632813 -7.949219 5.476563 -8.300781 5.277344 -8.523438 C 4.941406 -8.871094 4.53125 -9.046875 4.046875 -9.050781 C 3.652344 -9.046875 3.308594 -8.9375 3.015625 -8.722656 C 2.625 -8.4375 2.320313 -8.023438 2.097656 -7.484375 C 1.875 -6.9375 1.757813 -6.167969 1.75 -5.167969 C 2.042969 -5.617188 2.40625 -5.949219 2.835938 -6.171875 C 3.265625 -6.386719 3.714844 -6.496094 4.183594 -6.5 C 5.003906 -6.496094 5.699219 -6.195313 6.277344 -5.59375 C 6.851563 -4.988281 7.140625 -4.207031 7.144531 -3.253906 C 7.140625 -2.621094 7.003906 -2.039063 6.734375 -1.5 C 6.460938 -0.960938 6.089844 -0.546875 5.617188 -0.257813 C 5.140625 0.0273438 4.605469 0.167969 4.007813 0.171875 C 2.980469 0.167969 2.140625 -0.207031 1.496094 -0.960938 C 0.847656 -1.714844 0.527344 -2.957031 0.527344 -4.6875 C 0.527344 -6.625 0.882813 -8.03125 1.601563 -8.914063 C 2.21875 -9.675781 3.058594 -10.058594 4.121094 -10.0625 C 4.90625 -10.058594 5.554688 -9.839844 6.058594 -9.398438 C 6.5625 -8.953125 6.863281 -8.339844 6.964844 -7.566406 Z M 1.941406 -3.246094 C 1.9375 -2.820313 2.027344 -2.414063 2.210938 -2.027344 C 2.386719 -1.640625 2.640625 -1.34375 2.964844 -1.144531 C 3.289063 -0.9375 3.628906 -0.835938 3.984375 -0.839844 C 4.503906 -0.835938 4.949219 -1.046875 5.324219 -1.46875 C 5.695313 -1.886719 5.882813 -2.457031 5.886719 -3.179688 C 5.882813 -3.871094 5.699219 -4.417969 5.332031 -4.816406 C 4.960938 -5.214844 4.496094 -5.414063 3.9375 -5.414063 C 3.378906 -5.414063 2.90625 -5.214844 2.519531 -4.816406 C 2.132813 -4.417969 1.9375 -3.894531 1.941406 -3.246094 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-7\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.664063 -8.710938 L 0.664063 -9.890625 L 7.148438 -9.890625 L 7.148438 -8.933594 C 6.511719 -8.25 5.878906 -7.347656 5.253906 -6.226563 C 4.625 -5.097656 4.140625 -3.941406 3.800781 -2.753906 C 3.550781 -1.914063 3.394531 -0.996094 3.328125 0 L 2.0625 0 C 2.078125 -0.789063 2.230469 -1.738281 2.527344 -2.855469 C 2.820313 -3.96875 3.246094 -5.046875 3.800781 -6.085938 C 4.351563 -7.121094 4.941406 -7.996094 5.570313 -8.710938 Z \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-8\">\n",
       "<path style=\"stroke:none;\" d=\"M 2.476563 -5.433594 C 1.964844 -5.617188 1.585938 -5.886719 1.339844 -6.234375 C 1.089844 -6.578125 0.964844 -6.992188 0.96875 -7.476563 C 0.964844 -8.203125 1.226563 -8.816406 1.753906 -9.316406 C 2.277344 -9.8125 2.976563 -10.058594 3.847656 -10.0625 C 4.71875 -10.058594 5.421875 -9.804688 5.960938 -9.300781 C 6.492188 -8.789063 6.761719 -8.171875 6.761719 -7.445313 C 6.761719 -6.976563 6.636719 -6.570313 6.394531 -6.230469 C 6.148438 -5.882813 5.78125 -5.617188 5.285156 -5.433594 C 5.898438 -5.230469 6.363281 -4.90625 6.6875 -4.460938 C 7.007813 -4.011719 7.171875 -3.480469 7.171875 -2.863281 C 7.171875 -2.003906 6.867188 -1.285156 6.261719 -0.703125 C 5.652344 -0.121094 4.855469 0.167969 3.867188 0.171875 C 2.878906 0.167969 2.082031 -0.121094 1.476563 -0.707031 C 0.867188 -1.289063 0.5625 -2.019531 0.566406 -2.898438 C 0.5625 -3.546875 0.726563 -4.09375 1.0625 -4.535156 C 1.390625 -4.972656 1.863281 -5.269531 2.476563 -5.433594 Z M 2.226563 -7.519531 C 2.226563 -7.042969 2.378906 -6.65625 2.683594 -6.355469 C 2.988281 -6.054688 3.382813 -5.90625 3.875 -5.90625 C 4.34375 -5.90625 4.734375 -6.054688 5.039063 -6.351563 C 5.34375 -6.648438 5.496094 -7.015625 5.496094 -7.453125 C 5.496094 -7.902344 5.339844 -8.28125 5.027344 -8.589844 C 4.714844 -8.894531 4.324219 -9.046875 3.863281 -9.050781 C 3.386719 -9.046875 2.996094 -8.894531 2.691406 -8.597656 C 2.378906 -8.292969 2.226563 -7.933594 2.226563 -7.519531 Z M 1.832031 -2.890625 C 1.828125 -2.539063 1.910156 -2.203125 2.082031 -1.875 C 2.246094 -1.546875 2.496094 -1.289063 2.824219 -1.109375 C 3.152344 -0.925781 3.503906 -0.835938 3.882813 -0.839844 C 4.46875 -0.835938 4.953125 -1.027344 5.339844 -1.40625 C 5.71875 -1.785156 5.910156 -2.265625 5.914063 -2.851563 C 5.910156 -3.441406 5.714844 -3.929688 5.320313 -4.320313 C 4.925781 -4.703125 4.433594 -4.898438 3.84375 -4.902344 C 3.261719 -4.898438 2.78125 -4.707031 2.402344 -4.328125 C 2.019531 -3.941406 1.828125 -3.460938 1.832031 -2.890625 Z \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface66\">\n",
       "<rect x=\"0\" y=\"0\" width=\"350\" height=\"350\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 216.601563 330 L 330 213.890625 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 216.601563 330 L 77.214844 292.976563 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 216.601563 330 L 148.078125 172.070313 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 330 213.890625 L 201.722656 178.292969 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 330 213.890625 L 271.554688 56.273438 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 271.554688 56.273438 L 133.636719 20 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 271.554688 56.273438 L 148.078125 172.070313 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 148.078125 172.070313 L 20 135.445313 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 20 135.445313 L 77.214844 292.976563 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 20 135.445313 L 133.636719 20 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 77.214844 292.976563 L 201.722656 178.292969 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 201.722656 178.292969 L 133.636719 20 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 226.601563 330 C 226.601563 335.523438 222.121094 340 216.601563 340 C 211.078125 340 206.601563 335.523438 206.601563 330 C 206.601563 324.476563 211.078125 320 216.601563 320 C 222.121094 320 226.601563 324.476563 226.601563 330 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 340 213.890625 C 340 219.414063 335.523438 223.890625 330 223.890625 C 324.476563 223.890625 320 219.414063 320 213.890625 C 320 208.367188 324.476563 203.890625 330 203.890625 C 335.523438 203.890625 340 208.367188 340 213.890625 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 281.554688 56.273438 C 281.554688 61.796875 277.078125 66.273438 271.554688 66.273438 C 266.03125 66.273438 261.554688 61.796875 261.554688 56.273438 C 261.554688 50.75 266.03125 46.273438 271.554688 46.273438 C 277.078125 46.273438 281.554688 50.75 281.554688 56.273438 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 158.078125 172.070313 C 158.078125 177.59375 153.601563 182.070313 148.078125 182.070313 C 142.554688 182.070313 138.078125 177.59375 138.078125 172.070313 C 138.078125 166.546875 142.554688 162.070313 148.078125 162.070313 C 153.601563 162.070313 158.078125 166.546875 158.078125 172.070313 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 30 135.445313 C 30 140.96875 25.523438 145.445313 20 145.445313 C 14.476563 145.445313 10 140.96875 10 135.445313 C 10 129.921875 14.476563 125.445313 20 125.445313 C 25.523438 125.445313 30 129.921875 30 135.445313 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 87.214844 292.976563 C 87.214844 298.5 82.738281 302.976563 77.214844 302.976563 C 71.691406 302.976563 67.214844 298.5 67.214844 292.976563 C 67.214844 287.453125 71.691406 282.976563 77.214844 282.976563 C 82.738281 282.976563 87.214844 287.453125 87.214844 292.976563 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(74.509804%,74.509804%,74.509804%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 211.722656 178.292969 C 211.722656 183.816406 207.246094 188.292969 201.722656 188.292969 C 196.199219 188.292969 191.722656 183.816406 191.722656 178.292969 C 191.722656 172.769531 196.199219 168.292969 201.722656 168.292969 C 207.246094 168.292969 211.722656 172.769531 211.722656 178.292969 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(0%,0%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 143.636719 20 C 143.636719 25.523438 139.160156 30 133.636719 30 C 128.113281 30 123.636719 25.523438 123.636719 20 C 123.636719 14.476563 128.113281 10 133.636719 10 C 139.160156 10 143.636719 14.476563 143.636719 20 \"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"213.230469\" y=\"336.53125\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"326.269531\" y=\"220.421875\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-3\" x=\"267.6875\" y=\"62.804688\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-4\" x=\"144.4375\" y=\"178.582031\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-5\" x=\"16.097656\" y=\"141.886719\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-6\" x=\"73.378906\" y=\"299.507813\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-7\" x=\"197.816406\" y=\"184.738281\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-8\" x=\"129.769531\" y=\"26.53125\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x5d7b2f0>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vx_color_dict = {\"Now\": \"red\", \"No\": \"gray\", \"Endpoint\": \"blue\"}\n",
    "\n",
    "layout = cube.layout_auto()\n",
    "visual_style = {}\n",
    "visual_style[\"vertex_size\"] = 20\n",
    "visual_style[\"vertex_color\"] =  [vx_color_dict[here] for here in cube.vs[\"beenthere\"]]\n",
    "visual_style[\"vertex_label\"] = cube.vs[\"name\"]\n",
    "visual_style[\"layout\"] = layout\n",
    "visual_style[\"bbox\"] = (350, 350)\n",
    "visual_style[\"margin\"] = 20\n",
    "plot(cube,  **visual_style)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ant needs to crawl from Node 1 (red) to Node 8 (blue) with 1/g.degree() probability of choosing each of the edges at each of the vertices.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 3, 3, 3, 3, 3, 3, 3]\n",
      "[0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333]\n"
     ]
    }
   ],
   "source": [
    "route_prob = [1.0/dgr for dgr in cube.degree()]\n",
    "print cube.degree()\n",
    "print route_prob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's create our ***ant*** class.\n",
    "\n",
    "It will have 2 **methods**: *update()* and *decide()*.  \n",
    "It will also have to know which three edges it is choosing from.  We will call the class carrying this information ***state***\n",
    "\n",
    "The ***state*** class will keep track of the graph and the current node ID"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]\n",
      "[(0, 1), (0, 5), (0, 3), (1, 6), (1, 2), (2, 7), (2, 3), (3, 4), (4, 5), (4, 7), (5, 6), (6, 7)]\n",
      "(0, 1)\n",
      "0 1\n"
     ]
    }
   ],
   "source": [
    "## Let's first see how edges are represented in igraph:\n",
    "print cube.es.indices\n",
    "all_edges = cube.get_edgelist()\n",
    "print all_edges\n",
    "edge = all_edges[0]\n",
    "print edge\n",
    "print edge[0], edge[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node ID 0\n",
      "My edges: [(0, 1), (0, 5), (0, 3)]\n",
      "My edge probabilities: 0.333333333333\n",
      "\n",
      "node ID 1\n",
      "My edges: [(0, 1), (1, 6), (1, 2)]\n",
      "My edge probabilities: 0.333333333333\n"
     ]
    }
   ],
   "source": [
    "##  Now we can define the class State\n",
    "class State:\n",
    "    node_id = 0\n",
    "    wires = []\n",
    "    probs = []\n",
    "    graph = None\n",
    "    \n",
    "    # The second argument we pass during initialization is the graph of the environment (cube)\n",
    "    def __init__ (self, node_id, g):\n",
    "        self.node_id = node_id\n",
    "        self.graph = g.copy()\n",
    "        self.update()\n",
    "        \n",
    "    def update(self, node_id = node_id):\n",
    "        ##  Assign the new node_id\n",
    "        self.node_id = node_id\n",
    "        self.getMyNewWires()\n",
    "        self.getProbabilities()\n",
    "       \n",
    "    ''' We can later build a derived class from here\n",
    "    with a different getProbabilities() function'''\n",
    "    def getProbabilities (self):\n",
    "        if len (self.wires) == 0:\n",
    "            self.getMyNewWires()\n",
    "        self.probs = 1.0 / len (self.wires)\n",
    "    \n",
    "    def getMyNewWires(self):\n",
    "        mywires = self.wires\n",
    "       \n",
    "        if len(mywires) > 0:\n",
    "            del mywires\n",
    "            mywires = []\n",
    "            \n",
    "        all_edges = self.graph.get_edgelist()\n",
    "        #  print \"all edges of the graph:\", all_edges\n",
    "        for ii in self.graph.es.indices:\n",
    "            edge = all_edges[ii]\n",
    "            # print \"Edge\", edge\n",
    "            if edge[0] == self.node_id or edge[1] == self.node_id:\n",
    "                # print \"Adding edge \", edge, \" to wires\"\n",
    "                mywires.append (edge)\n",
    "        self.wires = mywires    \n",
    "        \n",
    "###   Testing the class:     \n",
    "myState = State (0, cube)\n",
    "print \"node ID %d\" %(myState.node_id)\n",
    "print \"My edges:\", myState.wires     \n",
    "print \"My edge probabilities:\", myState.probs\n",
    "\n",
    "print \"\"\n",
    "## Moving the ant to the next node:\n",
    "myState.update (1)\n",
    "print \"node ID %d\" %(myState.node_id)\n",
    "#The getMyNewWires() is already done in the update() function\n",
    "print \"My edges:\", myState.wires     \n",
    "print \"My edge probabilities:\", myState.probs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have the ***State*** class defined, working, and instantiated, we can define the ***Ant***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created an ant in the following state:\n",
      "Current node ID 0\n",
      "Possible routes: [(0, 1), (0, 5), (0, 3)]\n",
      "Decision Probabilities: 0.333333333333\n",
      "['Now', 'No', 'No', 'No', 'No', 'No', 'No', 'Endpoint']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class Ant:\n",
    "    state = None\n",
    "    arrived_TF = False\n",
    "    \n",
    "    def __init__ (self, mystate):\n",
    "        self.state = mystate\n",
    "        \n",
    "    ## This is the most basic way of selecting random routes: \n",
    "    ## We don't need to build an actual distribution; so we will just pick \n",
    "    ## at random out of the 3 possibilities (bootstrapping)''' \n",
    "    def decide (self):\n",
    "        myNextEdge = random.randrange (0, len (self.state.wires))\n",
    "        print self.state.wires[myNextEdge]\n",
    "        return myNextEdge\n",
    "    \n",
    "    def update(self):\n",
    "        myNextEdge = self.decide()\n",
    "        # we choose the next node_id where the ant is not (the ant never stays on the same node):\n",
    "        whichway = 0\n",
    "        if self.state.node_id == self.state.wires[myNextEdge][whichway]: \n",
    "            whichway = 1\n",
    "            \n",
    "        #print self.state.node_id, self.state.wires[myNextEdge], self.state.wires[myNextEdge][whichway]\n",
    "        myNewNodeID = self.state.wires[myNextEdge][whichway]\n",
    "        self.state.update(myNewNodeID)\n",
    "        if self.state.graph.vs[myNewNodeID][\"beenthere\"] == \"Endpoint\":\n",
    "            print \"Arrived\"\n",
    "            self.arrived_TF = True\n",
    "        self.state.graph.vs[myNewNodeID][\"beenthere\"] = \"Now\"\n",
    "            \n",
    "\n",
    "ant = Ant(myInitState)\n",
    "print \"Created an ant in the following state:\"\n",
    "print \"Current node ID %d\" %(ant.state.node_id)\n",
    "print \"Possible routes:\", ant.state.wires     \n",
    "print \"Decision Probabilities:\", ant.state.probs\n",
    "print ant.state.graph.vs[\"beenthere\"]\n",
    "\n",
    "print \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node ID 0\n",
      "My edges: [(0, 1), (0, 5), (0, 3)]\n",
      "My edge probabilities: 0.333333333333\n",
      "My vertices: ['Now', 'No', 'No', 'No', 'No', 'No', 'No', 'Endpoint']\n"
     ]
    }
   ],
   "source": [
    "myInitState = State (0, cube)\n",
    "print \"node ID %d\" %(myInitState.node_id)\n",
    "print \"My edges:\", myInitState.wires     \n",
    "print \"My edge probabilities:\", myInitState.probs\n",
    "print \"My vertices:\", myInitState.graph.vs[\"beenthere\"]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will iterate through the Ant.update() method until we arrive and increment the counter in the process.  If after 1000 iterations we are still not at the endpoint, we will stop the simulation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Created an ant in the following state:\n",
      "Current node ID 0\n",
      "Possible routes: [(0, 1), (0, 5), (0, 3)]\n",
      "['Now', 'No', 'No', 'No', 'No', 'No', 'No', 'Endpoint']\n",
      "(0, 5)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 5\n",
      "Possible routes: [(0, 5), (4, 5), (5, 6)]\n",
      "['Now', 'No', 'No', 'No', 'No', 'Now', 'No', 'Endpoint']\n",
      "(0, 5)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 0\n",
      "Possible routes: [(0, 1), (0, 5), (0, 3)]\n",
      "['Now', 'No', 'No', 'No', 'No', 'Now', 'No', 'Endpoint']\n",
      "(0, 5)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 5\n",
      "Possible routes: [(0, 5), (4, 5), (5, 6)]\n",
      "['Now', 'No', 'No', 'No', 'No', 'Now', 'No', 'Endpoint']\n",
      "(0, 5)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 0\n",
      "Possible routes: [(0, 1), (0, 5), (0, 3)]\n",
      "['Now', 'No', 'No', 'No', 'No', 'Now', 'No', 'Endpoint']\n",
      "(0, 1)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 1\n",
      "Possible routes: [(0, 1), (1, 6), (1, 2)]\n",
      "['Now', 'Now', 'No', 'No', 'No', 'Now', 'No', 'Endpoint']\n",
      "(1, 6)\n",
      "Updated the ant to the following state:\n",
      "Current node ID 6\n",
      "Possible routes: [(1, 6), (5, 6), (6, 7)]\n",
      "['Now', 'Now', 'No', 'No', 'No', 'Now', 'Now', 'Endpoint']\n",
      "(6, 7)\n",
      "Arrived\n",
      "Updated the ant to the following state:\n",
      "Current node ID 7\n",
      "Possible routes: [(2, 7), (4, 7), (6, 7)]\n",
      "['Now', 'Now', 'No', 'No', 'No', 'Now', 'Now', 'Now']\n",
      "Completed 6 iterations.\n",
      "Arrived =  True\n"
     ]
    }
   ],
   "source": [
    "ant = Ant(myInitState)\n",
    "print \"Created an ant in the following state:\"\n",
    "print \"Current node ID %d\" %(ant.state.node_id)\n",
    "print \"Possible routes:\", ant.state.wires     \n",
    "print ant.state.graph.vs[\"beenthere\"]\n",
    "\n",
    "iter_counter = 0\n",
    "for ii in range (1000):\n",
    "    ant.update()\n",
    "    print \"Updated the ant to the following state:\"\n",
    "    print \"Current node ID %d\" %(ant.state.node_id)\n",
    "    print \"Possible routes:\", ant.state.wires     \n",
    "    print ant.state.graph.vs[\"beenthere\"]\n",
    "    iter_counter = ii\n",
    "    if ant.arrived_TF:\n",
    "        break\n",
    "\n",
    "print \"Completed %d iterations.\" % iter_counter\n",
    "print \"Arrived = \", ant.arrived_TF"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This has been the general illustration of the two most powerful concepts in analytics from the 20th and 21st centuries:\n",
    "\n",
    "###Monte-Carlo simulation\n",
    "\n",
    "###Agent-Based simulation\n",
    "\n",
    "Because we intentionally did not set the seed, each time we rerun the simulation, we will have different numbers of iterations.  With enough simulations (same idea as we used for random forest and other cross-validation techniques), we will converge to the estimate of the true number of minutes the ant will take to arrive."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}