{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Depth-first and breadth-first search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is an implementation of a graph class that uses Python dictionaries to keep track of which nodes connect and which nodes have been explored.  Edges can be added to the graph by calling the ```addEdge``` function.  The neigbhors of a node can be found using the ```getNeighbors``` function.  The ```isExplored``` function returns whether a node has been explored, and the ```setExplored``` function sets a node to have been explored.  The ```resetExplored``` function sets all of the nodes in the graph to be unexplored."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.graph = {}\n",
    "        self.explored = {}\n",
    "\n",
    "    def addEdge(self, fr, to):\n",
    "        if fr not in self.graph:\n",
    "            self.graph[fr] = []\n",
    "            self.explored[fr] = False\n",
    "        if to not in self.graph:\n",
    "            self.graph[to] = []\n",
    "            self.explored[to] = False\n",
    "        self.graph[fr] += [to]\n",
    "\n",
    "    def getNeighbors(self, node):\n",
    "        return self.graph.get(node, [])\n",
    "    \n",
    "    def isExplored(self, node):\n",
    "        return self.explored[node]\n",
    "    \n",
    "    def setExplored(self, node):\n",
    "        self.explored[node] = True\n",
    "        \n",
    "    def resetExplored(self):\n",
    "        for node in self.explored:\n",
    "            self.explored[node] = False\n",
    "            \n",
    "    def __str__(self):\n",
    "        return str(self.graph)\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return str(self.graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now it's your job to implement depth-first and breadth-first search functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DFS: ['a', 'b', 'c', 'd']\n",
      "BFS: ['a', 'b', 'd', 'c']\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "def DFS(graph, node):\n",
    "    graph.resetExplored()\n",
    "    \n",
    "    search_result = []\n",
    "    DFS_helper(graph, node, search_result)\n",
    "    return search_result\n",
    "\n",
    "def DFS_helper(graph, node, search_result):\n",
    "    # Implement this part\n",
    "    pass\n",
    "    \n",
    "\n",
    "def BFS(graph, node):\n",
    "    graph.resetExplored()\n",
    "    \n",
    "    q = deque([node])\n",
    "    search_result = [node]\n",
    "    # Now use q.popleft() and q.append(item) to finish the BFS\n",
    "    while(len(q) > 0):\n",
    "        # Implement this part\n",
    "        break\n",
    "    return search_result\n",
    "\n",
    "\n",
    "# We can construct a graph using the constructor\n",
    "g = Graph()\n",
    "# We can add edges between two nodes using the 'addEdge' function\n",
    "g.addEdge('a', 'b')\n",
    "g.addEdge('a', 'd')\n",
    "g.addEdge('b', 'c')\n",
    "g.addEdge('b', 'd')\n",
    "\n",
    "#Should print [a, b, c, d] once completed\n",
    "print('DFS:', DFS(g, 'a'))\n",
    "\n",
    "#Should print [a, b, d, c] once completed\n",
    "print('BFS:', BFS(g, 'a'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://www.cs.colostate.edu/~cs220/fall17/recitations/recit15/graph.png)\n",
    "Create a representation of this graph in the code, and perform depth-first and breadth-first searches from nodes 'a' and 'f'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bonus\n",
    "================\n",
    "\n",
    "Create a new class Tree that does not allow cycles. You can check for cycles by doing a depth-first search, and returning if a colored node is reached at any point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}