s20/lab6/student-search-examples.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import display, HTML\n",
    "from graphviz import Digraph\n",
    "\n",
    "class test_graph:\n",
    "    def __init__(self):\n",
    "        self.nodes = {}\n",
    "        self.traverse_order = None # in what order were nodes checked?\n",
    "        self.next_guess = 0\n",
    "        self.colors = {}\n",
    "\n",
    "    def node(self, name):\n",
    "        name = str(name).upper()\n",
    "        self.nodes[name] = Node(self, name)\n",
    "\n",
    "    def edge(self, src, dst):\n",
    "        src, dst = str(src).upper(), str(dst).upper()\n",
    "        for name in [src, dst]:\n",
    "            if not name in self.nodes:\n",
    "                self.node(name)\n",
    "        self.nodes[src].children.append(self.nodes[dst])\n",
    "\n",
    "    def _repr_svg_(self):\n",
    "        g = Digraph(engine='neato')\n",
    "        for n in self.nodes:\n",
    "            g.node(n, fillcolor=self.colors.get(n, \"white\"), style=\"filled\")\n",
    "            children = self.nodes[n].children\n",
    "            for i, child in enumerate(children):\n",
    "                g.edge(n, child.name, penwidth=str(len(children) - i), len=\"1.2\")\n",
    "        return g._repr_svg_()\n",
    "\n",
    "    def dfs(self, src, dst):\n",
    "        src, dst = str(src).upper(), str(dst).upper()\n",
    "        self.traverse_order = []\n",
    "        self.next_guess = 0\n",
    "        self.colors = {}\n",
    "        self.visited = set()\n",
    "        self.path = self.nodes[src].dfs(dst)\n",
    "        display(HTML(\"now call .visit(???) to identify the first node explored\"))\n",
    "        display(self)\n",
    "\n",
    "    def bfs(self, src, dst):\n",
    "        src, dst = str(src).upper(), str(dst).upper()\n",
    "        self.traverse_order = []\n",
    "        self.next_guess = 0\n",
    "        self.colors = {}\n",
    "        self.path = self.nodes[src].bfs(dst)\n",
    "        display(HTML(\"now call .visit(???) to identify the first node explored\"))\n",
    "        display(self)\n",
    "    \n",
    "    def visit(self, name):\n",
    "        name = str(name).upper()\n",
    "        if self.traverse_order == None:\n",
    "            print(\"please call dfs or bfs first\")\n",
    "        if self.next_guess == len(self.traverse_order):\n",
    "            print(\"no more nodes to explore\")\n",
    "            return\n",
    "        self.colors = {}\n",
    "        for n in self.traverse_order[:self.next_guess]:\n",
    "            self.colors[n] = \"yellow\"\n",
    "        if name == self.traverse_order[self.next_guess]:\n",
    "            display(HTML(\"Correct...\"))\n",
    "            self.colors[name] = \"yellow\"\n",
    "            self.next_guess += 1\n",
    "        else:\n",
    "            display(HTML(\"<b>Oops!</b> Please guess again.\"))\n",
    "            self.colors[name] = \"red\"\n",
    "        display(self)\n",
    "        if self.next_guess == len(self.traverse_order):\n",
    "            if self.path == None:\n",
    "                display(HTML(\"You're done, there is no path!\"))\n",
    "            else:\n",
    "                seq = input(\"What path was found? [enter nodes, comma separated]: \")\n",
    "                seq = tuple(map(str.strip, seq.upper().split(\",\")))\n",
    "                if seq == tuple(map(str.upper, self.path)):\n",
    "                    print(\"Awesome!!!\")\n",
    "                else:\n",
    "                    print(\"actually, expected was: \", \",\".join(self.path))\n",
    "\n",
    "    \n",
    "class Node:\n",
    "    def __init__(self, graph, name):\n",
    "        self.graph = graph\n",
    "        self.name = name\n",
    "        self.children = []\n",
    "\n",
    "    def __repr__(self):\n",
    "        return \"node %s\" % self.name\n",
    "\n",
    "    def dfs(self, dst):\n",
    "        if self.name in self.graph.visited:\n",
    "            return None\n",
    "        \n",
    "        self.graph.traverse_order.append(self.name)\n",
    "        \n",
    "        self.graph.visited.add(self.name)\n",
    "\n",
    "        if self.name == dst:\n",
    "            return (self.name, )\n",
    "        for child in self.children:\n",
    "            childpath = child.dfs(dst)\n",
    "            if childpath:\n",
    "                return (self.name, ) + childpath\n",
    "        return None\n",
    "\n",
    "    def backtrace(self):\n",
    "        nodes = []\n",
    "        node = self\n",
    "        while node != None:\n",
    "            nodes.append(node.name)\n",
    "            node = node.back\n",
    "        return tuple(reversed(nodes))\n",
    "\n",
    "    def bfs(self, dst):\n",
    "        added = set()\n",
    "        todo = [self]\n",
    "        self.back = None\n",
    "        added.add(self.name)\n",
    "\n",
    "        while len(todo) > 0:\n",
    "            curr = todo.pop(0)\n",
    "            self.graph.traverse_order.append(curr.name)\n",
    "\n",
    "            if curr.name == dst:\n",
    "                return curr.backtrace()\n",
    "            else:\n",
    "                for child in curr.children:\n",
    "                    if not child.name in added:\n",
    "                        todo.append(child)\n",
    "                        child.back = curr\n",
    "                        added.add(child.name)\n",
    "\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"148pt\" height=\"286pt\"\n",
       " viewBox=\"0.00 0.00 148.06 285.53\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 281.53)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-281.53 144.06,-281.53 144.06,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-97.23\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-93.03\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"106.54\" cy=\"-184.54\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"106.54\" y=\"-180.34\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M41.22,-112.84C53.55,-126.37 71.56,-146.14 85.55,-161.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"83.12,-164.03 92.45,-169.07 88.3,-159.32 83.12,-164.03\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"68.16\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"68.16\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.93,-80.03C41.38,-69.55 48.45,-55.94 54.58,-44.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.74,-45.64 59.24,-35.16 51.53,-42.42 57.74,-45.64\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"59.92\" cy=\"-259.53\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"59.92\" y=\"-255.33\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M96.2,-201.18C90.2,-210.83 82.53,-223.16 75.79,-234.01\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.71,-232.34 70.4,-242.68 78.65,-236.03 72.71,-232.34\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"113.06\" cy=\"-94.61\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.06\" y=\"-90.41\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M78.12,-35C83.94,-44.92 91.39,-57.63 97.91,-68.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"95.04,-70.8 103.12,-77.65 101.08,-67.26 95.04,-70.8\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"29.01\" cy=\"-176.54\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"29.01\" y=\"-172.34\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.37,-241.93C49.23,-230.82 43.8,-216.24 39.11,-203.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"42.33,-202.27 35.56,-194.12 35.77,-204.71 42.33,-202.27\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M97.64,-109.64C84.73,-122.23 66.12,-140.37 51.54,-154.59\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"49.05,-152.13 44.33,-161.61 53.93,-157.14 49.05,-152.13\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11008e2e8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "g.edge(1, 2)\n",
    "g.edge(1, 3)\n",
    "g.edge(2, 4)\n",
    "g.edge(3, 5)\n",
    "g.edge(5, 6)\n",
    "g.edge(4, 6)\n",
    "g.bfs(1, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"273pt\" height=\"283pt\"\n",
       " viewBox=\"0.00 0.00 272.96 283.10\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 279.1)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-279.1 268.96,-279.1 268.96,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"153.45\" cy=\"-188.54\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"153.45\" y=\"-184.34\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"158.65\" cy=\"-114.31\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"158.65\" y=\"-110.11\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M154.74,-170.19C155.32,-161.83 156.03,-151.74 156.68,-142.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"160.17,-142.66 157.38,-132.44 153.19,-142.17 160.17,-142.66\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"237.96\" cy=\"-113.6\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"237.96\" y=\"-109.4\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M169.75,-174.09C182.26,-163 199.72,-147.51 213.85,-134.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"216.56,-137.26 221.72,-128 211.91,-132.02 216.56,-137.26\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"55.12\" cy=\"-181.46\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"55.12\" y=\"-177.26\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M126.58,-186.6C116.05,-185.85 103.78,-184.96 92.41,-184.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"92.53,-180.64 82.3,-183.42 92.02,-187.63 92.53,-180.64\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"95.91\" cy=\"-257.1\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"95.91\" y=\"-252.9\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.7,-201.68C126.38,-210.12 116.84,-221.26 109.25,-231.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"106.37,-229.37 103.39,-239.54 112.06,-233.45 106.37,-229.37\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"231.48\" cy=\"-185.14\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"231.48\" y=\"-180.94\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>2&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-129.33C184.14,-139.1 197.41,-152 208.66,-162.94\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"206.45,-165.68 216.06,-170.14 211.33,-160.66 206.45,-165.68\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.33,-131.65C235.64,-139.22 234.83,-148.2 234.07,-156.63\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"230.56,-156.57 233.14,-166.85 237.53,-157.2 230.56,-156.57\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M64.38,-198.63C69.54,-208.2 76.08,-220.32 81.86,-231.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"78.87,-232.87 86.69,-240.01 85.03,-229.54 78.87,-232.87\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-86.87\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-82.67\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>4&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M49.83,-163.67C45.71,-149.8 39.91,-130.29 35.19,-114.4\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"38.47,-113.17 32.27,-104.58 31.76,-115.17 38.47,-113.17\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;1 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.67,-243.96C122.99,-235.52 132.52,-224.38 140.12,-214.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"142.99,-216.27 145.98,-206.1 137.3,-212.18 142.99,-216.27\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M204.19,-186.33C199.89,-186.52 195.38,-186.71 190.9,-186.91\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"190.43,-183.43 180.6,-187.36 190.74,-190.42 190.43,-183.43\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"111.58\" cy=\"-34.95\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"111.58\" y=\"-30.75\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M47.04,-74.57C57.79,-67.97 71.21,-59.73 83.03,-52.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"84.99,-55.38 91.68,-47.17 81.33,-49.41 84.99,-55.38\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;2 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>9&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M121.56,-51.78C127.93,-62.51 136.3,-76.62 143.48,-88.73\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"140.57,-90.68 148.68,-97.5 146.59,-87.11 140.57,-90.68\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"205.84\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"205.84\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M138.67,-36.28C149.47,-35.05 162,-32.93 173.29,-30.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"174.3,-33.81 183.23,-28.1 172.69,-27 174.3,-33.81\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;3 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>10&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M211.88,-35.98C216.67,-50.23 223.43,-70.35 228.87,-86.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"225.55,-87.66 232.06,-96.02 232.19,-85.43 225.55,-87.66\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;9 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>10&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M178.75,-16.67C167.95,-17.9 155.42,-20.02 144.13,-22.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"143.12,-19.13 134.19,-24.84 144.73,-25.95 143.12,-19.13\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11006ab00>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# designed by anonymous\n",
    "g = test_graph()\n",
    "g.edge(1,2)\n",
    "g.edge(1,3)\n",
    "g.edge(1,4)\n",
    "g.edge(2, 5)\n",
    "g.edge(3,5)\n",
    "g.edge(5,1)\n",
    "g.edge(6,1)\n",
    "g.edge(4,6)\n",
    "g.edge(4,8)\n",
    "g.edge(8,9)\n",
    "g.edge(9,2)\n",
    "g.edge(9,10)\n",
    "g.edge(10,9)\n",
    "g.edge(10,3)\n",
    "g.edge(1,6)\n",
    "g.bfs(2,10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"353pt\" height=\"411pt\"\n",
       " viewBox=\"0.00 0.00 353.16 411.11\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 407.11)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-407.11 349.16,-407.11 349.16,4 -4,4\"/>\n",
       "<!-- 2 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"223.14\" cy=\"-374.99\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"223.14\" y=\"-370.79\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"261\" cy=\"-300.07\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"261\" y=\"-295.87\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M231.92,-357.61C236.6,-348.34 242.46,-336.75 247.69,-326.4\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"250.88,-327.85 252.27,-317.35 244.63,-324.7 250.88,-327.85\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"201.92\" cy=\"-280.55\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"201.92\" y=\"-276.35\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M219.05,-356.78C215.97,-343.1 211.71,-324.13 208.21,-308.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"211.53,-307.37 205.93,-298.38 204.7,-308.91 211.53,-307.37\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"200.11\" cy=\"-204.72\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"200.11\" y=\"-200.52\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M250.4,-283.46C241.02,-268.78 227.21,-247.15 216.43,-230.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.13,-228 210.8,-221.46 213.23,-231.77 219.13,-228\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M226.29,-288.6C226.51,-288.67 226.72,-288.74 226.94,-288.81\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"226.09,-292.22 236.69,-292.03 228.29,-285.57 226.09,-292.22\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M227.36,-287.24C237.95,-287.7 246.92,-285.47 246.92,-280.55 246.92,-277.32 243.06,-275.25 237.41,-274.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"237.52,-270.84 227.36,-273.86 237.18,-277.83 237.52,-270.84\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M201.48,-262.19C201.27,-253.44 201.02,-242.77 200.78,-233.01\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"204.28,-232.82 200.54,-222.91 197.28,-232.99 204.28,-232.82\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"114.61\" cy=\"-252.45\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.61\" y=\"-248.25\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M177.6,-272.72C168.69,-269.86 158.43,-266.55 148.81,-263.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"149.69,-260.07 139.1,-260.34 147.55,-266.73 149.69,-260.07\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"171.53\" cy=\"-110.35\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"171.53\" y=\"-106.15\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;7 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M194.73,-186.97C190.54,-173.13 184.65,-153.67 179.85,-137.82\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"183.13,-136.58 176.88,-128.02 176.43,-138.61 183.13,-136.58\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"306.77\" cy=\"-385.11\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"306.77\" y=\"-380.91\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M279.84,-381.85C273.52,-381.08 266.66,-380.25 259.98,-379.44\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"260.07,-375.93 249.72,-378.2 259.23,-382.88 260.07,-375.93\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M297.51,-367.9C291.05,-355.91 282.33,-339.7 275.03,-326.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"278.07,-324.4 270.25,-317.25 271.91,-327.72 278.07,-324.4\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M135.74,-240.65C146.2,-234.82 159,-227.67 170.42,-221.29\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"172.19,-224.32 179.22,-216.38 168.78,-218.2 172.19,-224.32\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"318.16\" cy=\"-254.44\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"318.16\" y=\"-250.24\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;4 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>9&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M292.37,-260.23C276.26,-263.85 255.3,-268.56 237.62,-272.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"236.64,-269.16 227.65,-274.77 238.17,-275.99 236.64,-269.16\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-213.61\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-209.41\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;6 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>8&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M49.56,-223.61C59.68,-228.1 71.79,-233.47 82.8,-238.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"81.56,-241.63 92.12,-242.48 84.4,-235.23 81.56,-241.63\"/>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>16</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"278.11\" cy=\"-142.78\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"278.11\" y=\"-138.58\" font-family=\"Times,serif\" font-size=\"14.00\">16</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;5 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>16&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M260.41,-156.83C250.07,-165.05 236.84,-175.55 225.41,-184.63\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"223.12,-181.97 217.47,-190.93 227.48,-187.46 223.12,-181.97\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"162.91\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"162.91\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;7 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>10&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M164.61,-36.25C165.83,-49.27 167.49,-67.05 168.88,-81.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"165.42,-82.51 169.83,-92.14 172.39,-81.86 165.42,-82.51\"/>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>25</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"45.72\" cy=\"-323.3\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.72\" y=\"-319.1\" font-family=\"Times,serif\" font-size=\"14.00\">25</text>\n",
       "</g>\n",
       "<!-- 25&#45;&gt;6 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>25&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M60.67,-307.92C69.97,-298.36 82.09,-285.89 92.49,-275.2\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"95.23,-277.4 99.69,-267.8 90.21,-272.52 95.23,-277.4\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11006ac88>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "for i in range(1, 6, 1):\n",
    "    g.edge(2*i, i+2)\n",
    "    g.edge(i, i+2)\n",
    "    g.edge(i**2, i+1)\n",
    "g.edge(4, 5)\n",
    "g.bfs(1, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"258pt\" height=\"256pt\"\n",
       " viewBox=\"0.00 0.00 258.48 255.98\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 251.98)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-251.98 254.48,-251.98 254.48,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"117.56\" cy=\"-140.72\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"117.56\" y=\"-136.52\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"223.48\" cy=\"-172.09\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"223.48\" y=\"-167.89\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"7\" d=\"M142.39,-148.07C156.33,-152.2 173.94,-157.42 189.19,-161.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"7\" points=\"187.47,-167.81 198.8,-164.78 190.95,-156.07 187.47,-167.81\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"199.78\" cy=\"-110.86\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"199.78\" y=\"-106.66\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"6\" d=\"M141.34,-132.08C149.18,-129.23 158.05,-126.01 166.47,-122.96\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"6\" points=\"168.44,-127.83 176.05,-119.48 164.86,-117.96 168.44,-127.83\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"161.72\" cy=\"-206.53\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"161.72\" y=\"-202.33\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"5\" d=\"M128.7,-157.32C133.58,-164.59 139.41,-173.29 144.81,-181.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"5\" points=\"141.22,-183.83 150.42,-189.7 148.48,-178.96 141.22,-183.83\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"81.41\" cy=\"-229.98\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"81.41\" y=\"-225.78\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;5 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M110.42,-158.35C105.27,-171.07 98.22,-188.46 92.37,-202.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"89.05,-201.8 88.54,-212.38 95.54,-204.42 89.05,-201.8\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-168.08\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-163.88\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M92.81,-148.19C83.13,-151.12 71.86,-154.53 61.4,-157.68\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"60.27,-154.37 51.71,-160.61 62.3,-161.07 60.27,-154.37\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"44.41\" cy=\"-85.37\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"44.41\" y=\"-81.17\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;7 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>1&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M99.47,-127.03C90.71,-120.4 80.01,-112.31 70.39,-105.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"72.37,-102.13 62.28,-98.89 68.14,-107.72 72.37,-102.13\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"112.79\" cy=\"-40.97\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"112.79\" y=\"-36.77\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;8 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>1&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M116.68,-122.42C115.97,-107.52 114.95,-86.22 114.14,-69.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"117.63,-68.97 113.66,-59.15 110.64,-69.31 117.63,-68.97\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M216.62,-154.38C214.64,-149.26 212.43,-143.55 210.28,-137.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"213.41,-136.38 206.54,-128.32 206.88,-138.91 213.41,-136.38\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M192.8,-128.41C187.11,-142.71 178.98,-163.13 172.47,-179.51\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"169.1,-178.51 168.65,-189.1 175.6,-181.1 169.1,-178.51\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"201.89\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"201.89\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>3&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M200.2,-92.52C200.5,-79.42 200.9,-61.54 201.24,-46.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"204.75,-46.39 201.48,-36.31 197.75,-46.23 204.75,-46.39\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M136.75,-213.82C130.25,-215.72 123.13,-217.8 116.23,-219.81\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"114.98,-216.53 106.37,-222.69 116.95,-223.25 114.98,-216.53\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M67.68,-214.36C61.67,-207.52 54.49,-199.35 47.84,-191.78\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"50.15,-189.11 40.92,-183.91 44.89,-193.73 50.15,-189.11\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M30.78,-150.13C33.04,-139.4 35.95,-125.54 38.51,-113.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"42,-113.79 40.64,-103.28 35.15,-112.34 42,-113.79\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M63.82,-72.76C70.26,-68.58 77.57,-63.84 84.54,-59.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"86.61,-62.14 93.09,-53.76 82.8,-56.27 86.61,-62.14\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M138.09,-34.45C147.02,-32.15 157.24,-29.51 166.84,-27.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"167.73,-30.42 176.54,-24.54 165.98,-23.65 167.73,-30.42\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11008ed68>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "\n",
    "for i in range(2,9):\n",
    "    g.edge(1,i)\n",
    "    if i == 2:\n",
    "        g.edge(2,3)\n",
    "        continue\n",
    "    if i == 3:\n",
    "        g.edge(3,9)\n",
    "    g.edge(i,  i+1)\n",
    "    \n",
    "g.dfs(1,9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"340pt\" height=\"322pt\"\n",
       " viewBox=\"0.00 0.00 340.12 321.93\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 317.93)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-317.93 336.12,-317.93 336.12,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"166.61\" cy=\"-159.35\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"166.61\" y=\"-155.15\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"250.32\" cy=\"-141.14\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"250.32\" y=\"-136.94\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"6\" d=\"M193.98,-159.84C201.99,-158.58 210.82,-156.76 219.05,-154.7\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"6\" points=\"220.44,-159.76 228.72,-152.07 217.69,-149.63 220.44,-159.76\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"189.93\" cy=\"-75.93\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"189.93\" y=\"-71.73\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"5\" d=\"M177.29,-142.37C181.52,-131.43 185.78,-116.93 188.59,-104.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"5\" points=\"192.94,-104.84 190.57,-94.18 184.35,-103.15 192.94,-104.84\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"105.12\" cy=\"-96.13\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.12\" y=\"-91.93\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M157.61,-142.01C151.05,-133.77 141.94,-123.96 133.12,-115.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"135.24,-112.69 125.52,-108.48 130.49,-117.83 135.24,-112.69\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"79.99\" cy=\"-179.2\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"79.99\" y=\"-175\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M139.23,-159.22C130.34,-160.7 120.42,-162.86 111.28,-165.29\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"110.04,-162 101.38,-168.12 111.96,-168.73 110.04,-162\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"140.56\" cy=\"-242.28\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"140.56\" y=\"-238.08\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>0&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M155.37,-176.04C150.76,-186.96 145.99,-201.49 142.76,-214.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"139.27,-213.72 140.46,-224.24 146.1,-215.28 139.27,-213.72\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"226.9\" cy=\"-226.43\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"226.9\" y=\"-222.23\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>0&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.69,-176.63C181.33,-185.74 190.9,-196.88 200.08,-206.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"197.74,-208.95 207.3,-213.52 202.67,-203.99 197.74,-208.95\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>1&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M222.95,-140.64C214.94,-141.9 206.11,-143.72 197.87,-145.79\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"196.94,-142.41 188.21,-148.41 198.78,-149.17 196.94,-142.41\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M241.91,-123.82C235.37,-115.15 226.11,-104.68 217.18,-95.71\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"219.44,-93.04 209.82,-88.6 214.58,-98.07 219.44,-93.04\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M239.76,-158.14C235.4,-169.58 230.97,-184.93 228.12,-198.18\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"224.64,-197.76 226.2,-208.24 231.51,-199.07 224.64,-197.76\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"305.12\" cy=\"-101.59\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"305.12\" y=\"-97.39\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;7 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>1&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.91,-132.14C277.63,-129.74 281.45,-127.06 285.08,-124.32\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"287.5,-126.86 293.09,-117.87 283.11,-121.41 287.5,-126.86\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;0 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>2&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M179.24,-92.9C175.02,-103.85 170.75,-118.35 167.95,-131.01\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"164.46,-130.61 165.96,-141.1 171.33,-131.96 164.46,-130.61\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>2&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M198.34,-93.24C204.88,-101.91 214.14,-112.38 223.07,-121.35\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"220.8,-124.03 230.42,-128.46 225.67,-118.99 220.8,-124.03\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M162.57,-76C154.12,-77.49 144.75,-79.62 136.08,-81.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"134.91,-78.69 126.31,-84.87 136.89,-85.4 134.91,-78.69\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"215.06\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"215.06\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;8 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>2&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M203.69,-60.12C206.08,-55.59 208.41,-50.52 210.42,-45.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"213.71,-46.69 213.83,-36.09 207.13,-44.3 213.71,-46.69\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;0 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>3&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M114.12,-113.47C120.68,-121.71 129.79,-131.52 138.61,-139.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"136.49,-142.79 146.21,-147.01 141.24,-137.65 136.49,-142.79\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;2 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>3&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M132.48,-96.06C140.93,-94.57 150.29,-92.45 158.97,-90.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"160.14,-93.38 168.74,-87.19 158.16,-86.66 160.14,-93.38\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M94.07,-112.91C89.58,-123.86 84.96,-138.41 81.88,-151.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"78.39,-150.67 79.69,-161.19 85.23,-152.16 78.39,-150.67\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"90.4\" cy=\"-36.43\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"90.4\" y=\"-32.23\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;9 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>3&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106.97,-78.04C106.27,-73.21 105.17,-67.9 103.83,-62.74\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"107.18,-61.74 100.98,-53.15 100.47,-63.73 107.18,-61.74\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;0 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>4&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M107.37,-179.33C116.25,-177.85 126.17,-175.68 135.32,-173.26\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"136.56,-176.54 145.22,-170.43 134.64,-169.81 136.56,-176.54\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>4&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M91.04,-162.42C95.53,-151.47 100.14,-136.92 103.23,-124.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"106.72,-124.66 105.42,-114.14 99.88,-123.17 106.72,-124.66\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M88.77,-196.48C95.22,-204.7 104.18,-214.49 112.88,-222.94\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"110.68,-225.67 120.38,-229.95 115.46,-220.56 110.68,-225.67\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-150.1\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-145.9\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;10 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>4&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M65.43,-163.89C64.16,-163.08 62.85,-162.26 61.51,-161.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"62.84,-158.2 52.4,-156.44 59.46,-164.33 62.84,-158.2\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;0 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>5&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M151.8,-225.59C156.41,-214.67 161.18,-200.14 164.41,-187.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"167.9,-187.91 166.71,-177.39 161.07,-186.35 167.9,-187.91\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>5&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M131.78,-225C125.33,-216.78 116.36,-206.99 107.67,-198.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"109.87,-195.8 100.17,-191.53 105.09,-200.92 109.87,-195.8\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M167.59,-243.67C176.11,-242.63 185.61,-241.01 194.47,-239.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"195.54,-242.44 204.47,-236.74 193.93,-235.63 195.54,-242.44\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"82.47\" cy=\"-269.87\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"82.47\" y=\"-265.67\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;11 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>5&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.42,-247.35C112.15,-248.33 109.85,-249.38 107.58,-250.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"105.82,-247.44 98.58,-255.17 109.06,-253.65 105.82,-247.44\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;0 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>6&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M218.83,-209.15C212.19,-200.04 202.61,-188.9 193.43,-179.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"195.78,-176.83 186.22,-172.26 190.84,-181.79 195.78,-176.83\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;1 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>6&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M237.46,-209.42C241.82,-197.98 246.25,-182.64 249.1,-169.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"252.58,-169.8 251.02,-159.33 245.71,-168.49 252.58,-169.8\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"5\" d=\"M199.87,-225.04C191.35,-226.08 181.85,-227.7 173,-229.61\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"5\" points=\"171.72,-225.42 162.99,-231.97 173.73,-233.94 171.72,-225.42\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"207.62\" cy=\"-295.93\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"207.62\" y=\"-291.73\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;12 -->\n",
       "<g id=\"edge30\" class=\"edge\">\n",
       "<title>6&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M216.03,-243.08C213.2,-250.55 210.52,-259.56 208.56,-268\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"205.11,-267.4 206.56,-277.89 211.97,-268.78 205.11,-267.4\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>13</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"299.65\" cy=\"-223.37\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"299.65\" y=\"-219.17\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;13 -->\n",
       "<g id=\"edge31\" class=\"edge\">\n",
       "<title>6&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M253.03,-231.83C256.77,-231.86 260.67,-231.78 264.54,-231.6\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"264.91,-235.08 274.64,-230.89 264.42,-228.1 264.91,-235.08\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge32\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M281.52,-110.59C277.8,-112.99 273.99,-115.66 270.36,-118.41\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"267.94,-115.86 262.34,-124.86 272.33,-121.32 267.94,-115.86\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge33\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M294.49,-84.82C282.04,-70.78 261.19,-50.95 243.93,-36.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"245.76,-33.45 235.8,-29.85 241.34,-38.88 245.76,-33.45\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;13 -->\n",
       "<g id=\"edge34\" class=\"edge\">\n",
       "<title>7&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M299.36,-119.34C296.38,-139.32 294.64,-172.06 295.14,-195.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"291.64,-195.64 295.53,-205.5 298.64,-195.37 291.64,-195.64\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;2 -->\n",
       "<g id=\"edge36\" class=\"edge\">\n",
       "<title>8&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M201.31,-33.81C198.92,-38.34 196.58,-43.41 194.57,-48.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"191.28,-47.24 191.16,-57.83 197.86,-49.63 191.28,-47.24\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;7 -->\n",
       "<g id=\"edge35\" class=\"edge\">\n",
       "<title>8&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M225.69,-34.77C238.14,-48.81 258.99,-68.64 276.25,-83.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"274.42,-86.14 284.38,-89.74 278.84,-80.71 274.42,-86.14\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge37\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M188.11,-16.31C169.31,-17.75 144.1,-21.31 123.99,-25.29\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"123.07,-21.9 114,-27.39 124.51,-28.75 123.07,-21.9\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;3 -->\n",
       "<g id=\"edge39\" class=\"edge\">\n",
       "<title>9&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M88.56,-54.53C89.25,-59.35 90.35,-64.66 91.7,-69.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"88.34,-70.83 94.54,-79.42 95.05,-68.84 88.34,-70.83\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;8 -->\n",
       "<g id=\"edge38\" class=\"edge\">\n",
       "<title>9&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M117.36,-38.12C136.15,-36.68 161.37,-33.12 181.47,-29.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"182.4,-32.53 191.46,-27.04 180.95,-25.68 182.4,-32.53\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge40\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M76.07,-51.72C63.56,-69.99 46.18,-100.74 35.62,-123.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"32.36,-121.76 31.42,-132.31 38.74,-124.65 32.36,-121.76\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;4 -->\n",
       "<g id=\"edge42\" class=\"edge\">\n",
       "<title>10&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M41.56,-165.4C42.83,-166.22 44.14,-167.03 45.48,-167.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"44.14,-171.09 54.59,-172.86 47.53,-164.96 44.14,-171.09\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;9 -->\n",
       "<g id=\"edge41\" class=\"edge\">\n",
       "<title>10&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M41.33,-134.8C53.84,-116.54 71.22,-85.78 81.78,-63.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"85.04,-64.77 85.98,-54.22 78.66,-61.88 85.04,-64.77\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge43\" class=\"edge\">\n",
       "<title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M30.05,-168C37.02,-188.41 52.12,-221.83 64.5,-244.81\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"61.5,-246.62 69.43,-253.65 67.61,-243.21 61.5,-246.62\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;5 -->\n",
       "<g id=\"edge45\" class=\"edge\">\n",
       "<title>11&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M108.61,-264.8C110.89,-263.82 113.19,-262.77 115.46,-261.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"117.21,-264.7 124.46,-256.98 113.97,-258.5 117.21,-264.7\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;10 -->\n",
       "<g id=\"edge44\" class=\"edge\">\n",
       "<title>11&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M79.43,-251.96C72.46,-231.55 57.35,-198.14 44.98,-175.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"47.97,-173.34 40.05,-166.31 41.86,-176.75 47.97,-173.34\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge46\" class=\"edge\">\n",
       "<title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.91,-280.07C123.1,-285.37 149.13,-291.05 170.43,-294.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"170.04,-297.97 180.45,-295.99 171.08,-291.05 170.04,-297.97\"/>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;6 -->\n",
       "<g id=\"edge48\" class=\"edge\">\n",
       "<title>12&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M218.49,-279.28C221.32,-271.81 224,-262.81 225.97,-254.36\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"229.41,-254.96 227.96,-244.47 222.55,-253.58 229.41,-254.96\"/>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;11 -->\n",
       "<g id=\"edge47\" class=\"edge\">\n",
       "<title>12&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M185.18,-285.73C166.99,-280.43 140.96,-274.75 119.66,-271.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"120.05,-267.83 109.64,-269.81 119.01,-274.75 120.05,-267.83\"/>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge49\" class=\"edge\">\n",
       "<title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M230.15,-285.29C245.41,-275.04 265.32,-259.51 279.95,-246.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"282.49,-248.92 287.48,-239.58 277.75,-243.77 282.49,-248.92\"/>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;6 -->\n",
       "<g id=\"edge52\" class=\"edge\">\n",
       "<title>13&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.53,-217.97C269.79,-217.94 265.89,-218.02 262.01,-218.2\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"261.64,-214.71 251.91,-218.91 262.13,-221.7 261.64,-214.71\"/>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;7 -->\n",
       "<g id=\"edge51\" class=\"edge\">\n",
       "<title>13&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M305.41,-205.62C308.39,-185.63 310.13,-152.89 309.63,-129.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"313.13,-129.31 309.24,-119.46 306.13,-129.59 313.13,-129.31\"/>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;12 -->\n",
       "<g id=\"edge50\" class=\"edge\">\n",
       "<title>13&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M277.12,-234.01C261.86,-244.25 241.95,-259.79 227.32,-272.8\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"224.78,-270.38 219.79,-279.72 229.52,-275.53 224.78,-270.38\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11008e320>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "for i in range(1, 6):\n",
    "    g.edge(0, i)\n",
    "    g.edge(i, 0)\n",
    "    g.edge(i, i+1)\n",
    "    g.edge(i+1, i)\n",
    "g.edge(6,0)\n",
    "g.edge(0,6)\n",
    "g.edge(6,1)\n",
    "g.edge(1,6)\n",
    "for i in range(1, 7):\n",
    "    g.edge(i, i+6)\n",
    "    g.edge(i+6, i)\n",
    "    g.edge(i+6, i+7)\n",
    "    g.edge(i+7, i+6)\n",
    "g.edge(7,13)\n",
    "g.edge(13,7)\n",
    "g.edge(6,13)\n",
    "g.edge(13,6)\n",
    "g.bfs(0, 11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"267pt\" height=\"285pt\"\n",
       " viewBox=\"0.00 0.00 266.78 284.69\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 280.69)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-280.69 262.78,-280.69 262.78,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"42.49\" cy=\"-258.69\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"42.49\" y=\"-254.49\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"114.9\" cy=\"-233.74\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.9\" y=\"-229.54\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M66.6,-250.39C71.2,-248.8 76.08,-247.12 80.91,-245.45\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"82.33,-248.67 90.65,-242.1 80.05,-242.05 82.33,-248.67\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"68.34\" cy=\"-134.17\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"68.34\" y=\"-129.97\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M106.79,-216.4C99.62,-201.07 89.06,-178.48 80.82,-160.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"83.92,-159.22 76.51,-151.65 77.58,-162.19 83.92,-159.22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"100.1\" cy=\"-176.95\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"100.1\" y=\"-172.75\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M116.61,-215.76C115.97,-211.75 115.03,-207.43 113.91,-203.17\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"117.23,-202.08 110.98,-193.53 110.54,-204.12 117.23,-202.08\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M80.52,-150.59C80.98,-151.21 81.45,-151.83 81.91,-152.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"79.22,-154.7 87.99,-160.65 84.84,-150.53 79.22,-154.7\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"119.35\" cy=\"-86.19\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"119.35\" y=\"-81.99\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;5 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>3&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M89.71,-122.86C94.16,-119.16 98.76,-114.94 103,-110.7\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"105.81,-112.82 110.11,-103.14 100.71,-108.03 105.81,-112.82\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;0 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>4&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M88.44,-193.49C80.32,-205.01 69.34,-220.59 60.15,-233.63\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"57.03,-231.98 54.13,-242.18 62.75,-236.02 57.03,-231.98\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M98.39,-194.94C99.03,-198.94 99.97,-203.27 101.09,-207.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"97.77,-208.61 104.02,-217.16 104.46,-206.58 97.77,-208.61\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M103.9,-159.02C106.62,-146.21 110.32,-128.74 113.43,-114.12\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"116.9,-114.59 115.56,-104.08 110.06,-113.14 116.9,-114.59\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"165.99\" cy=\"-156.97\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"165.99\" y=\"-152.77\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M127.29,-175.58C130.53,-174.75 133.84,-173.8 137.1,-172.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"138.27,-176.07 146.58,-169.5 135.98,-169.45 138.27,-176.07\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;3 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>5&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M97.98,-97.5C93.53,-101.19 88.92,-105.41 84.69,-109.66\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"81.88,-107.53 77.58,-117.21 86.98,-112.33 81.88,-107.53\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M130.4,-102.96C136.1,-111.6 143.15,-122.31 149.47,-131.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"146.59,-133.89 155.01,-140.31 152.44,-130.04 146.59,-133.89\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-55.92\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-51.72\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M95.09,-78.23C84.67,-74.82 72.32,-70.77 61.01,-67.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"62.02,-63.71 51.42,-63.92 59.84,-70.37 62.02,-63.71\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"211.6\" cy=\"-129.78\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"211.6\" y=\"-125.58\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;7 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>5&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M136.51,-100.53C147.62,-106.99 162.46,-114.32 176.02,-120.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"175.02,-123.52 185.6,-124.09 177.68,-117.04 175.02,-123.52\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;2 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>6&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M154.9,-173.63C148.07,-183.89 139.19,-197.24 131.53,-208.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"128.59,-206.85 125.97,-217.12 134.42,-210.73 128.59,-206.85\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;4 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>6&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M138.79,-158.33C135.56,-159.17 132.25,-160.12 128.99,-161.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"127.82,-157.85 119.51,-164.42 130.1,-164.47 127.82,-157.85\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M186.13,-144.96C186.24,-144.9 186.34,-144.83 186.45,-144.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"184.51,-150 191.31,-141.88 180.92,-143.99 184.51,-150\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"173.82\" cy=\"-92.14\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"173.82\" y=\"-87.94\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;8 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>6&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.25,-139.64C175.5,-133.85 176.49,-127.24 177.1,-120.82\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"180.62,-120.58 177.73,-110.38 173.63,-120.15 180.62,-120.58\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.97,-72.9C41.35,-83.08 48.31,-96.25 54.39,-107.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"51.48,-109.75 59.24,-116.95 57.67,-106.48 51.48,-109.75\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;3 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>7&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M184.32,-130.61C162.01,-131.3 130.25,-132.27 105.6,-133.03\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"105.41,-129.53 95.52,-133.34 105.62,-136.53 105.41,-129.53\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;5 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>7&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M194.45,-115.44C183.34,-108.97 168.5,-101.64 154.94,-95.82\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"155.94,-92.45 145.36,-91.88 153.27,-98.92 155.94,-92.45\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M196.24,-114.47C196.09,-114.32 195.95,-114.18 195.81,-114.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"198.85,-112.13 189.3,-107.55 193.91,-117.09 198.85,-112.13\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;4 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>8&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M159.96,-108.09C148.76,-120.96 132.86,-139.26 120.26,-153.75\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"117.57,-151.51 113.65,-161.36 122.86,-156.1 117.57,-151.51\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;6 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>8&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M165.56,-109.46C164.31,-115.25 163.32,-121.87 162.71,-128.29\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"159.19,-128.53 162.08,-138.72 166.18,-128.96 159.19,-128.53\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"231.78\" cy=\"-49.86\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"231.78\" y=\"-45.66\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M192.16,-78.76C196.28,-75.75 200.74,-72.5 205.12,-69.3\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"207.34,-72.01 213.36,-63.29 203.22,-66.36 207.34,-72.01\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;5 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>9&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M207.38,-57.74C191.62,-62.83 170.88,-69.54 153.49,-75.16\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"152.14,-71.91 143.7,-78.32 154.29,-78.57 152.14,-71.91\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;7 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>9&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M227.2,-67.99C224.65,-78.08 221.43,-90.84 218.58,-102.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"215.15,-101.44 216.09,-111.99 221.93,-103.15 215.15,-101.44\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"168.69\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"168.69\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;6 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>10&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M168.34,-36.17C167.88,-59.68 167.08,-100.9 166.54,-128.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"163.04,-128.73 166.34,-138.8 170.03,-128.87 163.04,-128.73\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;8 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>10&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.96,-36.33C170.54,-44.68 171.24,-54.75 171.88,-64.02\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"168.39,-64.29 172.57,-74.02 175.37,-63.8 168.39,-64.29\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11006a198>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "for i in range(7):\n",
    "    g.edge(i,i+2)\n",
    "    g.edge(i+4,i)\n",
    "    g.edge(i+4,i+2)\n",
    "    g.edge(i+2,i+3)\n",
    "g.bfs(0, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"420pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 419.70 403.93\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 399.93)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-399.93 415.7,-399.93 415.7,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"209.47\" cy=\"-140.54\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"209.47\" y=\"-136.34\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>16</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"108.43\" cy=\"-142.62\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"108.43\" y=\"-138.42\" font-family=\"Times,serif\" font-size=\"14.00\">16</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;16 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M182.4,-141.1C171.18,-141.33 157.99,-141.6 145.88,-141.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"145.51,-138.36 135.59,-142.07 145.66,-145.36 145.51,-138.36\"/>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>17</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"131.41\" cy=\"-78.01\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"131.41\" y=\"-73.81\" font-family=\"Times,serif\" font-size=\"14.00\">17</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;17 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>0&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M197.84,-124.23C188.34,-114.98 174.62,-103.56 162.08,-94.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"163.83,-91.28 153.65,-88.33 159.77,-96.98 163.83,-91.28\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"291.73\" cy=\"-195.07\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"291.73\" y=\"-190.87\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>0&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M223.05,-156.2C232.83,-164.09 246.39,-173.45 258.89,-181.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"257.34,-184.24 267.73,-186.3 260.89,-178.21 257.34,-184.24\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>12</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"203.4\" cy=\"-239.09\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"203.4\" y=\"-234.89\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;12 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M203.01,-158.29C200.57,-172.87 199.02,-193.81 198.98,-210.71\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"195.49,-211.2 199.18,-221.13 202.49,-211.07 195.49,-211.2\"/>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>14</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"103.33\" cy=\"-224.77\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"103.33\" y=\"-220.57\" font-family=\"Times,serif\" font-size=\"14.00\">14</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;14 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>16&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M107.3,-160.85C106.65,-171.28 105.83,-184.58 105.1,-196.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"101.59,-196.39 104.46,-206.59 108.57,-196.82 101.59,-196.39\"/>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>15</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-178.79\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-174.59\" font-family=\"Times,serif\" font-size=\"14.00\">15</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;15 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>16&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82.37,-147.43C73.02,-150.89 62.5,-155.45 53.14,-160.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"51.53,-156.98 44.27,-164.69 54.76,-163.19 51.53,-156.98\"/>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>17&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M143.05,-94.33C152.54,-103.58 166.27,-114.99 178.81,-124.23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"177.05,-127.27 187.23,-130.22 181.11,-121.57 177.05,-127.27\"/>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;16 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>17&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M125.13,-95.67C122.95,-101.79 120.46,-108.81 118.07,-115.52\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"114.76,-114.4 114.7,-124.99 121.35,-116.74 114.76,-114.4\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;0 -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>6&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M278.15,-179.41C268.37,-171.53 254.82,-162.16 242.32,-154.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"243.86,-151.37 233.47,-149.32 240.31,-157.41 243.86,-151.37\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;12 -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>6&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M265.83,-201.25C254.08,-206.15 240.25,-212.93 228.58,-219.47\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"226.63,-216.55 219.77,-224.62 230.17,-222.59 226.63,-216.55\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"340.42\" cy=\"-106.5\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"340.42\" y=\"-102.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;4 -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>6&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M301.12,-178C308.19,-165.13 318.01,-147.26 326.07,-132.61\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"329.31,-133.97 331.06,-123.53 323.17,-130.6 329.31,-133.97\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"384.7\" cy=\"-158.87\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"384.7\" y=\"-154.67\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;5 -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>6&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M318.34,-191.17C330.45,-187.36 344.76,-181.91 357,-176.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"358.69,-179.56 366.28,-172.17 355.74,-173.21 358.69,-179.56\"/>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;0 -->\n",
       "<g id=\"edge35\" class=\"edge\">\n",
       "<title>12&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M209.86,-221.35C212.3,-206.76 213.85,-185.83 213.89,-168.92\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"217.38,-168.43 213.69,-158.5 210.39,-168.56 217.38,-168.43\"/>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;6 -->\n",
       "<g id=\"edge36\" class=\"edge\">\n",
       "<title>12&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M229.29,-232.92C241.05,-228.01 254.88,-221.23 266.55,-214.7\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"268.49,-217.61 275.36,-209.55 264.96,-211.57 268.49,-217.61\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node16\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"255.63\" cy=\"-326\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"255.63\" y=\"-321.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;10 -->\n",
       "<g id=\"edge33\" class=\"edge\">\n",
       "<title>12&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M213.47,-255.85C221.01,-268.39 231.46,-285.78 240.07,-300.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"237.26,-302.23 245.41,-309 243.26,-298.62 237.26,-302.23\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node17\" class=\"node\">\n",
       "<title>11</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"188.1\" cy=\"-337.48\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"188.1\" y=\"-333.28\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;11 -->\n",
       "<g id=\"edge34\" class=\"edge\">\n",
       "<title>12&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M195.29,-256.31C191.44,-270.96 187.88,-292.27 186.28,-309.38\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"182.79,-309.17 185.56,-319.4 189.77,-309.67 182.79,-309.17\"/>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;12 -->\n",
       "<g id=\"edge39\" class=\"edge\">\n",
       "<title>14&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M129.88,-228.57C141.19,-230.19 154.57,-232.1 166.79,-233.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"166.32,-237.32 176.72,-235.27 167.32,-230.39 166.32,-237.32\"/>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node18\" class=\"node\">\n",
       "<title>13</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"118.32\" cy=\"-291.69\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"118.32\" y=\"-287.49\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;13 -->\n",
       "<g id=\"edge40\" class=\"edge\">\n",
       "<title>14&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M101.3,-242.96C102.11,-249.71 103.61,-257.52 105.47,-264.88\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"102.1,-265.83 108.2,-274.5 108.84,-263.92 102.1,-265.83\"/>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge42\" class=\"edge\">\n",
       "<title>15&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M53.06,-173.98C62.41,-170.52 72.94,-165.96 82.29,-161.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"83.9,-164.44 91.16,-156.72 80.68,-158.22 83.9,-164.44\"/>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;14 -->\n",
       "<g id=\"edge41\" class=\"edge\">\n",
       "<title>15&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M47.06,-190.87C55.4,-195.9 65.26,-201.83 74.37,-207.32\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"72.77,-210.45 83.14,-212.61 76.38,-204.45 72.77,-210.45\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"206.29\" cy=\"-41.01\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"206.29\" y=\"-36.81\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;0 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>1&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M206.87,-59.27C207.34,-74 208.02,-94.99 208.56,-111.95\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"205.08,-112.52 208.89,-122.4 212.07,-112.3 205.08,-112.52\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"271.92\" cy=\"-60.69\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"271.92\" y=\"-56.49\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M225.95,-53.57C228.79,-54.62 231.78,-55.65 234.83,-56.6\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"234.03,-60.01 244.6,-59.38 235.94,-53.28 234.03,-60.01\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;0 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>2&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M259.28,-76.85C250.39,-88.21 238.35,-103.62 228.33,-116.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"225.49,-114.37 222.09,-124.41 231.01,-118.69 225.49,-114.37\"/>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;1 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>2&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M252.26,-48.13C249.42,-47.08 246.42,-46.06 243.37,-45.1\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"244.18,-41.69 233.6,-42.32 242.26,-48.42 244.18,-41.69\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"350.1\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"350.1\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;2 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>3&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M329.15,-29.44C320.73,-34.03 310.88,-39.41 301.74,-44.4\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"300.03,-41.35 292.93,-49.22 303.38,-47.5 300.03,-41.35\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M342.62,-35.31C339.98,-47.56 337.9,-64.27 337.16,-78.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"333.65,-78.53 336.86,-88.62 340.65,-78.73 333.65,-78.53\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;2 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>4&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M321.34,-93.74C314.77,-89.35 307.27,-84.33 300.13,-79.55\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"301.63,-76.35 291.37,-73.7 297.74,-82.17 301.63,-76.35\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>4&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M347.89,-89.19C350.53,-76.94 352.61,-60.23 353.36,-46.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"356.86,-45.97 353.66,-35.88 349.87,-45.77 356.86,-45.97\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.09,-162.77C345.98,-166.58 331.67,-172.04 319.44,-177.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"317.75,-174.39 310.15,-181.78 320.7,-180.74 317.75,-174.39\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;4 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>5&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M371.42,-143.16C367.91,-139.02 364.06,-134.46 360.29,-130\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"362.82,-127.58 353.7,-122.2 357.48,-132.1 362.82,-127.58\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"379.69\" cy=\"-242.46\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"379.69\" y=\"-238.26\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;6 -->\n",
       "<g id=\"edge23\" class=\"edge\">\n",
       "<title>7&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M358.4,-230.99C347.38,-225.05 333.74,-217.71 321.68,-211.21\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"323.29,-208.1 312.83,-206.44 319.97,-214.26 323.29,-208.1\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node14\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"329.17\" cy=\"-288.87\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"329.17\" y=\"-284.67\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge24\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M358.24,-253.44C354.12,-256.79 349.86,-260.59 345.91,-264.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"343.24,-262.15 338.79,-271.77 348.27,-267.03 343.24,-262.15\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;6 -->\n",
       "<g id=\"edge25\" class=\"edge\">\n",
       "<title>8&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M322.13,-271.23C316.64,-257.47 308.91,-238.12 302.63,-222.37\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"305.7,-220.63 298.74,-212.64 299.2,-223.22 305.7,-220.63\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;7 -->\n",
       "<g id=\"edge26\" class=\"edge\">\n",
       "<title>8&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M350.62,-277.89C354.75,-274.54 359,-270.74 362.95,-266.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"365.62,-269.18 370.07,-259.56 360.6,-264.3 365.62,-269.18\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node15\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"327.97\" cy=\"-377.93\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"327.97\" y=\"-373.73\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;8 -->\n",
       "<g id=\"edge27\" class=\"edge\">\n",
       "<title>9&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M328.22,-359.91C328.38,-347.68 328.6,-331.25 328.79,-317.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"332.29,-317.22 328.92,-307.17 325.29,-317.12 332.29,-317.22\"/>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge28\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M315.25,-361.76C307.5,-355.02 297.29,-347.33 287.5,-340.76\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"289.37,-337.8 279.07,-335.32 285.58,-343.68 289.37,-337.8\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;8 -->\n",
       "<g id=\"edge29\" class=\"edge\">\n",
       "<title>10&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M277.3,-315.06C283.82,-311.76 291.12,-308.08 298.12,-304.54\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"300.06,-307.49 307.41,-299.86 296.9,-301.24 300.06,-307.49\"/>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;9 -->\n",
       "<g id=\"edge30\" class=\"edge\">\n",
       "<title>10&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M268.35,-342.17C276.1,-348.91 286.31,-356.6 296.1,-363.17\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"294.23,-366.13 304.53,-368.61 298.03,-360.25 294.23,-366.13\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge32\" class=\"edge\">\n",
       "<title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M196.2,-320.26C200.05,-305.61 203.62,-284.3 205.21,-267.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"208.7,-267.4 205.93,-257.17 201.72,-266.9 208.7,-267.4\"/>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;10 -->\n",
       "<g id=\"edge31\" class=\"edge\">\n",
       "<title>11&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M214.4,-333.01C215.93,-332.75 217.48,-332.48 219.03,-332.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"220.02,-335.6 229.29,-330.48 218.84,-328.7 220.02,-335.6\"/>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;12 -->\n",
       "<g id=\"edge37\" class=\"edge\">\n",
       "<title>13&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M138.48,-279.22C149.29,-272.54 162.79,-264.2 174.68,-256.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"176.71,-259.7 183.38,-251.47 173.03,-253.75 176.71,-259.7\"/>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge38\" class=\"edge\">\n",
       "<title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M120.35,-273.5C119.54,-266.75 118.04,-258.94 116.18,-251.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"119.55,-250.62 113.45,-241.96 112.81,-252.54 119.55,-250.62\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11009b860>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# designed by nicholas beninato\n",
    "nodes = list(range(18)) # should be multiple of 6\n",
    "def next(index):\n",
    "    if index == nodes[-1]:\n",
    "        return 0\n",
    "    return index + 1\n",
    "\n",
    "def prev(index):\n",
    "    if index == 0:\n",
    "        return nodes[-1]\n",
    "    return index - 1\n",
    "\n",
    "g = test_graph()\n",
    "for i in nodes:\n",
    "    for j in nodes:\n",
    "        if i == next(j):\n",
    "            g.edge(i, j)\n",
    "        if j % 2 == 0 and i == prev(j):\n",
    "            g.edge(i, j)\n",
    "        if j % 2 == 0 and i == next(next(j)):\n",
    "            g.edge(i, j)\n",
    "\n",
    "for i in nodes: # can comment out these loops to get rid of \"inner\" edges\n",
    "    for j in nodes:\n",
    "        if i % 6 == 0 and j % 6 == 0 and j != i:\n",
    "            g.edge(j, i)\n",
    "# g.dfs(0,8) # 0,16,14,12,10,8 (18 nodes)\n",
    "g.bfs(3, 12) # 3,2,0,12 (18 nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "now call .visit(???) to identify the first node explored"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"283pt\" height=\"302pt\"\n",
       " viewBox=\"0.00 0.00 282.97 301.79\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 297.79)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-297.79 278.97,-297.79 278.97,4 -4,4\"/>\n",
       "<!-- 4 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"157.42\" cy=\"-266.96\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"157.42\" y=\"-262.76\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"204.15\" cy=\"-195.67\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"204.15\" y=\"-191.47\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;6 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>4&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M168.26,-250.43C173.95,-241.73 181.06,-230.89 187.45,-221.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"190.49,-222.89 193.05,-212.61 184.64,-219.05 190.49,-222.89\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"183.49\" cy=\"-107.8\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"183.49\" y=\"-103.6\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;8 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>6&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M199.87,-177.46C197.03,-165.37 193.24,-149.25 190.02,-135.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"193.39,-134.62 187.69,-125.69 186.58,-136.22 193.39,-134.62\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"170.23\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"170.23\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;10 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>8&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180.81,-89.63C178.97,-77.21 176.51,-60.51 174.42,-46.36\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"177.83,-45.53 172.91,-36.15 170.91,-46.55 177.83,-45.53\"/>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"245.59\" cy=\"-275.79\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"245.59\" y=\"-271.59\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>1&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M218.65,-273.09C210.96,-272.32 202.45,-271.47 194.27,-270.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"194.48,-267.16 184.19,-269.64 193.79,-274.12 194.48,-267.16\"/>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;6 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M236.6,-258.4C231.08,-247.73 223.9,-233.84 217.7,-221.86\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"220.69,-220.02 212.98,-212.74 214.47,-223.23 220.69,-220.02\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"120.59\" cy=\"-177.98\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"120.59\" y=\"-173.78\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"6\" d=\"M127.86,-195.56C133.11,-208.23 140.29,-225.58 146.26,-240\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"6\" points=\"141.48,-242.19 150.16,-249.42 151.18,-238.17 141.48,-242.19\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;6 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>3&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"4\" d=\"M142.6,-188.9C150.1,-191.05 158.72,-193.06 167.08,-194.65\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"4\" points=\"166.61,-198.12 177.05,-196.36 167.79,-191.22 166.61,-198.12\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;6 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>3&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"3\" d=\"M147.87,-177.31C155.72,-178.5 164.34,-180.22 172.43,-182.19\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"3\" points=\"171.72,-185.62 182.28,-184.79 173.51,-178.85 171.72,-185.62\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;8 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>3&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"5\" d=\"M139.84,-165.24C149.31,-156.26 160.45,-144.04 169.17,-133.14\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"5\" points=\"172.69,-135.74 175.3,-125.14 165.75,-130.42 172.69,-135.74\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;8 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>3&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M128.91,-160.44C136.18,-150.49 146.88,-138.08 156.92,-127.77\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"159.42,-130.22 164.06,-120.7 154.49,-125.25 159.42,-130.22\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"27\" cy=\"-181.33\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"27\" y=\"-177.13\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;9 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>3&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M93.52,-178.95C84.4,-179.27 74.06,-179.64 64.29,-179.99\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"63.88,-176.51 54.01,-180.36 64.13,-183.5 63.88,-176.51\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"white\" stroke=\"black\" cx=\"247.97\" cy=\"-42.32\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"247.97\" y=\"-38.12\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;8 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>5&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M233.02,-57.51C224.88,-65.77 214.65,-76.15 205.61,-85.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"202.89,-83.12 198.36,-92.7 207.87,-88.03 202.89,-83.12\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;10 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>5&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" stroke-width=\"2\" d=\"M223.37,-34.62C217.42,-32.76 210.95,-30.73 204.63,-28.76\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" stroke-width=\"2\" points=\"205.52,-25.37 194.94,-25.73 203.43,-32.05 205.52,-25.37\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<__main__.test_graph at 0x11009b6d8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g = test_graph()\n",
    "for i in range(1,7,2):\n",
    "    g.edge(i+3,i+5)\n",
    "    g.edge(i,i+5)\n",
    "    g.edge(1+2,i+3)\n",
    "    g.edge(i,i+3)\n",
    "g.edge(3,9)\n",
    "g.bfs(3,5)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}