{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sebastian Raschka \n",
      "last updated: 2017-08-06 \n",
      "\n",
      "CPython 3.6.1\n",
      "IPython 6.1.0\n"
     ]
    }
   ],
   "source": [
    "%load_ext watermark\n",
    "%watermark -a 'Sebastian Raschka' -u -d -v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Breadth-First Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Breadt-first search (BFS) is algorithm that can find the closest members in a graph that match a certain search criterion.\n",
    "\n",
    "BFS requires that we model our problem as a graph (*nodes* connected through *edges*). BFS can be applied to directed and undirected graph, where it can be applied to answer to types of question:\n",
    "\n",
    "1. Is there are connection between a particular pair of nodes?\n",
    "2. Which is the closest node to a given node that satisfies a certain criterion?\n",
    "\n",
    "To answer these questions, BFS starts by checking all direct neighbors of a given node -- neighbors are nodes that have a direct connection to a particular node. Then, if none of those neighbors satisfies the criterion that we are looking for, the search is expanded to the neighbors of the nodes we just checked, and so on, until a match is found or all nodes in the graph were checked.\n",
    "\n",
    "To keep track of the nodes that we have already checked and that we are going to check, we need two additional data structures: \n",
    "\n",
    "1) A hash table to keep track of nodes we have already checked. If we don't check for previously checked nodes, we may end up in cycles depending on the structure of the graph.\n",
    "\n",
    "2) A queue that stores the items to be checked."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Representing the graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To represent the graph, its nodes and edges, we can simply use a hash table such as Python's built-in dictionaries. Imagine we have an undirected, social network graph that lists our direct friends (Elijah, Marissa, Nikolai) and friends of friends:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/breadth-first-search/friend-graph-1.jpg\" alt=\"\" style=\"width: 400px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say we are going to move to a new apartment next weekend, and we want to ask our friends if they have a pick-up truck that can be helpful in this endeavor. First, we would reach out to our directed friends (or 1st degree connections). If none of these have a pick-up truck, we ask them to ask their 1st degree connections (which are our 2nd degree connections), and so forth:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/breadth-first-search/friend-graph-2.jpg\" alt=\"\" style=\"width: 600px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can represent such a graph using a simple hash table (here: Python dictionary) as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph = {}\n",
    "\n",
    "graph['You'] = ['Elijah', 'Marissa', 'Nikolai', 'Cassidy']\n",
    "graph['Elijah'] = ['You']\n",
    "graph['Marissa'] = ['You']\n",
    "graph['Nikolai'] = ['John', 'Thomas', 'You']\n",
    "graph['Cassidy'] = ['John', 'You']\n",
    "graph['John'] = ['Cassidy', 'Nikolai']\n",
    "graph['Thomas'] = ['Nikolai', 'Mario']\n",
    "graph['Mario'] = ['Thomas']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Queue data structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let's setup a simple queue data structure. Of course, we can also use a regular Python list like a queue (using `.insert(0, x)` and `.pop()`, but this way, our breadth-first search implementation is maybe more illustrative. For more information about queues, please see the [Queues and Deques notebook](http://nbviewer.ipython.org/github/rasbt/algorithms_in_ipython_notebooks/blob/master/ipython_nbs/data-structures/queues-and-deques.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QueueItem():\n",
    "    def __init__(self, value, pointer=None):\n",
    "        self.value = value\n",
    "        self.pointer = pointer\n",
    "\n",
    "class Queue():\n",
    "    def __init__(self):\n",
    "        self.last = None\n",
    "        self.first = None\n",
    "        self.length = 0\n",
    "    \n",
    "    def enqueue(self, value):\n",
    "        item = QueueItem(value, None)\n",
    "        if self.last:\n",
    "            self.last.pointer = item\n",
    "        if not self.first:\n",
    "            self.first = item\n",
    "        self.last = item\n",
    "        self.length += 1\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.first is not None:\n",
    "            value = self.first.value\n",
    "            self.first = self.first.pointer\n",
    "            self.length -= 1\n",
    "        else:\n",
    "            value = None\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First element: a\n",
      "Last element: a\n",
      "Queue length: 1\n"
     ]
    }
   ],
   "source": [
    "qe = Queue()\n",
    "qe.enqueue('a')\n",
    "\n",
    "print('First element:', qe.first.value)\n",
    "print('Last element:', qe.last.value)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First element: a\n",
      "Last element: b\n",
      "Queue length: 2\n"
     ]
    }
   ],
   "source": [
    "qe.enqueue('b')\n",
    "\n",
    "print('First element:', qe.first.value)\n",
    "print('Last element:', qe.last.value)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First element: a\n",
      "Last element: c\n",
      "Queue length: 3\n"
     ]
    }
   ],
   "source": [
    "qe.enqueue('c')\n",
    "\n",
    "print('First element:', qe.first.value)\n",
    "print('Last element:', qe.last.value)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dequeued value: a\n",
      "Queue length: 2\n"
     ]
    }
   ],
   "source": [
    "val = qe.dequeue()\n",
    "\n",
    "print('Dequeued value:', val)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dequeued value: b\n",
      "Queue length: 1\n"
     ]
    }
   ],
   "source": [
    "val = qe.dequeue()\n",
    "\n",
    "print('Dequeued value:', val)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dequeued value: c\n",
      "Queue length: 0\n"
     ]
    }
   ],
   "source": [
    "val = qe.dequeue()\n",
    "\n",
    "print('Dequeued value:', val)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dequeued value: None\n",
      "Queue length: 0\n"
     ]
    }
   ],
   "source": [
    "val = qe.dequeue()\n",
    "\n",
    "print('Dequeued value:', val)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First element: c\n",
      "Last element: c\n",
      "Queue length: 1\n"
     ]
    }
   ],
   "source": [
    "qe.enqueue('c')\n",
    "\n",
    "print('First element:', qe.first.value)\n",
    "print('Last element:', qe.last.value)\n",
    "print('Queue length:', qe.length)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing freadth-first search to find the shortest path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, back to the graph, where we want to identify the closest connection that owns a truck, which can be helpful for moving (if we are allowed to borrow it, that is):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/breadth-first-search/friend-graph-2.jpg\" alt=\"\" style=\"width: 600px;\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph = {}\n",
    "\n",
    "graph['You'] = ['Elijah', 'Marissa', 'Nikolai', 'Cassidy']\n",
    "graph['Elijah'] = ['You']\n",
    "graph['Marissa'] = ['You']\n",
    "graph['Nikolai'] = ['John', 'Thomas', 'You']\n",
    "graph['Cassidy'] = ['John', 'You']\n",
    "graph['John'] = ['Cassidy', 'Nikolai']\n",
    "graph['Thomas'] = ['Nikolai', 'Mario']\n",
    "graph['Mario'] = ['Thomas']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For simplicity, let's assume we have function that checks if a person ows a pick-up truck. (Say, Mario owns a pick-up truck, the check function knows it but we don't know it.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def has_truck(person):\n",
    "    if person == 'Mario':\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the `breadth_first_search` implementation below will check our closest neighbors first, then, it will check the neighnors of our neighbors and so forth. We will make use both of the graph we constructed and the `Queue` data structure that we implemented. Also, note that we are keeping track of people we already checked to prevent cycles in our search:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def breadth_first_search(graph):\n",
    "\n",
    "    # initialize queue\n",
    "    queue = Queue()\n",
    "    for person in graph['You']:\n",
    "        queue.enqueue(person)\n",
    "\n",
    "    people_checked = set()\n",
    "    degree = 0\n",
    "    \n",
    "    while queue.length:\n",
    "        \n",
    "        person = queue.dequeue()\n",
    "\n",
    "        if has_truck(person):\n",
    "            return person\n",
    "        else:\n",
    "            degree += 1\n",
    "            people_checked.add(person)\n",
    "            for next_person in graph[person]:\n",
    "                # check to prevent endless cycles\n",
    "                if next_person not in people_checked:\n",
    "                    queue.enqueue(next_person)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Mario'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "breadth_first_search(graph)"
   ]
  }
 ],
 "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
}