HW 3 - Neighbor Joining, Parsimony, Branch & Bound/Submission/notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-fd91a97c0a7166df",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# BMI/CS 576 Fall 2019 - HW3\n",
    "The objectives of this homework are to practice phylogenetic tree reconstruction algorithms.  Specifically, you will gain practice with the following techniques:\n",
    "\n",
    "* Neighbor-joining\n",
    "* branch and bound\n",
    "* unweighted and weighted parsimony\n",
    "\n",
    "## HW policies\n",
    "Before starting this homework, please read over the [homework policies](https://canvas.wisc.edu/courses/167969/pages/hw-policies) for this course.  In particular, note that homeworks are to be completed *individually*.\n",
    "\n",
    "You are welcome to use any code from the weekly notebooks in your solutions to the HW."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-e632c3d68ef6e040",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 1: Neighbor-joining (20 points)\n",
    "\n",
    "Construct a tree from these distances using the neighbor-joining algorithm. Show your updated distance matrix after each merge and give branch lengths for the final tree.\n",
    "\n",
    "|       | A | B | C | D | E |\n",
    "|-------|---|---|---|---|---|\n",
    "| **A** |   | 7 | 13|  9| 10| \n",
    "| **B** |   |   |  8|  4|  5|\n",
    "| **C** |   |   |   |  6|  9|\n",
    "| **D** |   |   |   |   |  5|\n",
    "| **E** |   |   |   |   |  &nbsp; |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "======================== Iteration 1 ========================\n",
      "Actual Distance: \n",
      "\tA\tB\tC\tD\tE\t\n",
      "A\t0\t7\t13\t9\t10\t\n",
      "B\t7\t0\t8\t4\t5\t\n",
      "C\t13\t8\t0\t6\t9\t\n",
      "D\t9\t4\t6\t0\t5\t\n",
      "E\t10\t5\t9\t5\t0\t\n",
      "\n",
      "r: \n",
      "r(A) = 13.0\n",
      "r(B) = 8.0\n",
      "r(C) = 12.0\n",
      "r(D) = 8.0\n",
      "r(E) = 9.67\n",
      "\n",
      "Corrected Distance: \n",
      "\tA\tB\tC\tD\tE\t\n",
      "A\t0\t-14.0\t-12.0\t-12.0\t-12.67\t\n",
      "B\t-14.0\t0\t-12.0\t-12.0\t-12.67\t\n",
      "C\t-12.0\t-12.0\t0\t-14.0\t-12.67\t\n",
      "D\t-12.0\t-12.0\t-14.0\t0\t-12.67\t\n",
      "E\t-12.67\t-12.67\t-12.67\t-12.67\t0\t\n",
      "\n",
      "Merge A and B to a new node AB\n",
      "d(A, AB) = 6.0\n",
      "d(B, AB) = 1.0\n",
      "\n",
      "======================== Iteration 2 ========================\n",
      "Actual Distance: \n",
      "\tC\tD\tE\tAB\t\n",
      "C\t0\t6\t9\t7.0\t\n",
      "D\t6\t0\t5\t3.0\t\n",
      "E\t9\t5\t0\t4.0\t\n",
      "AB\t7.0\t3.0\t4.0\t0\t\n",
      "\n",
      "r: \n",
      "r(C) = 11.0\n",
      "r(D) = 7.0\n",
      "r(E) = 9.0\n",
      "r(AB) = 7.0\n",
      "\n",
      "Corrected Distance: \n",
      "\tC\tD\tE\tAB\t\n",
      "C\t0\t-12.0\t-11.0\t-11.0\t\n",
      "D\t-12.0\t0\t-11.0\t-11.0\t\n",
      "E\t-11.0\t-11.0\t0\t-12.0\t\n",
      "AB\t-11.0\t-11.0\t-12.0\t0\t\n",
      "\n",
      "Merge C and D to a new node CD\n",
      "d(C, CD) = 5.0\n",
      "d(D, CD) = 1.0\n",
      "\n",
      "======================== Iteration 3 ========================\n",
      "Actual Distance: \n",
      "\tE\tAB\tCD\t\n",
      "E\t0\t4.0\t4.0\t\n",
      "AB\t4.0\t0\t2.0\t\n",
      "CD\t4.0\t2.0\t0\t\n",
      "\n",
      "r: \n",
      "r(E) = 8.0\n",
      "r(AB) = 6.0\n",
      "r(CD) = 6.0\n",
      "\n",
      "Corrected Distance: \n",
      "\tE\tAB\tCD\t\n",
      "E\t0\t-10.0\t-10.0\t\n",
      "AB\t-10.0\t0\t-10.0\t\n",
      "CD\t-10.0\t-10.0\t0\t\n",
      "\n",
      "Merge E and AB to a new node EAB\n",
      "d(E, EAB) = 3.0\n",
      "d(AB, EAB) = 1.0\n",
      "\n",
      "======================== Final Tree ========================\n",
      "The final tree is (E:3.0000,(A:6.0000,B:1.0000):1.0000,(C:5.0000,D:1.0000):1.0000);\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t3aa34977878a48b185212617614041bd\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"275.0px\" id=\"t6b3b4f760f7943afb01be7615c2461b5\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 255.0 275.0\" width=\"255.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"tebbfb190c1f346ac9607c7379fe67007\"><clipPath id=\"t24ead6381d814edea9d51cb3050b8cef\"><rect height=\"215.0\" width=\"195.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#t24ead6381d814edea9d51cb3050b8cef)\"><g class=\"toyplot-mark-Text\" id=\"ta0017163d8c64c658f822cf50cc269bd\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" transform=\"translate(91.19601328903653,218.86291179596174)\"><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:11.0px;font-weight:normal;opacity:1;stroke:none;vertical-align:baseline;white-space:pre\" x=\"15.0\" y=\"2.8104999999999993\">D</text></g><g class=\"toyplot-Datum\" transform=\"translate(173.58803986710964,178.18145589798087)\"><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:11.0px;font-weight:normal;opacity:1;stroke:none;vertical-align:baseline;white-space:pre\" x=\"15.0\" y=\"2.8104999999999993\">C</text></g><g class=\"toyplot-Datum\" transform=\"translate(91.19601328903653,137.49999999999997)\"><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:11.0px;font-weight:normal;opacity:1;stroke:none;vertical-align:baseline;white-space:pre\" x=\"15.0\" y=\"2.8104999999999993\">B</text></g><g class=\"toyplot-Datum\" transform=\"translate(194.1860465116279,96.8185441020191)\"><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:11.0px;font-weight:normal;opacity:1;stroke:none;vertical-align:baseline;white-space:pre\" x=\"15.0\" y=\"2.8104999999999993\">A</text></g><g class=\"toyplot-Datum\" transform=\"translate(111.79401993355482,56.137088204038236)\"><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:11.0px;font-weight:normal;opacity:1;stroke:none;vertical-align:baseline;white-space:pre\" x=\"15.0\" y=\"2.8104999999999993\">E</text></g></g></g><g class=\"toyplot-mark-Graph\" id=\"t45698100e754437fbb363e5ceca71534\"><g class=\"toyplot-Edges\"><path d=\"M 50.0 56.137088204038236 L 111.79401993355482 56.137088204038236\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 50.0 117.15927205100954 L 70.59800664451828 117.15927205100954\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 50.0 198.5221838469713 L 70.59800664451828 198.5221838469713\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 96.8185441020191 L 194.1860465116279 96.8185441020191\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 137.49999999999997 L 91.19601328903653 137.49999999999997\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 178.18145589798087 L 173.58803986710964 178.18145589798087\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 218.86291179596174 L 91.19601328903653 218.86291179596174\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 50.0 123.93951470067302 L 50.0 56.137088204038236\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 50.0 123.93951470067302 L 50.0 117.15927205100954\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 50.0 123.93951470067302 L 50.0 198.5221838469713\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 117.15927205100954 L 70.59800664451828 96.8185441020191\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 117.15927205100954 L 70.59800664451828 137.49999999999997\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 198.5221838469713 L 70.59800664451828 178.18145589798087\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 70.59800664451828 198.5221838469713 L 70.59800664451828 218.86291179596174\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(91.19601328903653, 218.86291179596174)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(173.58803986710964, 178.18145589798087)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(91.19601328903653, 137.49999999999997)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(194.1860465116279, 96.8185441020191)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(111.79401993355482, 56.137088204038236)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 198.5221838469713)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 117.15927205100954)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 123.93951470067302)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 56.137088204038236)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 117.15927205100954)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 198.5221838469713)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 96.8185441020191)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 137.49999999999997)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 178.18145589798087)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(70.59800664451828, 218.86291179596174)\"><circle r=\"0.0\"></circle></g></g></g></g><g class=\"toyplot-coordinates-Axis\" id=\"t7988877f903247b3bbcc3c4b4793c3af\" transform=\"translate(50.0,225.0)translate(0,20.0)\"><line style=\"\" x1=\"0\" x2=\"144.1860465116279\" y1=\"0\" y2=\"0\"></line><g><line style=\"\" x1=\"144.1860465116279\" x2=\"144.1860465116279\" y1=\"0\" y2=\"-5\"></line><line style=\"\" x1=\"72.09302325581395\" x2=\"72.09302325581395\" y1=\"0\" y2=\"-5\"></line><line style=\"\" x1=\"0.0\" x2=\"0.0\" y1=\"0\" y2=\"-5\"></line></g><g><g transform=\"translate(144.1860465116279,6)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:10.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-2.78\" y=\"8.555\">0</text></g><g transform=\"translate(72.09302325581395,6)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:10.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-2.78\" y=\"8.555\">4</text></g><g transform=\"translate(0.0,6)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:10.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-2.78\" y=\"8.555\">7</text></g></g><g class=\"toyplot-coordinates-Axis-coordinates\" style=\"visibility:hidden\" transform=\"\"><line style=\"stroke:rgb(43.9%,50.2%,56.5%);stroke-opacity:1.0;stroke-width:1.0\" x1=\"0\" x2=\"0\" y1=\"-3.0\" y2=\"4.5\"></line><text style=\"alignment-baseline:alphabetic;fill:rgb(43.9%,50.2%,56.5%);fill-opacity:1.0;font-size:10px;font-weight:normal;stroke:none;text-anchor:middle\" x=\"0\" y=\"-6\"></text></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t3aa34977878a48b185212617614041bd\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t6b3b4f760f7943afb01be7615c2461b5\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot.coordinates.Axis\"] = (\n",
       "        function(canvas)\n",
       "        {\n",
       "            function sign(x)\n",
       "            {\n",
       "                return x < 0 ? -1 : x > 0 ? 1 : 0;\n",
       "            }\n",
       "\n",
       "            function mix(a, b, amount)\n",
       "            {\n",
       "                return ((1.0 - amount) * a) + (amount * b);\n",
       "            }\n",
       "\n",
       "            function log(x, base)\n",
       "            {\n",
       "                return Math.log(Math.abs(x)) / Math.log(base);\n",
       "            }\n",
       "\n",
       "            function in_range(a, x, b)\n",
       "            {\n",
       "                var left = Math.min(a, b);\n",
       "                var right = Math.max(a, b);\n",
       "                return left <= x && x <= right;\n",
       "            }\n",
       "\n",
       "            function inside(range, projection)\n",
       "            {\n",
       "                for(var i = 0; i != projection.length; ++i)\n",
       "                {\n",
       "                    var segment = projection[i];\n",
       "                    if(in_range(segment.range.min, range, segment.range.max))\n",
       "                        return true;\n",
       "                }\n",
       "                return false;\n",
       "            }\n",
       "\n",
       "            function to_domain(range, projection)\n",
       "            {\n",
       "                for(var i = 0; i != projection.length; ++i)\n",
       "                {\n",
       "                    var segment = projection[i];\n",
       "                    if(in_range(segment.range.bounds.min, range, segment.range.bounds.max))\n",
       "                    {\n",
       "                        if(segment.scale == \"linear\")\n",
       "                        {\n",
       "                            var amount = (range - segment.range.min) / (segment.range.max - segment.range.min);\n",
       "                            return mix(segment.domain.min, segment.domain.max, amount)\n",
       "                        }\n",
       "                        else if(segment.scale[0] == \"log\")\n",
       "                        {\n",
       "                            var amount = (range - segment.range.min) / (segment.range.max - segment.range.min);\n",
       "                            var base = segment.scale[1];\n",
       "                            return sign(segment.domain.min) * Math.pow(base, mix(log(segment.domain.min, base), log(segment.domain.max, base), amount));\n",
       "                        }\n",
       "                    }\n",
       "                }\n",
       "            }\n",
       "\n",
       "            var axes = {};\n",
       "\n",
       "            function display_coordinates(e)\n",
       "            {\n",
       "                var current = canvas.createSVGPoint();\n",
       "                current.x = e.clientX;\n",
       "                current.y = e.clientY;\n",
       "\n",
       "                for(var axis_id in axes)\n",
       "                {\n",
       "                    var axis = document.querySelector(\"#\" + axis_id);\n",
       "                    var coordinates = axis.querySelector(\".toyplot-coordinates-Axis-coordinates\");\n",
       "                    if(coordinates)\n",
       "                    {\n",
       "                        var projection = axes[axis_id];\n",
       "                        var local = current.matrixTransform(axis.getScreenCTM().inverse());\n",
       "                        if(inside(local.x, projection))\n",
       "                        {\n",
       "                            var domain = to_domain(local.x, projection);\n",
       "                            coordinates.style.visibility = \"visible\";\n",
       "                            coordinates.setAttribute(\"transform\", \"translate(\" + local.x + \")\");\n",
       "                            var text = coordinates.querySelector(\"text\");\n",
       "                            text.textContent = domain.toFixed(2);\n",
       "                        }\n",
       "                        else\n",
       "                        {\n",
       "                            coordinates.style.visibility= \"hidden\";\n",
       "                        }\n",
       "                    }\n",
       "                }\n",
       "            }\n",
       "\n",
       "            canvas.addEventListener(\"click\", display_coordinates);\n",
       "\n",
       "            var module = {};\n",
       "            module.show_coordinates = function(axis_id, projection)\n",
       "            {\n",
       "                axes[axis_id] = projection;\n",
       "            }\n",
       "\n",
       "            return module;\n",
       "        })(modules[\"toyplot/canvas\"]);\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t45698100e754437fbb363e5ceca71534\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[-5.0, -1.0, -5.0, -0.0, -4.0, -6.0, -6.0, -7.0, -7.0, -7.0, -7.0, -6.0, -6.0, -6.0, -6.0], [0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 2.5, 2.3333333333333335, 4.0, 2.5, 0.5, 3.0, 2.0, 1.0, 0.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t45698100e754437fbb363e5ceca71534\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[8, 9, 10, 11, 12, 13, 14, 7, 7, 7, 6, 6, 5, 5], [4, 6, 5, 3, 2, 1, 0, 8, 9, 10, 11, 12, 13, 14]],\"toyplot\");\n",
       "(function(axis, axis_id, projection)\n",
       "        {\n",
       "            axis.show_coordinates(axis_id, projection);\n",
       "        })(modules[\"toyplot.coordinates.Axis\"],\"t7988877f903247b3bbcc3c4b4793c3af\",[{\"domain\": {\"bounds\": {\"max\": Infinity, \"min\": -Infinity}, \"max\": 0.525, \"min\": -7.0}, \"range\": {\"bounds\": {\"max\": Infinity, \"min\": -Infinity}, \"max\": 155.0, \"min\": 0.0}, \"scale\": \"linear\"}]);\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import toytree, itertools\n",
    "\n",
    "def print_matrix(d):\n",
    "    print('', end=\"\\t\")\n",
    "    for i in L:\n",
    "        print(i, end=\"\\t\")\n",
    "    print()\n",
    "    for i in L:\n",
    "        print(i, end=\"\\t\")\n",
    "        for j in L:\n",
    "            v = d.get((i, j), d.get((j, i))) if i != j else 0\n",
    "            print(round(v, 2), end=\"\\t\")\n",
    "        print()\n",
    "\n",
    "d = {\n",
    "    ('A', 'A'): 0, ('A', 'B'): 7, ('A', 'C'): 13, ('A', 'D'): 9, ('A', 'E'): 10, \n",
    "    ('B', 'A'): 7, ('B', 'B'): 0, ('B', 'C'): 8, ('B', 'D'): 4, ('B', 'E'): 5, \n",
    "    ('C', 'A'): 13, ('C', 'B'): 8, ('C', 'C'): 0, ('C', 'D'): 6, ('C', 'E'): 9, \n",
    "    ('D', 'A'): 9, ('D', 'B'): 4, ('D', 'C'): 6, ('D', 'D'): 0, ('D', 'E'): 5, \n",
    "    ('E', 'A'): 10, ('E', 'B'): 5, ('E', 'C'): 9, ('E', 'D'): 5, ('E', 'E'): 0\n",
    "}\n",
    "\n",
    "L = sorted({e1 for (e1, e2) in d})\n",
    "\n",
    "for iteration in range(1, len(L) - 1):\n",
    "    print(f\"======================== Iteration {iteration} ========================\")\n",
    "    r = {e : sum(d[(e, k)] for k in L if e != k) / (len(L) - 2) for e in L}\n",
    "    D = {(i, j) : d[(i, j)] - r[i] - r[j] for (i, j) in itertools.combinations(L, r=2)}\n",
    "    (i, j) = min(D, key=D.get)\n",
    "    k = i + j\n",
    "    \n",
    "    d[(i, k)] = (d[(i, j)] + r[i] - r[j]) / 2\n",
    "    d[(j, k)] = (d[(i, j)] + r[j] - r[i]) / 2\n",
    "    d.update({(m, k) : (d[(i, m)] + d[(j, m)] - d[(i, j)]) / 2 for m in L if m not in (i, j)})\n",
    "    d.update({tuple(reversed(e)) : d[e] for e in d})\n",
    "    \n",
    "    print(\"Actual Distance: \")\n",
    "    print_matrix(d)\n",
    "    \n",
    "    print()\n",
    "    print(\"r: \")\n",
    "    for e in r:\n",
    "        print(f\"r({e}) = {str(round(r[e], 2))}\") \n",
    "        \n",
    "    print()\n",
    "    print(\"Corrected Distance: \")\n",
    "    print_matrix(D)\n",
    "    \n",
    "    print()\n",
    "    print(f\"Merge {i} and {j} to a new node {k}\")\n",
    "    print(f\"d({i}, {k}) = {d[(i, k)]}\")\n",
    "    print(f\"d({j}, {k}) = {d[(j, k)]}\")\n",
    "    \n",
    "    L = list([e for e in L if e not in (i, j)] + [k])\n",
    "    print()\n",
    "    \n",
    "tree = \"(E:3.0000,(A:6.0000,B:1.0000):1.0000,(C:5.0000,D:1.0000):1.0000);\"\n",
    "\n",
    "print(\"======================== Final Tree ========================\")\n",
    "print(f\"The final tree is {tree}\")\n",
    "_ = toytree.tree(tree).draw(use_edge_lengths=True, scalebar=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-1f115a62bb2dd441",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Trees for Problem 2 and 3\n",
    "![parsimony_trees](parsimony_trees.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-d388d0f01da01423",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 2: Unweighted parsimony (20 POINTS)\n",
    "\n",
    "Suppose we are given five DNA sequences (1, 2, 3, 4, and 5), each of which is one base long. The figure above gives two possible trees relating these five sequences.\n",
    "\n",
    "**(a)** For each of the two trees, find the minimal cost of the tree using Fitch’s algorithm (unweighted parsimony). Show the intermediate computations of the algorithm.\n",
    "\n",
    "**(b)** For each of the two trees, determine an assignment of ancestral bases that achieves the minimal cost that you found in (a).\n",
    "\n",
    "**(c)** Which tree would be preferred when using unweighted parsimony?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import toytree\n",
    "\n",
    "newicks = [\"(((C, G), G), (T, T));\", \"((G, G), (T, (C, T)));\"]\n",
    "\n",
    "def fitch_score_and_min_cost_states(newick):\n",
    "    tree = toytree.tree(newick)\n",
    "    R = {}\n",
    "    num_changes = 0\n",
    "    for node in tree.treenode.traverse(\"postorder\"):\n",
    "        if node.is_leaf():\n",
    "            R[node.name] = {node.name}\n",
    "        else:\n",
    "            left_states, right_states = [R[child.name] for child in node.children]\n",
    "            states_intersection = left_states & right_states\n",
    "            if states_intersection:\n",
    "                R[node.name] = states_intersection\n",
    "            else:\n",
    "                R[node.name] = left_states | right_states\n",
    "                num_changes += 1\n",
    "    for node in tree.treenode.traverse():\n",
    "        node.add_feature('R', \"{\"+ \",\".join(R[node.name]) + \"}\")\n",
    "    return tree, num_changes, R\n",
    "\n",
    "\n",
    "def fitch_ancestral_states(newick, R):\n",
    "    tree = toytree.tree(newick)\n",
    "    r = {} # a dictionary mapping node names to character states\n",
    "    for node in tree.treenode.traverse(\"preorder\"):\n",
    "        if node.is_root():\n",
    "            r[node.name] = sorted(R[node.name])[0] # use the lexicographically smallest element\n",
    "        else:\n",
    "            parent = node.up\n",
    "            if r[parent.name] in R[node.name]:\n",
    "                r[node.name] = r[parent.name]\n",
    "            else:\n",
    "                node.add_feature('color', toytree.colors[1])\n",
    "                r[node.name] = sorted(R[node.name])[0]\n",
    "    for node in tree.treenode.traverse():\n",
    "        node.add_feature('r', r[node.name])\n",
    "    return tree, r\n",
    "\n",
    "def draw(tree, node_labels='name'):\n",
    "    tree.draw(\n",
    "        node_colors=[c or toytree.colors[0] for c in tree.get_node_values(\"color\", show_root=True, show_tips=True)],\n",
    "        node_labels=tree.get_node_values(node_labels, show_root=True, show_tips=True), \n",
    "        tree_style=\"c\", \n",
    "        node_markers=\"r2.5x2\",\n",
    "        scalebar=False,\n",
    "        use_edge_lengths=False,\n",
    "        node_labels_style={\"font-size\": \"16px\"}\n",
    "    )\n",
    "    \n",
    "def fitch_algorithm(newick):    \n",
    "    tree, num_changes, R = fitch_score_and_min_cost_states(newick)\n",
    "    draw(tree, node_labels='R')\n",
    "    \n",
    "    tree, r = fitch_ancestral_states(newick, R)\n",
    "    draw(tree, node_labels='r')\n",
    "    \n",
    "    print(\"In the first graph, the text in the node represents the possible states for the node.\")\n",
    "    print(\"In the second graph, the orange node is the node that increase the cost. \")\n",
    "    print(f\"The minimum cost of the tree '{newick}' is {num_changes}.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In the first graph, the text in the node represents the possible states for the node.\n",
      "In the second graph, the orange node is the node that increase the cost. \n",
      "The minimum cost of the tree '(((C, G), G), (T, T));' is 2.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t2a7abc365dda4d898642fe5ba50a2fb2\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t641b2b11727d4d61908470b8d018426c\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"t201379a4fa5646759d72ece7defd300e\"><clipPath id=\"tc1b7e53229594d3d956256d916a76698\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#tc1b7e53229594d3d956256d916a76698)\"><g class=\"toyplot-mark-Text\" id=\"t6a404b6a76254380a07acdc604f7cac2\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"tb6f41399f4b644fb81da451afb5f66ac\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"tf5e6c97b4e164df49522ec3ca90690a7\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.12\" y=\"4.087999999999999\">{C}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-19.568\" y=\"4.087999999999999\">{G,C}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-18.68\" y=\"4.087999999999999\">{G,T}</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t2a7abc365dda4d898642fe5ba50a2fb2\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t641b2b11727d4d61908470b8d018426c\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tb6f41399f4b644fb81da451afb5f66ac\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tb6f41399f4b644fb81da451afb5f66ac\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tf5e6c97b4e164df49522ec3ca90690a7\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t7cdfcfededc444eb94e3ab90c6411a04\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t766582fa18ab4ba2b75061483fcaf9ed\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"te24cd825cd334378a524ab78a8056484\"><clipPath id=\"t506f935aa0c54fb086548dd9c4d252d3\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#t506f935aa0c54fb086548dd9c4d252d3)\"><g class=\"toyplot-mark-Text\" id=\"tbaac616a7e254a329fc05df408473276\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"t581981189c9c441d9f6ea999f34f7fa9\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"ta099e9ce5bff40f3a4768c408f2ea3e4\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(98.8%,55.3%,38.4%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-5.776\" y=\"4.087999999999999\">C</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(98.8%,55.3%,38.4%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t7cdfcfededc444eb94e3ab90c6411a04\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t766582fa18ab4ba2b75061483fcaf9ed\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t581981189c9c441d9f6ea999f34f7fa9\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t581981189c9c441d9f6ea999f34f7fa9\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"ta099e9ce5bff40f3a4768c408f2ea3e4\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fitch_algorithm(newicks[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In the first graph, the text in the node represents the possible states for the node.\n",
      "In the second graph, the orange node is the node that increase the cost. \n",
      "The minimum cost of the tree '((G, G), (T, (C, T)));' is 2.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"tf5f418f39689423cbeaa22216f8aaa47\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t233e9e650ebf4530a7e250a4bff8af91\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"te91d22cef96e428aab8d2c0da2578313\"><clipPath id=\"tf8f537daaf6f4d6ca4dbc8e260d7e234\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#tf8f537daaf6f4d6ca4dbc8e260d7e234)\"><g class=\"toyplot-mark-Text\" id=\"t470b08df4ef14c7fb92ba515bc0354f5\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"tae2236a4ff6240e6bb31b3289a01c865\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"taa610a8138ad4c7dbad2c65b03ea8edb\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.12\" y=\"4.087999999999999\">{C}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-18.232\" y=\"4.087999999999999\">{T,C}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-10.232000000000001\" y=\"4.087999999999999\">{T}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-11.568\" y=\"4.087999999999999\">{G}</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-18.68\" y=\"4.087999999999999\">{G,T}</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"tf5f418f39689423cbeaa22216f8aaa47\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t233e9e650ebf4530a7e250a4bff8af91\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tae2236a4ff6240e6bb31b3289a01c865\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tae2236a4ff6240e6bb31b3289a01c865\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"taa610a8138ad4c7dbad2c65b03ea8edb\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t2a68523b4f00444b95fe333cc191ab98\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t775c51b0cf774f3780913d347ddf33e5\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"t2de7576d563146fe8552b796989a402d\"><clipPath id=\"t67a1f53855b845139a8ed7e45b8b2be5\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#t67a1f53855b845139a8ed7e45b8b2be5)\"><g class=\"toyplot-mark-Text\" id=\"tbd06aa88cca44b6bb58f722a4dcd8d29\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"tb0485aace2a44887bf83875e789b6ad0\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"taf3c9a5d04dc411fb1bb269dd796d0fc\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(98.8%,55.3%,38.4%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-5.776\" y=\"4.087999999999999\">C</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(98.8%,55.3%,38.4%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t2a68523b4f00444b95fe333cc191ab98\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t775c51b0cf774f3780913d347ddf33e5\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tb0485aace2a44887bf83875e789b6ad0\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tb0485aace2a44887bf83875e789b6ad0\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"taf3c9a5d04dc411fb1bb269dd796d0fc\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fitch_algorithm(newicks[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(c): Both trees are equally perferred by unweighted parsimony\n"
     ]
    }
   ],
   "source": [
    "print(\"(c): Both trees are equally perferred by unweighted parsimony\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-47a34506ea0189d7",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 3: Weighted parsimony (20 POINTS)\n",
    "\n",
    "(25points) Suppose we are given the same five sequences as in Problem 2 and the same two possible trees. Given the weighted parsimony costs given in the matrix below:\n",
    "\n",
    "![weighted_parsimony_weights](weighted_parsimony_weights.png)\n",
    "\n",
    "**(a)** For each of the two trees, find the minimal cost of the tree using the weighted parsimony algorithm. Show the intermediate computations of the algorithm.\n",
    "\n",
    "**(b)** For each of the two trees, determine an assignment of ancestral bases that achieves the minimal cost that you found in (a).\n",
    "\n",
    "**(c)** Which tree would be preferred when using weighted parsimony with the given costs?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = {\n",
    "    ('A', 'A'): 0, ('A', 'C'): 2, ('A', 'G'): 1, ('A', 'T'): 2, \n",
    "    ('C', 'A'): 2, ('C', 'C'): 0, ('C', 'G'): 2, ('C', 'T'): 1, \n",
    "    ('G', 'A'): 1, ('G', 'C'): 2, ('G', 'G'): 0, ('G', 'T'): 2, \n",
    "    ('T', 'A'): 2, ('T', 'C'): 1, ('T', 'G'): 2, ('T', 'T'): 0, \n",
    "}\n",
    "\n",
    "chars = 'ACGT'\n",
    "\n",
    "INF = float('inf')\n",
    "\n",
    "def argmin(g):\n",
    "    return min(enumerate(g), key=lambda e: e[1])\n",
    "\n",
    "def weighted_parsimony(newick):\n",
    "    tree = toytree.tree(newick)\n",
    "    R = {}\n",
    "    arrows = {}\n",
    "    for node in tree.treenode.traverse(\"postorder\"):\n",
    "        if node.is_leaf():\n",
    "            for a in chars:\n",
    "                R[(str(node.idx), a)] = INF if a != node.name else 0\n",
    "                print(f\"R_{node.idx}({a})  = {R[(str(node.idx), a)]}\", end=\";\\t\")\n",
    "            print(\"\\n\")\n",
    "        else:\n",
    "            j, k = [str(child.idx) for child in node.children]\n",
    "            for a in chars:\n",
    "                l_index, l_val = argmin(R[(j, b)] + S[(a, b)] for b in chars)\n",
    "                r_index, r_val = argmin(R[(k, c)] + S[(a, c)] for c in chars)\n",
    "                arrows[(node.name, a)] = [chars[l_index], chars[r_index]]\n",
    "                R[(node.name, a)] = l_val + r_val\n",
    "                print((f\"R_{node.idx}({a})  = \" + \n",
    "                       \"min{\" + \", \".join(f\"R_{j}({b})+S({a},{b})\" for b in chars) + \"} + \\n\\t  \" +\n",
    "                       \"min{\" + \", \".join(f\"R_{k}({c})+S({a},{c})\" for c in chars) + \"} \\n\\t\" +\n",
    "                       \"= min{\" + \", \".join(f\"{R[(j, b)] + S[(a, b)]}\" for b in chars) + \"} + \" +\n",
    "                       \"min{\" + \", \".join(f\"{R[(k, c)] + S[(a, c)]}\" for c in chars) + \"}\" +\n",
    "                       f\" = {l_val} + {r_val} = {R[(str(node.idx), a)]}\"))\n",
    "            print()\n",
    "    \n",
    "    index, value = argmin(R[(node.name, a)] for a in chars) \n",
    "    print(f\"=================Final score for this tree is {value} =================\")\n",
    "    \n",
    "    for node in tree.treenode.traverse(\"preorder\"):\n",
    "        if node.is_leaf():\n",
    "            continue\n",
    "        \n",
    "        index, value = argmin(R[(str(node.idx), a)] for a in chars) \n",
    "        \n",
    "        if node.is_root():\n",
    "            node.name = chars[index]\n",
    "            \n",
    "        cl, cr = arrows[(str(node.idx), chars[index])]\n",
    "        l, r = node.children\n",
    "        l.name = cl\n",
    "        r.name = cr\n",
    "        \n",
    "    draw(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The following tree is used for indexing vertices\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t5d72c1192a5d408e8b06969c115e339c\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"tf9e9578ad3bc43a9ac46d28494a97b1a\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"te51d1ef975234f2796585c312c2f7084\"><clipPath id=\"t4e5f5395e7ad43eb9c1aa2af8fb5de0d\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#t4e5f5395e7ad43eb9c1aa2af8fb5de0d)\"><g class=\"toyplot-mark-Text\" id=\"td9a3bb51ca844f0da0ecb2051f3ba387\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"t55ac07f1370e49488121a9deaff72452\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"t8f04a811fdbf49c88d7e20f8534a2c6a\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">0</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">1</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">2</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">3</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">4</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">5</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">6</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">7</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.448\" y=\"4.087999999999999\">8</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t5d72c1192a5d408e8b06969c115e339c\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"tf9e9578ad3bc43a9ac46d28494a97b1a\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t55ac07f1370e49488121a9deaff72452\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t55ac07f1370e49488121a9deaff72452\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t8f04a811fdbf49c88d7e20f8534a2c6a\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(\"The following tree is used for indexing vertices\")\n",
    "draw(toytree.tree(newicks[0]), node_labels='idx')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R_4(A)  = inf;\tR_4(C)  = inf;\tR_4(G)  = inf;\tR_4(T)  = 0;\t\n",
      "\n",
      "R_3(A)  = inf;\tR_3(C)  = inf;\tR_3(G)  = inf;\tR_3(T)  = 0;\t\n",
      "\n",
      "R_7(A)  = min{R_4(A)+S(A,A), R_4(C)+S(A,C), R_4(G)+S(A,G), R_4(T)+S(A,T)} + \n",
      "\t  min{R_3(A)+S(A,A), R_3(C)+S(A,C), R_3(G)+S(A,G), R_3(T)+S(A,T)} \n",
      "\t= min{inf, inf, inf, 2} + min{inf, inf, inf, 2} = 2 + 2 = 4\n",
      "R_7(C)  = min{R_4(A)+S(C,A), R_4(C)+S(C,C), R_4(G)+S(C,G), R_4(T)+S(C,T)} + \n",
      "\t  min{R_3(A)+S(C,A), R_3(C)+S(C,C), R_3(G)+S(C,G), R_3(T)+S(C,T)} \n",
      "\t= min{inf, inf, inf, 1} + min{inf, inf, inf, 1} = 1 + 1 = 2\n",
      "R_7(G)  = min{R_4(A)+S(G,A), R_4(C)+S(G,C), R_4(G)+S(G,G), R_4(T)+S(G,T)} + \n",
      "\t  min{R_3(A)+S(G,A), R_3(C)+S(G,C), R_3(G)+S(G,G), R_3(T)+S(G,T)} \n",
      "\t= min{inf, inf, inf, 2} + min{inf, inf, inf, 2} = 2 + 2 = 4\n",
      "R_7(T)  = min{R_4(A)+S(T,A), R_4(C)+S(T,C), R_4(G)+S(T,G), R_4(T)+S(T,T)} + \n",
      "\t  min{R_3(A)+S(T,A), R_3(C)+S(T,C), R_3(G)+S(T,G), R_3(T)+S(T,T)} \n",
      "\t= min{inf, inf, inf, 0} + min{inf, inf, inf, 0} = 0 + 0 = 0\n",
      "\n",
      "R_2(A)  = inf;\tR_2(C)  = inf;\tR_2(G)  = 0;\tR_2(T)  = inf;\t\n",
      "\n",
      "R_1(A)  = inf;\tR_1(C)  = 0;\tR_1(G)  = inf;\tR_1(T)  = inf;\t\n",
      "\n",
      "R_0(A)  = inf;\tR_0(C)  = inf;\tR_0(G)  = 0;\tR_0(T)  = inf;\t\n",
      "\n",
      "R_5(A)  = min{R_1(A)+S(A,A), R_1(C)+S(A,C), R_1(G)+S(A,G), R_1(T)+S(A,T)} + \n",
      "\t  min{R_0(A)+S(A,A), R_0(C)+S(A,C), R_0(G)+S(A,G), R_0(T)+S(A,T)} \n",
      "\t= min{inf, 2, inf, inf} + min{inf, inf, 1, inf} = 2 + 1 = 3\n",
      "R_5(C)  = min{R_1(A)+S(C,A), R_1(C)+S(C,C), R_1(G)+S(C,G), R_1(T)+S(C,T)} + \n",
      "\t  min{R_0(A)+S(C,A), R_0(C)+S(C,C), R_0(G)+S(C,G), R_0(T)+S(C,T)} \n",
      "\t= min{inf, 0, inf, inf} + min{inf, inf, 2, inf} = 0 + 2 = 2\n",
      "R_5(G)  = min{R_1(A)+S(G,A), R_1(C)+S(G,C), R_1(G)+S(G,G), R_1(T)+S(G,T)} + \n",
      "\t  min{R_0(A)+S(G,A), R_0(C)+S(G,C), R_0(G)+S(G,G), R_0(T)+S(G,T)} \n",
      "\t= min{inf, 2, inf, inf} + min{inf, inf, 0, inf} = 2 + 0 = 2\n",
      "R_5(T)  = min{R_1(A)+S(T,A), R_1(C)+S(T,C), R_1(G)+S(T,G), R_1(T)+S(T,T)} + \n",
      "\t  min{R_0(A)+S(T,A), R_0(C)+S(T,C), R_0(G)+S(T,G), R_0(T)+S(T,T)} \n",
      "\t= min{inf, 1, inf, inf} + min{inf, inf, 2, inf} = 1 + 2 = 3\n",
      "\n",
      "R_6(A)  = min{R_2(A)+S(A,A), R_2(C)+S(A,C), R_2(G)+S(A,G), R_2(T)+S(A,T)} + \n",
      "\t  min{R_5(A)+S(A,A), R_5(C)+S(A,C), R_5(G)+S(A,G), R_5(T)+S(A,T)} \n",
      "\t= min{inf, inf, 1, inf} + min{3, 4, 3, 5} = 1 + 3 = 4\n",
      "R_6(C)  = min{R_2(A)+S(C,A), R_2(C)+S(C,C), R_2(G)+S(C,G), R_2(T)+S(C,T)} + \n",
      "\t  min{R_5(A)+S(C,A), R_5(C)+S(C,C), R_5(G)+S(C,G), R_5(T)+S(C,T)} \n",
      "\t= min{inf, inf, 2, inf} + min{5, 2, 4, 4} = 2 + 2 = 4\n",
      "R_6(G)  = min{R_2(A)+S(G,A), R_2(C)+S(G,C), R_2(G)+S(G,G), R_2(T)+S(G,T)} + \n",
      "\t  min{R_5(A)+S(G,A), R_5(C)+S(G,C), R_5(G)+S(G,G), R_5(T)+S(G,T)} \n",
      "\t= min{inf, inf, 0, inf} + min{4, 4, 2, 5} = 0 + 2 = 2\n",
      "R_6(T)  = min{R_2(A)+S(T,A), R_2(C)+S(T,C), R_2(G)+S(T,G), R_2(T)+S(T,T)} + \n",
      "\t  min{R_5(A)+S(T,A), R_5(C)+S(T,C), R_5(G)+S(T,G), R_5(T)+S(T,T)} \n",
      "\t= min{inf, inf, 2, inf} + min{5, 3, 4, 3} = 2 + 3 = 5\n",
      "\n",
      "R_8(A)  = min{R_7(A)+S(A,A), R_7(C)+S(A,C), R_7(G)+S(A,G), R_7(T)+S(A,T)} + \n",
      "\t  min{R_6(A)+S(A,A), R_6(C)+S(A,C), R_6(G)+S(A,G), R_6(T)+S(A,T)} \n",
      "\t= min{4, 4, 5, 2} + min{4, 6, 3, 7} = 2 + 3 = 5\n",
      "R_8(C)  = min{R_7(A)+S(C,A), R_7(C)+S(C,C), R_7(G)+S(C,G), R_7(T)+S(C,T)} + \n",
      "\t  min{R_6(A)+S(C,A), R_6(C)+S(C,C), R_6(G)+S(C,G), R_6(T)+S(C,T)} \n",
      "\t= min{6, 2, 6, 1} + min{6, 4, 4, 6} = 1 + 4 = 5\n",
      "R_8(G)  = min{R_7(A)+S(G,A), R_7(C)+S(G,C), R_7(G)+S(G,G), R_7(T)+S(G,T)} + \n",
      "\t  min{R_6(A)+S(G,A), R_6(C)+S(G,C), R_6(G)+S(G,G), R_6(T)+S(G,T)} \n",
      "\t= min{5, 4, 4, 2} + min{5, 6, 2, 7} = 2 + 2 = 4\n",
      "R_8(T)  = min{R_7(A)+S(T,A), R_7(C)+S(T,C), R_7(G)+S(T,G), R_7(T)+S(T,T)} + \n",
      "\t  min{R_6(A)+S(T,A), R_6(C)+S(T,C), R_6(G)+S(T,G), R_6(T)+S(T,T)} \n",
      "\t= min{6, 3, 6, 0} + min{6, 5, 4, 5} = 0 + 4 = 4\n",
      "\n",
      "=================Final score for this tree is 4 =================\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t36a59087cc0845a9a341e16dc5407e0a\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t45b75c0980d24f89906710d347d41352\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"t235844068e6447d88c2603d4e56c729c\"><clipPath id=\"t56ae258acfcc40efb004c9c3cea17717\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#t56ae258acfcc40efb004c9c3cea17717)\"><g class=\"toyplot-mark-Text\" id=\"tcfcb5d00d2a7453ca4d97713413e1b96\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"t3a83bc38c04145da9084c6d9c1a0cf98\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"t0f5e2c4cc8bd47079b0348fc778bdda7\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-5.776\" y=\"4.087999999999999\">C</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t36a59087cc0845a9a341e16dc5407e0a\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t45b75c0980d24f89906710d347d41352\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t3a83bc38c04145da9084c6d9c1a0cf98\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t3a83bc38c04145da9084c6d9c1a0cf98\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t0f5e2c4cc8bd47079b0348fc778bdda7\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "weighted_parsimony(newicks[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R_4(A)  = inf;\tR_4(C)  = inf;\tR_4(G)  = 0;\tR_4(T)  = inf;\t\n",
      "\n",
      "R_3(A)  = inf;\tR_3(C)  = inf;\tR_3(G)  = 0;\tR_3(T)  = inf;\t\n",
      "\n",
      "R_7(A)  = min{R_4(A)+S(A,A), R_4(C)+S(A,C), R_4(G)+S(A,G), R_4(T)+S(A,T)} + \n",
      "\t  min{R_3(A)+S(A,A), R_3(C)+S(A,C), R_3(G)+S(A,G), R_3(T)+S(A,T)} \n",
      "\t= min{inf, inf, 1, inf} + min{inf, inf, 1, inf} = 1 + 1 = 2\n",
      "R_7(C)  = min{R_4(A)+S(C,A), R_4(C)+S(C,C), R_4(G)+S(C,G), R_4(T)+S(C,T)} + \n",
      "\t  min{R_3(A)+S(C,A), R_3(C)+S(C,C), R_3(G)+S(C,G), R_3(T)+S(C,T)} \n",
      "\t= min{inf, inf, 2, inf} + min{inf, inf, 2, inf} = 2 + 2 = 4\n",
      "R_7(G)  = min{R_4(A)+S(G,A), R_4(C)+S(G,C), R_4(G)+S(G,G), R_4(T)+S(G,T)} + \n",
      "\t  min{R_3(A)+S(G,A), R_3(C)+S(G,C), R_3(G)+S(G,G), R_3(T)+S(G,T)} \n",
      "\t= min{inf, inf, 0, inf} + min{inf, inf, 0, inf} = 0 + 0 = 0\n",
      "R_7(T)  = min{R_4(A)+S(T,A), R_4(C)+S(T,C), R_4(G)+S(T,G), R_4(T)+S(T,T)} + \n",
      "\t  min{R_3(A)+S(T,A), R_3(C)+S(T,C), R_3(G)+S(T,G), R_3(T)+S(T,T)} \n",
      "\t= min{inf, inf, 2, inf} + min{inf, inf, 2, inf} = 2 + 2 = 4\n",
      "\n",
      "R_2(A)  = inf;\tR_2(C)  = inf;\tR_2(G)  = inf;\tR_2(T)  = 0;\t\n",
      "\n",
      "R_1(A)  = inf;\tR_1(C)  = 0;\tR_1(G)  = inf;\tR_1(T)  = inf;\t\n",
      "\n",
      "R_0(A)  = inf;\tR_0(C)  = inf;\tR_0(G)  = inf;\tR_0(T)  = 0;\t\n",
      "\n",
      "R_5(A)  = min{R_1(A)+S(A,A), R_1(C)+S(A,C), R_1(G)+S(A,G), R_1(T)+S(A,T)} + \n",
      "\t  min{R_0(A)+S(A,A), R_0(C)+S(A,C), R_0(G)+S(A,G), R_0(T)+S(A,T)} \n",
      "\t= min{inf, 2, inf, inf} + min{inf, inf, inf, 2} = 2 + 2 = 4\n",
      "R_5(C)  = min{R_1(A)+S(C,A), R_1(C)+S(C,C), R_1(G)+S(C,G), R_1(T)+S(C,T)} + \n",
      "\t  min{R_0(A)+S(C,A), R_0(C)+S(C,C), R_0(G)+S(C,G), R_0(T)+S(C,T)} \n",
      "\t= min{inf, 0, inf, inf} + min{inf, inf, inf, 1} = 0 + 1 = 1\n",
      "R_5(G)  = min{R_1(A)+S(G,A), R_1(C)+S(G,C), R_1(G)+S(G,G), R_1(T)+S(G,T)} + \n",
      "\t  min{R_0(A)+S(G,A), R_0(C)+S(G,C), R_0(G)+S(G,G), R_0(T)+S(G,T)} \n",
      "\t= min{inf, 2, inf, inf} + min{inf, inf, inf, 2} = 2 + 2 = 4\n",
      "R_5(T)  = min{R_1(A)+S(T,A), R_1(C)+S(T,C), R_1(G)+S(T,G), R_1(T)+S(T,T)} + \n",
      "\t  min{R_0(A)+S(T,A), R_0(C)+S(T,C), R_0(G)+S(T,G), R_0(T)+S(T,T)} \n",
      "\t= min{inf, 1, inf, inf} + min{inf, inf, inf, 0} = 1 + 0 = 1\n",
      "\n",
      "R_6(A)  = min{R_2(A)+S(A,A), R_2(C)+S(A,C), R_2(G)+S(A,G), R_2(T)+S(A,T)} + \n",
      "\t  min{R_5(A)+S(A,A), R_5(C)+S(A,C), R_5(G)+S(A,G), R_5(T)+S(A,T)} \n",
      "\t= min{inf, inf, inf, 2} + min{4, 3, 5, 3} = 2 + 3 = 5\n",
      "R_6(C)  = min{R_2(A)+S(C,A), R_2(C)+S(C,C), R_2(G)+S(C,G), R_2(T)+S(C,T)} + \n",
      "\t  min{R_5(A)+S(C,A), R_5(C)+S(C,C), R_5(G)+S(C,G), R_5(T)+S(C,T)} \n",
      "\t= min{inf, inf, inf, 1} + min{6, 1, 6, 2} = 1 + 1 = 2\n",
      "R_6(G)  = min{R_2(A)+S(G,A), R_2(C)+S(G,C), R_2(G)+S(G,G), R_2(T)+S(G,T)} + \n",
      "\t  min{R_5(A)+S(G,A), R_5(C)+S(G,C), R_5(G)+S(G,G), R_5(T)+S(G,T)} \n",
      "\t= min{inf, inf, inf, 2} + min{5, 3, 4, 3} = 2 + 3 = 5\n",
      "R_6(T)  = min{R_2(A)+S(T,A), R_2(C)+S(T,C), R_2(G)+S(T,G), R_2(T)+S(T,T)} + \n",
      "\t  min{R_5(A)+S(T,A), R_5(C)+S(T,C), R_5(G)+S(T,G), R_5(T)+S(T,T)} \n",
      "\t= min{inf, inf, inf, 0} + min{6, 2, 6, 1} = 0 + 1 = 1\n",
      "\n",
      "R_8(A)  = min{R_7(A)+S(A,A), R_7(C)+S(A,C), R_7(G)+S(A,G), R_7(T)+S(A,T)} + \n",
      "\t  min{R_6(A)+S(A,A), R_6(C)+S(A,C), R_6(G)+S(A,G), R_6(T)+S(A,T)} \n",
      "\t= min{2, 6, 1, 6} + min{5, 4, 6, 3} = 1 + 3 = 4\n",
      "R_8(C)  = min{R_7(A)+S(C,A), R_7(C)+S(C,C), R_7(G)+S(C,G), R_7(T)+S(C,T)} + \n",
      "\t  min{R_6(A)+S(C,A), R_6(C)+S(C,C), R_6(G)+S(C,G), R_6(T)+S(C,T)} \n",
      "\t= min{4, 4, 2, 5} + min{7, 2, 7, 2} = 2 + 2 = 4\n",
      "R_8(G)  = min{R_7(A)+S(G,A), R_7(C)+S(G,C), R_7(G)+S(G,G), R_7(T)+S(G,T)} + \n",
      "\t  min{R_6(A)+S(G,A), R_6(C)+S(G,C), R_6(G)+S(G,G), R_6(T)+S(G,T)} \n",
      "\t= min{3, 6, 0, 6} + min{6, 4, 5, 3} = 0 + 3 = 3\n",
      "R_8(T)  = min{R_7(A)+S(T,A), R_7(C)+S(T,C), R_7(G)+S(T,G), R_7(T)+S(T,T)} + \n",
      "\t  min{R_6(A)+S(T,A), R_6(C)+S(T,C), R_6(G)+S(T,G), R_6(T)+S(T,T)} \n",
      "\t= min{4, 5, 2, 4} + min{7, 3, 7, 1} = 2 + 1 = 3\n",
      "\n",
      "=================Final score for this tree is 3 =================\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t0126913604254b81adb5ef53d94e0c84\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"250.0px\" id=\"t6867a1ebf8054007a0c9bf2576b2eede\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 350.0 250.0\" width=\"350.0px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"t9af25d98d9134f8186098c7123963033\"><clipPath id=\"te4cbeb129ed94a059da857690e439b4a\"><rect height=\"190.0\" width=\"290.0\" x=\"30.0\" y=\"30.0\"></rect></clipPath><g clip-path=\"url(#te4cbeb129ed94a059da857690e439b4a)\"><g class=\"toyplot-mark-Text\" id=\"t3c859715ea804949a40ac194d6b71e7f\"><g class=\"toyplot-Series\"></g></g><g class=\"toyplot-mark-Graph\" id=\"tdfaed82b587644c9965371c04cb80e6c\"><g class=\"toyplot-Edges\"><path d=\"M 268.75 150.0 L 300.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 268.75 150.0 L 237.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 268.75 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 175.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 112.5 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 81.25 150.0 L 50.0 200.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 128.125 100.0 L 81.25 150.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><path d=\"M 198.4375 50.0 L 128.125 100.0\" style=\"fill:none;opacity:1;stroke:rgb(14.9%,14.9%,14.9%);stroke-linecap:round;stroke-opacity:1.0;stroke-width:2.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(50.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(112.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(175.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(237.5, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(300.0, 200.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(81.25, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(128.125, 100.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(268.75, 150.0)\"><circle r=\"0.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:rgb(40%,76.1%,64.7%);stroke-opacity:1.0\" transform=\"translate(198.4375, 50.0)\"><circle r=\"0.0\"></circle></g></g></g><g class=\"toyplot-mark-Point\" id=\"t2e2cfa1c879b4e0b83808292c221a235\"><g class=\"toyplot-Series\"><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(50.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(112.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-5.776\" y=\"4.087999999999999\">C</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(175.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(237.5, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(300.0, 200.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(81.25, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(128.125, 100.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-4.888\" y=\"4.087999999999999\">T</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(268.75, 150.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g><g class=\"toyplot-Datum\" style=\"fill:rgb(40%,76.1%,64.7%);fill-opacity:1.0;opacity:1.0;stroke:none;stroke-width:1\" transform=\"translate(198.4375, 50.0)\"><rect height=\"30.0\" width=\"37.5\" x=\"-18.75\" y=\"-15.0\"></rect><g><text style=\"fill:rgb(14.9%,14.9%,14.9%);fill-opacity:1.0;font-family:helvetica;font-size:16.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.224\" y=\"4.087999999999999\">G</text></g></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t0126913604254b81adb5ef53d94e0c84\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"t6867a1ebf8054007a0c9bf2576b2eede\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tdfaed82b587644c9965371c04cb80e6c\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"tdfaed82b587644c9965371c04cb80e6c\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[7, 7, 8, 6, 5, 5, 6, 8], [4, 3, 7, 2, 1, 0, 5, 6]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t2e2cfa1c879b4e0b83808292c221a235\",\"data\",\"point\",[\"x\", \"y0\"],[[0.0, 1.0, 2.0, 3.0, 4.0, 0.5, 1.25, 3.5, 2.375], [0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 2.0, 1.0, 3.0]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "weighted_parsimony(newicks[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(c) The second tree is preferred using weighted parsimony since it has smaller cost\n"
     ]
    }
   ],
   "source": [
    "print(\"(c) The second tree is preferred using weighted parsimony since it has smaller cost\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-8cc69ce21bfbf312",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 4: Branch and bound (40 POINTS)\n",
    "\n",
    "Implement the basic branch and bound algorithm (page 7 of the \"Searching through tree space\" lecture slides) for finding an optimal tree with an unweighted parsimony objective function.  Your implementation should be broken down into three functions, `best_tree_branch_and_bound`, `branch`, and `bound`, which you are to implement below.\n",
    "\n",
    "Some implementation specifications for each function:\n",
    "### `best_tree_branch_and_bound`\n",
    "\n",
    "* You should use the [Heap queue algorithm](https://docs.python.org/3/library/heapq.html) module functions to efficiently maintain the queue (Q) \n",
    "* Q should be sorted by lower bound of the trees, with ties broken by lexicographical ordering of the trees' newick strings.\n",
    "* The algorithm should begin with an unrooted tree consisting of the first three names in `sequence_names`, and add leaves in the order in which they appear in the sequence_names list.\n",
    "\n",
    "### `branch`\n",
    "\n",
    "* This function should call the `add_leaf` function (provided) to grow an unrooted tree with the next leaf in all possible ways\n",
    "\n",
    "### `bound`\n",
    "\n",
    "* You will likely want to take advantage of your work in the day 16 notebook for this function\n",
    "* To convert an unrooted tree to a rooted tree (such that you can use your parsimony scoring code), it is recommended that you call the provided `root` function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0db645b3e786815e",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Code for PROBLEM 4\n",
    "# You are welcome to develop your code as a separate Python module\n",
    "# and import it here if that is more convenient for you.\n",
    "\n",
    "import heapq\n",
    "import toytree\n",
    "\n",
    "def best_tree_branch_and_bound(alignment, sequence_names, branch, bound):\n",
    "    \"\"\"Computes an optimal (lowest scoring) tree using a branch and bound algorithm.\n",
    "    \n",
    "    Args:\n",
    "        alignment: a list of strings corresponding to the rows of a multiple alignment.\n",
    "        sequence_names: a list of the names of the sequences in the same order as the\n",
    "                        rows of the multiple alignment.\n",
    "        branch: a function that grows a partial tree in multiple ways\n",
    "        bound: a function that computes the lower bound of a partial tree\n",
    "    Returns:\n",
    "        A tuple (score, newick_string) where newick_string is a Newick formatted string\n",
    "        representing the optimal tree (unrooted) and score is its score.\n",
    "    \"\"\"\n",
    "    h = []\n",
    "    def push(t):\n",
    "        heapq.heappush(h, (bound(t, alignment, sequence_names), t))\n",
    "    \n",
    "    push(f\"({','.join(sequence_names[:3])});\")\n",
    "    \n",
    "    while True:\n",
    "        score, tree = heapq.heappop(h)\n",
    "        ntips = toytree.tree(tree).ntips\n",
    "        if ntips == len(sequence_names):\n",
    "            return (score, tree)\n",
    "        for t in branch(tree, sequence_names[ntips]):\n",
    "            push(t)\n",
    "    \n",
    "def branch(newick_tree, next_leaf_name):\n",
    "    \"\"\"Grows a partial unrooted tree by adding the next leaf in all possible ways.\n",
    "    \n",
    "    Args:\n",
    "        newick_tree: a partial unrooted tree as a Newick string\n",
    "        next_leaf_name: the name of the next leaf to add to the tree\n",
    "    Returns:\n",
    "        A list of Newick strings representing all possible ways in which to add the next leaf.\n",
    "    \"\"\"\n",
    "    return [add_leaf(newick_tree, next_leaf_name, i) for i in range(1, toytree.tree(newick_tree).nnodes)]\n",
    "\n",
    "def bound(newick_tree, alignment, sequence_names):\n",
    "    \"\"\"Computes a lower bound for the unweighted parsimony score of a full tree that can be \n",
    "    grown from a given partial tree.\n",
    "    \n",
    "    Args:\n",
    "        newick_tree: a partial unrooted tree as a Newick string\n",
    "        alignment: a list of strings corresponding to the rows of a multiple alignment.\n",
    "        sequence_names: a list of the names of the sequences in the same order as the\n",
    "                        rows of the multiple alignment.\n",
    "    Returns:\n",
    "        The lower bound as an integer.\n",
    "    \"\"\"\n",
    "    tree = toytree.tree(root(newick_tree))\n",
    "    return score_tree_parsimony(tree, alignment, sequence_names)\n",
    "\n",
    "def add_leaf(newick_tree, leaf_name, edge_index):\n",
    "    \"\"\"Adds a new leaf on to the specified edge in an unrooted tree.\n",
    "    \n",
    "    Args:\n",
    "        newick_tree: a partial unrooted tree as a Newick string\n",
    "        leaf_name: the name of the next leaf to add to the tree\n",
    "        edge_index: the index (from 1 to the number of edges) of the edge on\n",
    "                    which to add the leaf.  Edges are ordered by the order\n",
    "                    in which their child node is encountered in a preorder\n",
    "                    traversal of the tree.\n",
    "    Returns:\n",
    "        A newick string representing the tree with the added leaf.\n",
    "    \"\"\"\n",
    "    new_tree = toytree.tree(newick_tree)\n",
    "    if len(new_tree.treenode.children) != 3:\n",
    "        raise ValueError(\"Tree does not look unrooted: \" +  newick_tree)\n",
    "    for i, node in enumerate(new_tree.treenode.traverse(\"preorder\")):\n",
    "        if i == edge_index:\n",
    "            break\n",
    "    parent = node.up\n",
    "    node.detach()\n",
    "    new_internal_node = parent.add_child()\n",
    "    new_internal_node.add_child(node)\n",
    "    new_internal_node.add_child(name=leaf_name)\n",
    "    return new_tree.treenode.write(format=9)\n",
    "\n",
    "def root(newick_tree):\n",
    "    \"\"\"Converts an unrooted tree into a rooted tree.\n",
    "    (useful for scoring an unrooted tree with parsimony).\n",
    "    \n",
    "    Args:\n",
    "        newick_tree: an unrooted tree as a Newick string\n",
    "    Returns:\n",
    "        A rooted version of the tree as a newick string.\n",
    "    \"\"\"\n",
    "    unrooted_tree = toytree.tree(newick_tree)\n",
    "    if len(unrooted_tree.treenode.children) != 3:\n",
    "        raise ValueError(\"Tree does not look unrooted: \" +  newick_tree)\n",
    "    unrooted_tree_root = unrooted_tree.treenode\n",
    "    first_child = unrooted_tree.treenode.children[0]\n",
    "    first_child.detach()\n",
    "    rooted_tree_root = toytree.TreeNode.TreeNode()\n",
    "    rooted_tree_root.add_child(first_child)\n",
    "    rooted_tree_root.add_child(unrooted_tree_root)\n",
    "    return rooted_tree_root.write(format=9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitch_score_and_min_cost_states(tree, leaf_states):\n",
    "    \"\"\"Runs the first stage of Fitch's algorithm for\n",
    "       the given tree and character states as the leaves.\n",
    "    \n",
    "    Args:\n",
    "        tree: a toytree tree.\n",
    "        leaf_states: a dictionary mapping leaf names to characters.  \n",
    "    Returns:\n",
    "        A two-element tuple, where the first element is the minimum\n",
    "        cost of the tree (minimum number of changes required to explain\n",
    "        the leaf data) and second element is a dictionary mapping the\n",
    "        node names to sets of possible states at the nodes (the R values\n",
    "        in the algorithm)\n",
    "    \"\"\"\n",
    "    R = {}\n",
    "    num_changes = 0\n",
    "    for node in tree.treenode.traverse(\"postorder\"):\n",
    "        if node.is_leaf():\n",
    "            R[node.name] = {leaf_states[node.name]}\n",
    "        else:\n",
    "            left_states, right_states = [R[child.name] for child in node.children]\n",
    "            states_intersection = left_states & right_states\n",
    "            if states_intersection:\n",
    "                R[node.name] = states_intersection\n",
    "            else:\n",
    "                R[node.name] = left_states | right_states\n",
    "                num_changes += 1\n",
    "    return num_changes, R\n",
    "\n",
    "def alignment_leaf_states_list(alignment, sequence_names):\n",
    "    \"\"\"Returns a list of dictionaries, where each dictionary corresponds to the leaf states\n",
    "    for a column of the alignment.\"\"\"\n",
    "    return [dict(zip(sequence_names, column)) for column in zip(*alignment)]\n",
    "\n",
    "def score_tree_parsimony(tree, alignment, sequence_names):\n",
    "    \"\"\"Computes the parsimony score for a given tree and alignment.\n",
    "    \n",
    "    Args:\n",
    "        tree: a toytree tree object\n",
    "        alignment: a list of strings corresponding to the rows of a multiple alignment.\n",
    "        sequence_names: a list of the names of the sequences in the same order as the\n",
    "                        rows of the multiple alignment.\n",
    "    Returns:\n",
    "        The parsimony score (a number)\n",
    "    \"\"\"\n",
    "    columns = alignment_leaf_states_list(alignment, sequence_names)\n",
    "    fitch_results = [fitch_score_and_min_cost_states(tree, column) for column in columns]\n",
    "    column_scores, column_Rs = zip(*fitch_results)\n",
    "    return sum(column_scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-74ce6b4272ffdd9b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Tests for PROBLEM 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-34048ad0320bda93",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Data sets for testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-34048",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "import fasta\n",
    "def read_names_and_alignments_from_fasta(filename):\n",
    "    return zip(*fasta.read_sequences_from_fasta_file(filename))\n",
    "\n",
    "v3_sequence_names, v3_alignment = read_names_and_alignments_from_fasta(\"v3_alignment.fasta\")\n",
    "\n",
    "v3_big_sequence_names, v3_big_alignment = read_names_and_alignments_from_fasta(\"v3_big_alignment.fasta\")\n",
    "\n",
    "medium_num_seqs = 7\n",
    "v3_medium_alignment = v3_big_alignment[:medium_num_seqs]\n",
    "v3_medium_sequence_names = v3_big_sequence_names[:medium_num_seqs]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch3",
     "locked": true,
     "points": 4,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: branch passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for branch3\n",
    "assert sorted(branch('(D,PA,PB);', 'C1')) == ['(D,PA,(PB,C1));', \n",
    "                                              '(D,PB,(PA,C1));', \n",
    "                                              '(PA,PB,(D,C1));']\n",
    "print(\"SUCCESS: branch passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch4",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: branch4 passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for branch4\n",
    "assert sorted(branch('(D,PA,(PB,C1));', 'C2')) == ['(D,(PB,C1),(PA,C2));',\n",
    "                                                   '(D,PA,((PB,C1),C2));',\n",
    "                                                   '(D,PA,(C1,(PB,C2)));',\n",
    "                                                   '(D,PA,(PB,(C1,C2)));',\n",
    "                                                   '(PA,(PB,C1),(D,C2));']\n",
    "print(\"SUCCESS: branch4 passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch5",
     "locked": true,
     "points": 3,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: branch5 passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for branch5\n",
    "assert sorted(branch('(D,(PB,C1),(PA,C2));', 'C3')) == ['((PB,C1),(PA,C2),(D,C3));',\n",
    "                                                        '(D,(C1,(PB,C3)),(PA,C2));',\n",
    "                                                        '(D,(PA,C2),((PB,C1),C3));',\n",
    "                                                        '(D,(PB,(C1,C3)),(PA,C2));',\n",
    "                                                        '(D,(PB,C1),((PA,C2),C3));',\n",
    "                                                        '(D,(PB,C1),(C2,(PA,C3)));',\n",
    "                                                        '(D,(PB,C1),(PA,(C2,C3)));']\n",
    "print(\"SUCCESS: branch5 passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "bound_one_column",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: bound_one_column passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for bound_one_column\n",
    "v3_alignment_column0 = [s[0] for s in v3_alignment]\n",
    "v3_alignment_column3 = [s[3] for s in v3_alignment]\n",
    "v3_alignment_column29 = [s[29] for s in v3_alignment]\n",
    "assert bound('(D,PA,PB);', v3_alignment_column0, v3_sequence_names) == 0\n",
    "assert bound('(D,PA,PB);', v3_alignment_column3, v3_sequence_names) == 1\n",
    "assert bound('((C1,C2),(PA,PB),D);', v3_alignment_column29, v3_sequence_names) == 1\n",
    "print(\"SUCCESS: bound_one_column passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "bound_alignment",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: bound_alignment passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for bound_alignment\n",
    "assert bound('(D,PA,PB);', v3_alignment, v3_sequence_names) == 25\n",
    "assert bound('((D, C1),PA,PB);', v3_alignment, v3_sequence_names) == 48\n",
    "assert bound('((C1,PA),(C2,PB),D);', v3_alignment, v3_sequence_names) == 64\n",
    "print(\"SUCCESS: bound_alignment passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0b40486d279ff93d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "class CallCounter:\n",
    "    def __init__(self, func):\n",
    "        self._func = func\n",
    "        self._num_calls = 0\n",
    "    def __call__(self, *args, **kwds):\n",
    "        self._num_calls += 1\n",
    "        return self._func(*args, **kwds)\n",
    "    def num_calls(self):\n",
    "        return self._num_calls\n",
    "    def reset(self):\n",
    "        self._num_calls = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch_and_bound_v3",
     "locked": true,
     "points": 8,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: branch_and_bound_v3 passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for branch_and_bound_v3\n",
    "counting_bound = CallCounter(bound)\n",
    "assert best_tree_branch_and_bound(v3_alignment, v3_sequence_names, branch, counting_bound) == (58, '(D,PA,(PB,(C1,C2)));')\n",
    "assert counting_bound.num_calls() == 19\n",
    "print(\"SUCCESS: branch_and_bound_v3 passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch_and_bound_v3_medium",
     "locked": true,
     "points": 7,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUCCESS: branch_and_bound_v3 passed all tests\n"
     ]
    }
   ],
   "source": [
    "# tests for branch_and_bound_v3_medium\n",
    "counting_bound = CallCounter(bound)\n",
    "assert best_tree_branch_and_bound(v3_medium_alignment, v3_medium_sequence_names, branch, counting_bound) == (75, '(C09,(C35,(PD1,PD3)),(PA5,(PB6,PB8)));')\n",
    "assert counting_bound.num_calls() == 133\n",
    "print(\"SUCCESS: branch_and_bound_v3 passed all tests\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": true,
     "grade_id": "branch_and_bound_v3_big",
     "locked": true,
     "points": 5,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# tests for branch_and_bound_v3_big\n",
    "###\n",
    "### AUTOGRADER TEST - DO NOT REMOVE\n",
    "###\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3 [3.6]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}