testing_tree_utils.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## testing out functions in tree_utils.py\n",
    "first, lets load in the necessary libraries..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import tree_utils\n",
    "import pickle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### visualizing graphs\n",
    "first, we can create a grid graph and use the `draw()` function to look at it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOYAAADmCAYAAADBavm7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJG0lEQVR4nO3csWtTewPG8eccDklpbLFYdJJGutXBRYnSDLrb/V7s2NV/oUXhDp3dLuoUN53yL+jlBl0c6lZscbKkVGoDaQk9dygWy1uS3zknJ+8zfD9wJv3Fg4/fhoZTozRNUwGwEv+/bwDA/yJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ0neg98P+3rT2dXHrwc6Oh7oSjXRvVtzWm0s6Prs1DjvEUOwg4dx7xBlffJnp9vTs/aW/tnelyQdD07Pf62axEolLS9e08bKbdXna5lvCGHYwUNZO2QK8/O3H1p92dHRyUDDTsWRVKskaq01dOfm1eCbQRh28FDmDsFh7nR7evzivY6OB0EvLEkz1UTtp02+Yo8RO3goe4fgD3+etbfUOwm/CUnqnQz0vP0l0xkMxw4eyt4hKMzvh3192N4f+nZ9mdNUer/d1d5hP9tBXIodPExih6Aw33R2FWW7h3ORpFZnN+dp/I4dPExih6AwP349uPBpUxbHg1NtvnqrKIq4Cl6br9+xg8FVdIdPOwcjf19QmFm+wb30D6lOFzqPM3Gl2N8jO4xH0R1+9kf3FBTmlWru5xAkSY+aD5SmKVfB6+HyfXYwuIruMDM1uqegMO/dmlM1yff0XjWJdbc+l+ssLmIHD5PYIejVnzQWlPc/BkolrTYWcp7G79jBwyR2CArzxuyUlhevKc74UVQcSc3FeZ7ZHBN28DCJHYLfjzdWbqtWyfa9Zq2SaH1lKdMZDMcOHsreITjM+nxNrbWGZqrJyK8UcXT2+FFrrcFjYGPGDh7K3iHXT5c8b3/Rh+2upMufpm8uzmt9ZYl/DCViBw9l7ZA5zF/2DvtqdXa1+eqt4uq0HjUf6G6dnwOcNHbwMO4dcod5/gLR2ft4wZdBQezgYVw78F+LAIYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwFCS9+D3w77edHZ1/Y+/FFem9eff/+rerTmtNhZ0fXZqnPeIIdjBw7h3iNI0TbMc2On29Ky9pX+29yVJx4PT81+rJrFSScuL17Sxclv1+VrmG0IYdvBQ1g6Zwvz87YdWX3Z0dDLQsFNxJNUqiVprDd25eTX4ZhCGHTyUuUNwmDvdnh6/eK+j40HQC0vSTDVR+2mTr9hjxA4eyt4h+MOfZ+0t9U7Cb0KSeicDPW9/yXQGw7GDh7J3CArz+2FfH7b3h75dX+Y0ld5vd7V32M92EJdiBw+T2CEozDedXUXZ7uFcJKnV2c15Gr9jBw+T2CEozI9fDy582pTF8eBUm6/eKooiroLX5ut37GBwFd3h087ByN8XFGaWb3Av/UOq04XO40xcKfb3yA7jUXSHn/3RPQWFeaWa+zkESdKj5gOlacpV8Hq4fJ8dDK6iO8xMje4pKMx7t+ZUTfI9vVdNYt2tz+U6i4vYwcMkdgh69SeNBWX8AOpcKmm1sZDzNH7HDh4msUNQmDdmp7S8eE1xxo+i4khqLs7zzOaYsIOHSewQ/H68sXJbtUq27zVrlUTrK0uZzmA4dvBQ9g7BYdbna2qtNTRTTUZ+pYijs8ePWmsNHgMbM3bwUPYOuX665Hn7iz5sdyVd/jR9c3Fe6ytL/GMoETt4KGuHzGH+snfYV6uzq81XbxVXp/Wo+UB36/wc4KSxg4dx75A7zPMXiM7exwu+DApiBw/j2oH/WgQwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGCBMwRJiAIcIEDBEmYIgwAUOECRgiTMAQYQKGkrwHvx/29aazq+t//KW4Mq0///5X927NabWxoOuzU+O8RwzBDh7GvUOUpmma5cBOt6dn7S39s70vSToenJ7/WjWJlUpaXrymjZXbqs/XMt8QwrCDh7J2yBTm528/tPqyo6OTgYadiiOpVknUWmvozs2rwTeDMOzgocwdgsPc6fb0+MV7HR0Pgl5YkmaqidpPm3zFHiN28FD2DsEf/jxrb6l3En4TktQ7Geh5+0umMxiOHTyUvUNQmN8P+/qwvT/07foyp6n0frurvcN+toO4FDt4mMQOQWG+6ewqynYP5yJJrc5uztP4HTt4mMQOQWF+/Hpw4dOmLI4Hp9p89VZRFHEVvDZfv2MHg6voDp92Dkb+vqAws3yDe+kfUp0udB5n4kqxv0d2GI+iO/zsj+4pKMwr1dzPIUiSHjUfKE1TroLXw+X77GBwFd1hZmp0T0Fh3rs1p2qS7+m9ahLrbn0u11lcxA4eJrFD0Ks/aSwo4wdQ51JJq42FnKfxO3bwMIkdgsK8MTul5cVrijN+FBVHUnNxnmc2x4QdPExih+D3442V26pVsn2vWaskWl9ZynQGw7GDh7J3CA6zPl9Ta62hmWoy8itFHJ09ftRaa/AY2Jixg4eyd8j10yXP21/0Ybsr6fKn6ZuL81pfWeIfQ4nYwUNZO2QO85e9w75anV192jnQz/5AM1OJ7tb5OcBJYwcP494hd5gAysN/LQIYIkzAEGEChggTMESYgCHCBAwRJmDoP81nQ78f7+xQAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 216x216 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = nx.grid_graph(dim=(3,3)) # change the dimensions of the graph, the plot will resize\n",
    "tree_utils.draw(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we can also add colors to the edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOYAAADmCAYAAADBavm7AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJP0lEQVR4nO3cv08T/wPH8dddLj1CwUgkOhkgbDq4aKqhg+7yF8jI6r+A0Y3ZVZjqBlP/BTVpcPkMuhEhThIIhh9JIQ33HfhIMF8+5X13vfIano/kJrl64cWzDc2VKMuyTACsxDd9AQD+H2EChggTMESYgCHCBAwRJmCIMAFDhAkYSoqe+Ougq4+dbW382NfRSU9jaaInMxNaaEzp7q2RQV4j+mAHD4PeIcp758/W7rHetr/py+aeJOmkd3bxb2kSK5M0N3tHb+YfanqynvuCEIYdPFS1Q64w//n5WwsfOjo67anfWXEk1WuJWosNPbp/O/hiEIYdPFS5Q3CYW7vHevn+k45OekEPLEnjaaL26ybP2APEDh6q3iH4zZ+37W86Pg2/CEk6Pu3pXft7rnPQHzt4qHqHoDB/HXT1eXOv78v1Vc4y6dPmrnYOuvlOxJXYwcMwdggK82NnW1G+a7gQSWp1tguejcvYwcMwdggKc+PH/l/vNuVx0jvT8sqaoijiKHksr66zg8FRdoevW/vXfl1QmHl+wb3yP0lHS52Pc3Gt3PeRHQaj7A6H3et7CgpzLC18H4Ik6UXzmbIs4yh5PJ97yg4GR9kdxkeu7ykozCczE0qTYnfvpUmsx9MThc7F39jBwzB2CHr0V40pFf3DQJmkhcZUwbNxGTt4GMYOQWHeuzWiudk7inO+FRVHUnN2kns2B4QdPAxjh+DX4zfzD1Wv5ftds15LtDT/INc56I8dPFS9Q3CY05N1tRYbGk+Ta58p4uj89qPWYoPbwAaMHTxUvUOhT5e8a3/X581dSVffTd+cndTS/AN+GCrEDh6q2iF3mH/sHHTV6mxreWVNcTqqF81nejzN5wCH7c8OX1fWdJiOapwdbsSgeygc5sUDROev4yUfBmX9u4PY4UYNqgf+tAhgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMRVmWZUVO/HXQ1cfOtpZX1xXXRvV87qmezExooTGlu7dGBn2d+A9/dthYXddRbVRj7HAjBt1D7jC3do/1tv1NXzb3JEknvbOLf0uTWJmkudk7ejP/UNOT9dwXhDDs4KGqHXKF+c/P31r40NHRaU/9zoojqV5L1Fps6NH928EXgzDs4KHKHYLD3No91sv3n3R00gt6YEkaTxO1Xzd5xh4gdvBQ9Q7Bb/68bX/T8Wn4RUjS8WlP79rfc52D/tjBQ9U7BIX566Crz5t7fV+ur3KWSZ82d7Vz0M13Iq7EDh6GsUNQmB8724ryXcOFSFKrs13wbFzGDh6GsUNQmBs/9v96tymPk96Zvq6sSVHEUfLYWF1nB4Oj9A5b+9d+XVCYeX7BvcphOlrqfJw7qpX7PrLDYJTeoXt9T0FhjqVJqQsZbz6Tsoyj5DE295QdDI7SO4xc31NQmE9mJpQmxe7eS5NYj6cnCp2Lv7GDh2HsEPTorxpTygpdhpRJWmhMFTwbl7GDh2HsEBTmvVsjmpu9ozjKdxFxJDVnJ7lnc0DYwcMwdgh+PX4z/1D1Wr7fNeu1REvzD3Kdg/7YwUPVOwSHOT1ZV2uxofE0ufaZIo7Obz9qLTa4DWzA2MFD1TsU+nTJu/Z3fd7clXT13fTN2UktzT/gh6FC7OChqh0Kfx5z56CrVmdbyytritNRvWg+0+NpPgc4bH92+LqypsN0VOPscCMG3UPhMC8eIDp/HS/5MCjr3x3EDjdqUD3wp0UAQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgiDABQ4QJGCJMwBBhAoYIEzBEmIAhwgQMESZgKMqyLCty4q+Drj52trW8uq64Nqrnc0/1ZGZCC40p3b01MujrxH/4s8PG6rqOaqMaY4cbMegecoe5tXust+1v+rK5J0k66Z1d/FuaxMokzc3e0Zv5h5qerOe+IIRhBw9V7ZArzH9+/tbCh46OTnvqd1YcSfVaotZiQ4/u3w6+GIRhBw9V7hAc5tbusV6+/6Sjk17QA0vSeJqo/brJM/YAsYOHqncIfvPnbfubjk/DL0KSjk97etf+nusc9McOHqreISjMXwddfd7c6/tyfZWzTPq0uaudg26+E3EldvAwjB2CwvzY2VaU7xouRJJane2CZ+MydvAwjB2Cwtz4sf/Xu015nPTOtLyypiiKOEoey6vr7GBwlN3h69b+tV8XFGaeX3Cv/E/S0VLn41xcK/d9ZIfBKLvDYff6noLCHEuTUhfyovlMWZZxlDyezz1lB4Oj7A7jI9f3FBTmk5kJpUmxu/fSJNbj6YlC5+Jv7OBhGDsEPfqrxpQK3bcnKZO00JgqeDYuYwcPw9ghKMx7t0Y0N3tHcc63ouJIas5Ocs/mgLCDh2HsEPx6/Gb+oeq1fL9r1muJluYf5DoH/bGDh6p3CA5zerKu1mJD42ly7TNFHJ3fftRabHAb2ICxg4eqdyj06ZJ37e/6vLkr6eq76Zuzk1qaf8APQ4XYwUNVOxT+PObOQVetzra+bu3rsNvT+Eiix9N8DnDY2MHDoHcoHCaA6vCnRQBDhAkYIkzAEGEChggTMESYgCHCBAz9D2gRrrg0TRKyAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 216x216 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# make all edges connected to node (1,1) red\n",
    "for u, v, data in graph.edges(data=True):\n",
    "    if (1,1) in (u,v): # make all edges connected to node (1,1) red\n",
    "        data['colors'] = 'red'\n",
    "    else:\n",
    "        data['colors'] = 'black'\n",
    "tree_utils.draw(graph, edge_colors='c')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### drawing different spanning trees \n",
    "we can use the `uniform_random_spanning_tree()` function to draw USTs on a grid.\n",
    "\n",
    "adding the optional `delay` argument lets us reflect on the graph for a while."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAADmCAYAAADBT66SAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAMBklEQVR4nO3dvW4TaxuF4TWesbGJ7EAqW4qIoDACQW0o0kbKAVABlSmoKOA4oKUJDX8FJxApbQpCiUBCWGxQJEuEip8I4mAPs4t8e5OPIBHnfTbDPL4vKV38xtyEZRhjJ8qyLBMAwI1S3ncAAGCLYQcAZxh2AHCGYQcAZxh2AHCGYQcAZxh2AHAmsT5wMEy1/Pyt7qy+Uf/9lgajVNUk1uzRmrrzx7V4pqVqObb+sq7Q0AYdbdDRxu/sGFm9QGl7lOrmSk8P1taVSfryNd3zOVOVnTt98dycbiy0dSjhm2E3Gtqgow062sijo8mwf9wa6vLSE/XebWow+vbLz68mJbWbdd3rdjRdK4d+eRdoaIOONuhoI6+OwcO+PUp14fZjvdj4pGG6/6PKcaTTrYYeXT0/8Y/yNLRBRxt0tJFnx+AnT2+u9NR7tznWHZekYZrp5cambq30Qu9C4dHQBh1t0NFGnh2Dhn0wTPVgbX1f/8T46e1H33T/ybq2R3uvOU0KGtqgow062si7Y9CwLz9/q+AL9Jm0/Gwj9JTCoqENOtqgo428OwYN+53VNz99hnccn7+mWlp9HXRGkdHQBh1t0NFG3h2D/h97//1WyM3/9fRVX1EUmZxVNLPXHiquNYLPmeSGEh2t0NGGVcf+h4NtbNg1dqPraFG5YnJOEUWJza99khtKdLRCRxtWHQfDHK6xV43+S9PMdF1Zlk3kx0yjTkM6/jEfdPyzOh70lahBwz57tBZy8+/nHLE5p4hoaIOONuhoI++OQcPenT+uw5Wwv7VPVWJdmT8RdEaR0dAGHW3Q0UbeHYOGffFMS8FPj0TS4tlm6CmFRUMbdLRBRxt5dwy7xl6OdfHcnKrJwY6pJiVd6sxN9MuPaWiDjjboaCPvjsFvKXBjoa12s65yPN7jUyUu6WSzrusL7dC7UHg0tEFHG3S0kWfH4GE/lMS61+3oVKux70enalLSqVZdd7udiX9kl2hohY426Ggjz46m78d+a6Wn+2vrknZeNfWjqUosRZEudY7pOu/dvAcNbdDRBh1t5NHRbNj/sT1KtfxsQ0urr9X/sKXBMFW1HGv2SE1X5k9o8WyT3/xf2N3w6au+onJFM9N1Go6J70UbdLTxOzuaDzts/fOybH6bAOwXP8waAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAGYYdAJxh2AHAmSjLsszywMEw1fLzt7qz+kb991sajFJVk1izR2vqzh/X4pmWquXY8ku6s7vh07/6ipKKZhp1Go6J70UbdLTxOzuaDfv2KNXNlZ4erK0rk/Tla7rnc6YqO3f64rk53Vho61DCN8NuNLRBRxt0tJFHR5Nh/7g11OWlJ+q929Rg9O2Xn19NSmo367rX7Wi6Vg798i7Q0AYdbdDRRl4dg4d9e5Tqwu3HerHxScN0/0eV40inWw09unp+4h/laWiDjjboaCPPjsFPnt5c6an3bnOsOy5JwzTTy41N3Vrphd6FwqOhDTraoKONPDsGDftgmOrB2vq+/onx09uPvun+k3Vtj/Zec5oUNLRBRxt0tJF3x6BhX37+VsEX6DNp+dlG6CmFRUMbdLRBRxt5dwwa9jurb376DO84Pn9NtbT6OuiMIqOhDTraoKONvDsmIV+4/34r5Obfz/lgc04R0dCGVcenr/qKosjkrCKavfZQca0RfA4dbToe9M912DV2o+tog+HkXo+joQ2rjlG5YnJOUUWJza+fjja//oP+uQ4a9qrRf2ma5Fet0dCGVceZ6bqyLJvYj5lGnY5/UMeD/rkOGvbZo7WQm38/54jNOUVEQxt0tEFHG3l3DBr27vxxHa6E/U1pqhLryvyJoDOKjIY26GiDjjby7hg07ItnWgp+eiSSFs82Q08pLBraoKMNOtrIu2PYNfZyrIvn5lRNDnZMNSnpUmduol9+TEMbdLRBRxt5dwx+S4EbC221m3WV4/EenypxSSebdV1faIfehcKjoQ062qCjjTw7Bg/7oSTWvW5Hp1qNfT86VZOSTrXqutvtTPwju0RDK3S0QUcbeXY0fT/2Wys93V9bl7TzqqkfTVViKYp0qXNM13nv5j1oaIOONuhoI4+O5j9BaXuUavnZhpZWX++8+qxc0cx0XbNHaroyf0KLZ5v85v8CDW3Q0cbujv0PWxoMU1XLMR3H9Du/H82H/f8O/99Liv/DL+EeDW3QEX+S//r7kR9mDQDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4AzDDgDOMOwA4EyUZVlmeeBgmGr5+VvdWX2jp3/1FSUVzTTqmj1aU3f+uBbPtFQtx5Zf0h0a2qCjjd0d+++3NBilqiYxHcf0O78fzYZ9e5Tq5kpPD9bWlUn68jXd8zlTlZ07ffHcnG4stHUo4ZthNxraoKMNOtrIo6PJsH/cGury0hP13m1qMPr2y8+vJiW1m3Xd63Y0XSuHfnkXaGiDjjboaCOvjsHDvj1KdeH2Y73Y+KRhuv+jynGk062GHl09P/GP8jS0QUcbdLSRZ8fgJ09vrvTUe7c51h2XpGGa6eXGpm6t9ELvQuHR0AYdbdDRRp4dg4Z9MEz1YG19X//E+OntR990/8m6tkd7rzlNChraoKMNOtrIu2PQsC8/f6vgC/SZtPxsI/SUwqKhDTraoKONvDsGDfud1Tc/fYZ3HJ+/plpafR10RpHR0AYdbdDRRt4dk5Av3H+/FXLzfz191VcURSZnFc3stYeKa43gcya5oURHK1Yd+x9stqGorLbxoB3DrrEbXUeLyhWTc4ooSmx+7ZPcUKKjFauOg+GEX2M32saDdgwa9qrRf2mama4ry7KJ/Jhp1GlIxz/mw6rjpL8S1WobD9oxaNhnj9ZCbv79nCM25xQRDW3Q0QYdbeTdMWjYu/PHdbgS9sg0VYl1Zf5E0BlFRkMbdLRBRxt5dwwa9sUzLQU/zRRJi2eboacUFg1t0NEGHW3k3THsGns51sVzc6omBzummpR0qTM30S8/pqENOtqgo428Owa/pcCNhbbazbrK8XiPT5W4pJPNuq4vtEPvQuHR0AYdbdDRRp4dg4f9UBLrXrejU63Gvh+dqklJp1p13e12Jv6RXaKhFTraoKONPDuavh/7rZWe7q+tS9p51dSPpiqxFEW61Dmm67x38x40tEFHG3S0kUdH85+gtD1KtfxsQ0urr9X/sKXBMFW1HGv2SE1X5k9o8WyT3/xfoKENOtqgo43f2dF82AEA+eKHWQOAMww7ADjDsAOAMww7ADjDsAOAMww7ADjzNy7bbR4+RuY+AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 360x216 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = nx.grid_graph(dim=(3,5))\n",
    "for i in range(20):\n",
    "    UST = tree_utils.uniform_random_spanning_tree(graph)\n",
    "    tree_utils.draw(UST, delay=.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we can also use the `random_minimum_spanning_tree()` function to draw MSTs on the grid in the same way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAS4AAADmCAYAAABrjGguAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAALsElEQVR4nO3cz2obZxuG8fvVSKM6I8vFDVZoV0HGC2df4kVJCMmuB+AjMMmmB9NNgo/ApoES6M5ZJHThM/DCRGgViIwwIdJgrH/zLUI/jHEcvRq9Yx7r+oF21mh6M71QLGtclmWZAMCQ0k2fAAD4IlwAzCFcAMwhXADMIVwAzCFcAMwhXADMKc/rQO1uqg8nfaXnIyXVstbXarp/N5nX4Rce+4bDtuGE2jZXuIbjiQ6OOnr1rqXjTk+VckmTLFPJOQ1HE200lvX8cVPPNhuqRLy588W+4bBtOEVs62b9y/mPn8+0vXuo03Sg9Hz8zZ9LqpFWk1j7O1v6+celmU5yEbFvOGwbTlHbzhSuj5/P9Puf/+rL2UjjKZ4eOaf6Uln//PGbfuEC+C72DYdtwylyW+/3acPxRNu7h1OfnCSNs0xfzkba3j3UcDzxfcmFwr7hsG04RW/rHa6Do45O08HUJ/efcZbptD/Q26OO70suFPYNh23DKXpb73C9ete69t+u10kHY71835rpuYuCfcNh23CK3tYrXO1uquNOz+sFLjv+1FO7m+Y6xm3FvuGwbTg3sa1XuD6c9FUp5/toOO339ODhEznneFx6PNh6orSf7wKoRCW1Tvq5jnEbzePaZdur3cS2Xq+Wno80yXnfQeecXMynM1cpxXfknMt1jEmWKR2M5nRGt8c8rl22vdpNbOsVrqRaVinn/1gr9brevN5XlmU8Lj3+/mtPKyv1XPuWnFMSz+0LEbfGPK5dtr3aTWzrFa71tZqGo3wfCQ/HEzXXarmOcVuxbzhsG85NbOsVrvt3E200lr1P6qKNe8t8D+wb2Dcctg3nJrb1/o3a88dNJdXI92mSpCSO9OJRc6bnLgr2DYdtwyl6W+9wPdtsaDWJFXn+mzYqOa3WYj3dbPi+5EJh33DYNpyit/UOVyUqaW9nS/Wl8tQnGTmn+g9l7e9s8U3772DfcNg2nKK3zX93iP5A6eCab4HHkX6qVbW385Bv2Htg33DYNpyitp05XNLXTwLeHnX08n1Lx596Svs9Oee0Uq9rOJ5o496yXjxq6in3NJrJ5X0r0YX7GrFvLly74RSxba5wXdTupl//Ij5e0pvX+2pyF8m5andTtU76SgcjJXGZfeeIazecUNvOLVyS/v9X33M8JFAIrt1wQmzLe2AA5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmEC4A5hAuAOYQLgDmlOd1oHY31dL6ryrFd3Rw1NH6Wk337ybzOvzCa3dTfTjpKz0fKamW2XeOuHbDCbWty7Ism/XJw/FEB0cdvXrX0nGnp7Tfk3NOKyt1DUcTbTSW9fxxU882G6pEvLnzdXnfSrmkSZap5Bz75sS1G04R284cro+fz7S9e6jTdKD0fPzNn0uqkVaTWPs7W/r5x6WZTnIRsW84bBtOUdvOFK6Pn8/0+5//6svZSOMpnh45p/pSWf/88Zt+4QL4LvYNh23DKXJb7/dpw/FE27uHU5+cJI2zTF/ORtrePdRwPPF9yYXCvuGwbThFb+sdroOjjk7TwdQn959xlum0P9Dbo47vSy4U9g2HbcMpelvvcL1617r2367XSQdjvXzfmum5i4J9w2HbcIre1itc7W6q407P6wUuO/7UU7ub5jrGbcW+4bBtODexrVe4Ppz0VSnn+2g47ff04OETOed4XHo82HqitJ/vAmBftrW4bSUqqXXSn/rnvSqUno80mf3PviTp639szKczVynFd+Scy3UM9r0a24Yzj20nWaZ0MJr+NX0OnlTLKuU8wZV6XW9e7yvLMh6XHn//taeVlTr7sq2pxzy2LTmnJJ7+izxe4Vpfq2k4yveR8HA8UXOtlusYtxX7hsO24dzEtl7hun830UZj2fukLtq4t8z3wL6BfcNh23BuYlvv37Q/f9xUUo18nyZJSuJILx41Z3ruomDfcNg2nKK39Q7Xs82GVpNYkefvuqKS02ot1tPNhu9LLhT2DYdtwyl6W+9wVaKS9na2VF8qT32SkXOq/1DW/s4W37T/DvYNh23DKXrb/HeH6A+UDq75Fngc6adaVXs7D/mGvQf2DYdtwylq29z343p71NHL9y0df+qpEl24X9R4oo17y3rxqKmn3NNoJuwbzuVt/3/PqHqdbXMq4rrNFa6L2t1UrZO+0sFISVxWk7tIzhX7htPupl//Ij5e0pvX+2w7R6Gu27mFC7Dsv7/85n8HG3gPDMAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwBzCBcAcwgXAHMIFwJzyvA7U7qb6cNJXej5SUi1rfa2m+3eTeR1+4bFvOO1uqqX1X1WK7+jgqMO2cxTqunVZlmWzPnk4nujgqKNX71o67vRUKZc0yTKVnNNwNNFGY1nPHzf1bLOhSsSbO1/sG87lbdN+T845razU2TanIq7bmcP18fOZtncPdZoOlJ6Pv/lzSTXSahJrf2dLP/+4NNNJLiL2DYdtwylq25nC9fHzmX7/8199ORtpPMXTI+dUXyrrnz9+0y9cAN/FvuGwbThFbuv9Pm04nmh793Dqk5OkcZbpy9lI27uHGo4nvi+5UNg3HLYNp+htvcN1cNTRaTqY+uT+M84ynfYHenvU8X3JhcK+4bBtOEVv6x2uV+9a1/7b9TrpYKyX71szPXdRsG84bBtO0dt6havdTXXc6Xm9wGXHn3pqd9Ncx7it2Dcctg3nJrb1CteHk74q5XwfDaf9nh48fCLnHI9LjwdbT5T2810A7Mu2FretRCW1TvpT/7xXhdLzkSaz/9mXJH39j435dOYqpfiOnHO5jsG+V2PbcOax7STLlA5G07+mz8GTalmlnCe4Uq/rzet9ZVnG49Lj77/2tLJSZ1+2NfWYx7Yl55TE03+Rxytc62s1DUf5PhIejidqrtVyHeO2Yt9w2Dacm9jWK1z37ybaaCx7n9RFG/eW+R7YN7BvOGwbzk1s6/2b9uePm0qqke/TJElJHOnFo+ZMz10U7BsO24ZT9Lbe4Xq22dBqEivy/F1XVHJarcV6utnwfcmFwr7hsG04RW/rHa5KVNLezpbqS+WpTzJyTvUfytrf2eKb9t/BvuGwbThFb5v/7hD9gdLBNd8CjyP9VKtqb+ch37D3wL7hsG04RW2b+35cb486evm+peNPPVWiC/fdGU+0cW9ZLx419ZR7Gs2EfcNh23CK2DZXuC5qd1O1TvpKByMlcVlN7iI5V+wbDtuGE2rbuYULAIrCe2AA5hAuAOYQLgDmEC4A5hAuAOYQLgDm/A+8fy4eIu65iwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 288x216 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = nx.grid_graph(dim=(3,4))\n",
    "for i in range(10):\n",
    "    MST = tree_utils.random_minimum_spanning_tree(graph)\n",
    "    tree_utils.draw(MST, delay=.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### counting the number of spanning trees\n",
    "the `find_NST()` function computes the number of spanning trees that can be drawn on the graph. as currently implemented, it is only accurate up to 6x6 grids. **TODO: change this to Parker's function**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "on a 4x4 grid: 100,352 \n",
      "   true value: 100,352\n",
      "on a 7x7 grid: 19,872,369,301,840,785,408 \n",
      "   true value: 19,872,369,301,840,986,112\n"
     ]
    }
   ],
   "source": [
    "graph = nx.grid_graph(dim=(4,4))\n",
    "num_4x4_STs = tree_utils.find_NST(graph)\n",
    "print(\"on a 4x4 grid: {:,} \\n   true value: 100,352\".format(num_4x4_STs))\n",
    "\n",
    "graph = nx.grid_graph(dim=(7,7))\n",
    "num_7x7_STs = tree_utils.find_NST(graph)\n",
    "print(\"on a 7x7 grid: {:,} \\n   true value: 19,872,369,301,840,986,112\".format(num_7x7_STs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### enumerating spanning trees on a grid\n",
    "we can enumerate all possible spanning trees (STs) on a grid like so:\n",
    "* consider a *seed* ST. \n",
    "* say that a *neighboring* ST of our seed ST is one that has precisely one edge in a different place.\n",
    "* find all the neighbors of our seed ST and store them as the *1-neighbors* of our seed ST.\n",
    "* loop through each 1-neighbor and start again, finding its own neighbors. if it has a neighbor we haven't seen before, store it as a *2-neighbor* of the ST.\n",
    "* loop through the 2-neighbors, etc., until the number of distinct *0-n neighbors* is the same as the number of STs we're looking for\n",
    "\n",
    "the function `enumerate_STs()` does the above work. the only required argument is the dimensions of the grid graph, but you can also let it randomize the seed by passing in a `seed=int` argument. it enumerates up to 3x3 grids nearly instantaneously, takes about 30s for a 3x4 grid, and about an hour and a half for a 4x4 grid. I've gotten it down to 35 minutes for 4x4 with some speedups, but open to new ideas..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0-neighbors: 1\n",
      "1-neighbors: 8\n",
      "2-neighbors: 6\n",
      "3-neighbors: 0\n",
      "---\n",
      "15 unique STs\n",
      "CPU times: user 47.6 ms, sys: 9.8 ms, total: 57.4 ms\n",
      "Wall time: 52.6 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "neighbors = tree_utils.enumerate_STs((2,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "then, we can unpack all the spanning trees into a list and sample from them, using either our UST or MST algorithms, in order to see their distributions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "STs = tree_utils.unpack_enumerated_STs(neighbors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_trials = 100000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 100000/100000 [00:34<00:00, 2873.39it/s]\n"
     ]
    }
   ],
   "source": [
    "UST_data = tree_utils.sample_STs(STs, \"UST\", num_trials)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 100000/100000 [00:38<00:00, 2619.84it/s]\n"
     ]
    }
   ],
   "source": [
    "MST_data = tree_utils.sample_STs(STs, \"MST\", num_trials)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA6gAAADXCAYAAAAX3XyhAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAtNElEQVR4nO3df7xlVV3/8debGUGwAhUbDdBBwXKM8scIpmaXSIVKxwoSIsLC+FqRmfg17AcR/dJK0URTUoKIGgx/MOUoljj69UcEqMUPQ0ecZPAH8lMRAUc+3z/Wvs7hzLn3njtz75xzLq/n47Ef55y119pn7bP2Pud89lp771QVkiRJkiSN2i6jroAkSZIkSWCAKkmSJEkaEwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqNL9SJINSUZ2b6kk5ySpJCt70lZ2aeeMql5dPUb62SyUJAcmeVeSL3ef622jrpMmU5Kpbhs6bR5lTuvKTC1axaQFMC6/PZK2ZYAqTZjuB7V3ujvJV5N8IslbkxyRZNkivfemJJsWY9mLbVBwvNR07f5u4CeBfwX+CHjVMOWS/GqSDyW5Jcm3ktyY5L+7bep5Xb6pAdvfXNPKRVzlRZPkoUle1AX7G5N8M8ntST6S5IQkO/z7meSg7vP9ZLcP353k+iT/nuRnk2Qh1uX+JsnjkvxRkouSfKFnW1w+R7mHJHld9z13d5IvJjk7yb6zlNm3y/PFrsymbhkPnqXMqiRv7/axu5Jc29V391nKPC3J+m7//Ga3b750tu/6JD/dHXi7PckdSS5Ncvxsn4EkjYNZv6wljbU/6h6XAXsBjweOA04ALk9ybFV9pq/MLwF77LQabuuVtIDphhHWYSaj/mwWwv7AKuBvq+rEYQp0f3D/FTgcuA14D7AZ2JW2Tf0C8APAOmATW7e7aXsBvwXcDrxuwFvcNp8VGCNHAX8DfAn4IPAFYAXws8BbgSOSHFVVO9Lr/mTg+cB/AB+jfYYPB54LvAM4j7Zdjsp/Ao8DbhphHbbHc4BTgW8DnwXuAh44W4EkD6W1wWOBS4C1tO3+l4GfSvIjVXVdX5nHdGW+F7gI+B/gYNr+cHiSp1fVzX1lDumW/wDgQuB64Me7+h6W5LCquruvzBra9nAXcAFwC20bOQN4Om1b7V+fk4A3ADcD/wDcAxwJnJPkoKp6+WyfhySNVFU5OTlN0ARU23UHzlsBvL3L8wXgexf4vTcBmxZ4mSu7+p6zyJ/bOd37rBx1Gy7iOj6zW8fT5lHmF7synwL2HDB/D+DQIdpvQbeLUU+0oOG5wC596Q/v9q0Cfm4H32O3GdK/B7ime4+DR/1ZzHOdTuvqPTXCOnw/cAiwe/d6U1en5bOUeUuX5zV96S/p0t83oMzF3bzf7Et/bZf+5r70ZT3t+rye9F1owWoBpwzYFm4E7gZW96Q/kBYcF3B0X5mVtGD25t7vO+DBwMauzI+MelsZ9bSzfnucnJzmPznEV1pCquorwNHABmA/4Hd752fAeZZpjk/ysW6Y4V3dMMOLk7ygyzPVlXsU8Ki+IZzn9Cyruvd4eDd08YYk307ywm7+rMNsk/xAknd3w9i+0Q2nfPaAfDOe55YB5xV1dZ8e2vb5nrpvmu2z6dJ3SfLiJJd1w+S+0T3/tUHDPHs+g72TnJXkS93Qv6uT/PKg9Z5NkicneUc3HPDuJP+b5E1JHtH/vsCHupd/2LOOp83xFk/rHs+pqtv7Z1bVnVX1we2o95zb1ZDL2TPJn3fDIO9Kcmu3jJ8YkPc750wmeUKS9yS5LcmdacOXnzboPQapqkuq6l+q6t6+9C8Db+5eTvW894OzdWjok/vqtUuSD3Z1O65nWffpKetJ/xot+AE4cNg6d5/V65Js7j6r/0nysiSP7t8nuvzT++Ojk/xm2rDRbybZ0M2f8RzUbrt8X5KvJ/la2rDkHxm2roupqq6tqkur6pvD5E/yXbTRJ9+gBdi9zgT+F3hOkkf3lHkM8Gxa8PvGvjJ/2C3ruCQP6kn/MVqP9Ieral1Pfe8FXtG9fHFyn6HdRwIPA9ZW1eU9Ze4Cfr97+Wt97/8rwG7AmVW1qafMrcCfTb8PQ5jPfpzk0O4775pum/hmkquS/GGSbXqwe7/HkxyT5IpuX/1iktcm2a3L9+Pdd+rXuv3/vLQe7/7lbeqmPZOcmfb7c1dXn5f0fa5zrfceSV6Z5FNp3/l3JPl4kmN25DOSNByH+EpLTFXdm+RPaH+ej0ny21U12zDEP6UNvf08rff1duARwFNoQ8cuYOvQzpd2ZV7XU/5Tfct7CG3I4h3AO4F7ga8MUfX9gY8DV9J6Mx4BvAB4b5JfqKoLhljGTP6INpTyh4HXs3XY6W2Ds9/HebRhrtfThnYW8DPAm4BnAMcOKLMX8FHasLoLaX8WjwLOTnJvVZ07TKWT/DRtaF+65fwvbVjorwFrkjyjqj7fs44raYH4h2gHKeh5nMn0EMTHDlOneRhmu5pVkr1on+Mq4DLadrc38PPA+5P8WlW9ZUDR1bQ//B+ntdkjgZ8DPpDkCVV17Y6sGPCt7nHLdEJV3dr9ef0wcEGSJ1bV17vZf0jbH8+pqvPmWniSPWg9uND2hzl1AcAlwJOATwLnA3sCvwf86BzFX9/leQ+wnjY0drb3ehrw77Rh4O+k9co9gbatXTJMfcfMU4Hdgff3tBnwne/Ti4ETgUOB6WG+h3aP7x9wEOPrST5KC2CfCnygmzXdpu/rr0BVXZfkM7T98NHA5+YqQ9vW7gSelmS3ngMes5V5b1+eucxnP/4d2rDoj9G2pQfShiCfBkwl+YmqGrRt/SZwBO38+Q20z+23gYckuYg23Po9wFm0A2q/SPseOGLAsnalbZt7deV2pe37r6f1rP/GXCvcfe9cAjwR+ARwNq2X+znAPyZ5fFX9fk+RHf6uk9Rn1F24Tk5O85uYZYhvT57daH+iC9i/J31Df1lagLIZ2GPAcvbue72JWYZyTtcN+HsGDKdjwDBbtg6zKuAv+/Kv7tbjVuB7etJPY4ZhhMwwbGvQe/fNH/TZHNOV+QTwXT3pDwIu7+b9wgyfwVuBZT3pq2gBzTVDtvN3dW3zbeBH++b9Tvce7+9Ln2L+Q3yfSAuk76UF4z8LPGoe5ac/70196UNvV7Mse3rY5VuA9KQfSPsTeHfftjS9/gW8sG9Z/6dLf9Ow6zZDnZbTgsYCnjNg/iu6ef/UvT60a8NrBn0WXZ4Dum36j2l/wm/olvFn86jXH0y/b99ntR/w1Tn2iRvo+Z6YbXuiHSz5ny59TV/+3+r5/LfZN0c1MccQX1rQUsAbZpj/8m7+q3vS/rJLO3mGMmd283+tJ+2fmWVoOO1c8AKO6Em7rEt78gxlrurmP64nbbq9HzpDmTu6+QO3x7688/l9eHTvtteT/sfd+72gL/20Lv32vvrvBlzd7Tc3Az/WM28X4N+6ck+YoZ0/Qs/wedpB0891857Zk75yjv3iFX3pD6QF/ff2vvd8PiMnJ6fhJof4SktQtSPp0z1jDxuiyLcY0GtSVdtzcZR7gJdX1ZY5c97X7cDpfe9/Oa0naC9ar+XO9ivd4ylVdUdPvb5BCxIBXjSg3J3Ay6qnt6CqrqH1Bj6uG1I4lzW0P1YXVNX/65v3GtqfsWcleeQwKzKTqvokrUfiK93jO4BNSW5Ou4Ltc3dg8du9XSXZtavPHcArq6p6yn8W+Gta78igiwh9tKrO6Us7m3aA4OBhKz+DVwE/CKyvqosHzP9L2p/Yo5O8krb93k37c37nDMs8gNbL+vvAr9J6h/4vrfdzWMfT/jj3f1bXM/jiVb3+orb2xM/labSeqA9X1UV9885ka8/fJNmze9xmiHtf+l5LrMyeM8zvN9R+XFXX9W57Pc7oHp8zw/L/uqo+3bOcu2m9jrsA76mqD/XMu5d20SdoI2IGeWX1DJ+vqltoQTK0i17NqBs6/IvA5VX1F73zqg2r/h3aQZpf6Cu6kL+h0v2eQ3ylpWv6fJtBfxh6nU8bYnVNkrfThod+vAacjzikTVV143aU+0T1Da/rbKD9+X4iMNTQ2AX0JNqf/g0D5n2I9ofkiQPmfbbaeYT9ru8eH0wLvOZ6bxgwZLKqtiT5MK0H4Im0i/Zst6p6e5J30Xr7ntEt8xm0YdHPT/L3tB7JubalXju6XX0/7QJNH+3+YPa7hBbQDfr8L+9PqKpvJfkK7bPfLkleApxM60E8blCeqqokv0Qb+j59vt//qaoZh+pW1fva4vMA2nDkY7uyP5bk56rqnjnq9T3AY4Drq+ecwx4fma087Wq9w5reLj/UP6Oqvp3kI11d5pR2DvlUX/Kmqjon7Tz1Fw54j9OGrqkWwtD7cXe+7W/RDiY+Fvhutv4OAewzw3tss78CX+werxgwb/oq8INu/7OFNsS434bucdD3Ra+n0C5mNdP5+w/oHh/Xk7bQv6HS/Z4BqrQEdeejPaR7+dU5sv827byqXwZO6aYtSdbThq9tnOfbf3me+afNdJ7q9PKGPdq/kPYEbhkUIHRB4k20W0z0u22G5U33Kg9zn9rp9f3SDPOn0/caYllzqqpvAe/vpunbz/wcrefxl4B30c4RG9aOblc7sv63zVBmC8N99ttIu23H62lDdQ+bIWgGoKq+2h1AOJo2kmHO8067ct+i9UCenuQe4M9pV5H9qzmKfk/3ONM+NNc54PPZZ6fbZa79dRhTtJ7jXh+iDbFcOWAebHsRo4UwV4/idPptE1Rm727ezf0FmLuHtddQ+3F3cOUS2giFq2g9oF9l6/naf0gbujvIoHpsGWLeAwbMu6kGn+c67O/I9MWXntJNM+kdBbPQv6HS/Z5DfKWl6Rm0A1BfmaFH5Tuq6ttV9bqq+mHabWp+jhaMPA943/SVFOdhPr1svVbMkP7w7rH3j8r0RUkGHWTbazvff5DbaRfq2OaPUJLltD+Bg3pKF+q9Yev693tEX74F1W0Xb2fr8LxhL6rSW35HtquRrn+vJC+l3VPyKtotd2YNwpIcTQtOb6L94f3r7Xjb6YvZTA2Rd3obnGkfmil92nz22enPe679dU5VdVpVpW+a6uZtGDBv6KuwztP0RbNmulDY9JWUe+8rPfIy3XfQ/rSA7bohyzyCdg795lmGnH/HPPbjNbTg9JyqOqiqTqyq3+t6vAddyGyx7N0dXOs36HdkkOn5Zwza/nqm6YtkLcZvqHS/Z4AqLTFptz6ZPnftH+dTtqpurKp3VtXP046GP4Z2vt20b7OdPVBDeFKS7x6QPtU9frIn7dbucb8B+VfPsPzpo+rzqf8nad+Tzxww75ndsj4xj+XNx/T6TvXP6P6YTl+ZdbHef9r0sOvtDg6G2K4GuZZ2Lu8Pd1fV7Df9B3FR1z/J79CC9E/RgtNZh68nOYB2oaOv0oYTfhh4URe0zsf0cMg5z+XuhpNfB+yTwbdwesY833s205/3j/XP6AKDhXyvneU/gG8CT+//Duq+T6dvdfXBnlnTz5+dvttNdct4Om37/Y+eWdPD9Q/vr0DaLWweS7tS93XDlKF9B+0BfKzue8ui2coc0ZdnaHPsxwd0j+8cUHSbbWURLWfrrbN6TXWPnxwwr9d/0g6AznXl64G287tOUh8DVGkJSfK9tEvrT9HOS/yzOfLvluTpA9IfwNYhwr1H2W8GHpZk9wWp8H3tCZzaV4/VtPPxbqcdkZ42fc7cL3fB2nT+/fqX0WN6qNt8Lip0dvf4592tP6bfZw/axXIA3jaP5c3Hu4FbaLcKemrfvJfSek7+vap26PzTtPsPPqv/T3Y37+G0i/ZAC7SGXeZ8t6ttdMOqz6edx/bHvfPS7kH5EtrwwaGGz26PJH9Aa+craMN6Z73gSXdhp7W04X/HV9Vm2sVUbgbe0tW7N//AgylJHsbW7es9Q1b372m/6X+ebL3fY7dPvHTIZQzjY7SDB89MsqZv3kkMef7pOOkugHYerWfxtL7ZJ9GGG19cVdf1lPkcbTj8Sra9dckfdcs6r7ug2rQPAZ+mfXbPm07s9r1Xdy/f3Heu94W0nvije7eX7jSOP+le/k3f+/8d7cJcJ/UesEjyYLbeG/vNzGGe+/Gm7nGqL++j2bpuO8uf9/ZaJnkIW+8Z+3ezFewOQJ0PrE7yB4N6Y5M8Jsn+3fMd/q6TtC3PQZUmVM8FHHahDWt9PK33YldaAHfsEFcQ3B34SJKNtD/h/0u7lP6zaBeBWNd7dUXa/fyeQhu29GHan6D/qqp/WYBVmu5pOoR2tdvp+6DuQrvIzHeG0lbVpd37PxP4zySX0IZWPRe4mME9qx+gXRn1b5O8g9YzeFtVnTlTharqH7s/4T8PXJ3k3bThkM+nBYgXVNX5O7TWM7/3HUl+hXZrig8l+WfaQYcn03p0vky7dcqOOoR2YZMvdxe4mb6a6/7AT9G2kYtof5SHNd/taian0HoyTkryFFqv1fR9UL8bOGkeV5+dlyTH064q/W3g/wEv6Yn7pm2q+14t+C9o7fPaqnovQFXdkOSFwL/Q7o/6tJ5zmt/aXTX0P2lt+21awPOTtM/w3Ww9SDKXv6Btl0cD35/k/bSDPj9P27eez9ah8dutuwjUCbRbfbwjSe99UA+jXcF4UM/dTpNkb+573u7e3ePbkkwHf6+qqv/pyfO7tODqZUmeQGuTx9GGrt7I4Ptn/jotYP/rJIfRgs9DaL37n6HvKszdRaR+mdazdmGSC2ntfhht5MdH2TqkfrrM15L8Km3/25BkLe3A1fNoFxK7kL77bFbV55P8X9rQ8suTXEC7uvqRtAsLvaaqPj5gffrNZz/+F9p28LIkB9F6Kh8J/DTtIMsOXW18Hr5EO9f1qiTraOepHkn7PXlTVQ1zoO0k2nDr04Hjuu/FrwDfR1vvp9BuQfZ5Fu67TlKvGoN73Tg5OQ0/sfU+g9PT3bQj7FcAf0v7c7jLDGU30HOvT9qP9yto57t9AbiLNjTxP4AXA7v2lX8Q7Wj9ZtrQw/vcQ657vWGWup/DzPdBPYf2g34RbQjvnbQ/bNvca7Irt1e3vjd2n8FVwInMcG+7rszLaH8i76bv3p39n01P+i60P6KXd3W6s/usf2PQ5zzbZzBo/Ydo76fQeo+/SvuT+YWuDb5vQN4p5n8f1P26dXkXrWfsa937fAlYT7vlwsDtqa/9ej/LeW1Xc9RvL1oPzGe7druNFhw9e77rzxz38e3Lexrb7mv904ae/M/t0i4DHjBgea/t5r++J+0XaQHGdbSrOt9Du3rpv9IOzmxzT8khPqu/7pZxN+1qwyfTzg0s4HXz2R5n+zxpgfj7aAd6vg78O/AjzHKP4p01cd97K880bVM/Wo/X62lBxvQ+cDaw7xz7z991ee/pyr4OePAsZVbRDjzd1LXTZ2i9rrvPUubptP3xVtpw5CtpF+dZNkuZ59J6bb8OfKPbNo+fx+c439+H/Wi9jzd0dby6K7+8f3/p28cGtcULGXA/49m2S7r9m3Zg5o1dPe6mfee/hL79idl/K3alBaofY+s9l79AO9D5Urp7zM73M3JychpuStV8ro0gSZImSdcDdxbw4qramReskXaaJJsAqmrlaGsiaUd5DqokSUtAku8bkPZI4A9oIx4WYii+JEmLynNQJUlaGt7RXZzlCtpQ6JW0cwD3AF5ZVV8cXdUkSRqOAaokSUvDecBxtPsw7kk7r/VS4MyqGnT7D0mSxo7noEqSJEmSxsJQ56AmOTzJtUk2JjllwPzdklzQzb90+r5bSY5N8qme6d7u8u2SJEmSJN3HnD2o3U2KP0O7p9Nm2mXKj6mqa3ry/DrwQ1X14iRHAz9TVS/oW85BwLuratabeO+99961cuXK7VmXneYb3/gGD3rQg0ZdDQ3J9posttfksc0mi+01WWyvyWJ7TRbba3SuuOKKm6rqYYPmDXMO6sHAxqq6DqC7SfQa4JqePGto97OCdk+3M5Ok7hv9HgOsnevNVq5cyeWXXz5EtUZnw4YNTE1NjboaGpLtNVlsr8ljm00W22uy2F6TxfaaLLbX6CT535nmDTPEdx/g+p7Xm7u0gXmqagvtpsYP7cvzAuCfhng/SZIkSdL90E65im+SQ4A7q+qqGeafCJwIsGLFCjZs2LAzqrXd7rjjjrGvo7ayvSaL7TV5bLPJYntNFttrsthek8X2Gk/DBKg3APv1vN63SxuUZ3OS5bTL29/cM/9oZuk9raqzgLMAVq9eXePe1e5wgMlie00W22vy2GaTxfaaLLbXZLG9JovtNZ6GGeJ7GXBgkv2T7EoLNtf15VkHHN89PxK4ZPr80yS7AD/PEOefSpIkSZLuv+bsQa2qLUlOAi4GlgFnV9XVSU4HLq+qdcDbgPOSbARuoQWx054JXD99kSVJkiRJkgYZ6hzUqloPrO9LO7Xn+V3AUTOU3QA8dfurKEmSJGlUVp7ynlFXYVGcc7i3mBlHwwzxlSRJkiRp0e2Uq/hK0v3dUj36DHDyQVt44RJcv02v+qlRV2FRXHnD7baXJGlsGaBKkjTAUj2ocPJBo66BJI2HpXrADib7oJ0Bqr5j6f4Zs3dnkizlHwtJi8ffMI0Dz2mUdpwBqjShlu6fsVHXQJKk7eNBVmnHGaBuB798JEmSJGnheRVfSZIkSdJYMECVJEmSJI0FA1RJkiRJ0lgwQJUkSZIkjQUDVEmSJEnSWDBAlSRJkiSNBQNUSZIkSdJYMECVJEmSJI2FoQLUJIcnuTbJxiSnDJi/W5ILuvmXJlnZM++Hknw8ydVJrkzywAWsvyRJkiRpiZgzQE2yDHgjcASwCjgmyaq+bCcAt1bVAcAZwKu7ssuBfwBeXFWPB6aAby1Y7SVJkiRJS8YwPagHAxur6rqqugdYC6zpy7MGOLd7fiFwWJIAzwb+u6r+C6Cqbq6qby9M1SVJkiRJS8kwAeo+wPU9rzd3aQPzVNUW4HbgocBjgUpycZJPJHnFjldZkiRJkrQULd8Jy38G8BTgTuADSa6oqg/0ZkpyInAiwIoVK9iwYcMiV2vHrNgdTj5oy6iroSHZXpPF9po8ttlksb0mi+01WWyvybKU22vc46nZDBOg3gDs1/N63y5tUJ7N3XmnewI303pbP1xVNwEkWQ88CbhPgFpVZwFnAaxevbqmpqbmvSI70xvOv4jXXLnYsb0WyskHbbG9JojtNXlss8lie00W22uy2F6TZSm316Zjp0Zdhe02zBDfy4ADk+yfZFfgaGBdX551wPHd8yOBS6qqgIuBg5Ls0QWuPwZcszBVlyRJkiQtJXMeMqiqLUlOogWby4Czq+rqJKcDl1fVOuBtwHlJNgK30IJYqurWJK+lBbkFrK+q9yzSukiSJEmSJthQfdpVtR5Y35d2as/zu4CjZij7D7RbzUiSJEmSNKNhhvhKkiRJkrToDFAlSZIkSWPBAFWSJEmSNBYMUCVJkiRJY8EAVZIkSZI0FgxQJUmSJEljwQBVkiRJkjQWDFAlSZIkSWPBAFWSJEmSNBYMUCVJkiRJY8EAVZIkSZI0FgxQJUmSJEljwQBVkiRJkjQWDFAlSZIkSWNhqAA1yeFJrk2yMckpA+bvluSCbv6lSVZ26SuTfDPJp7rpzQtcf0mSJEnSErF8rgxJlgFvBJ4FbAYuS7Kuqq7pyXYCcGtVHZDkaODVwAu6eZ+rqicsbLUlSZIkSUvNMD2oBwMbq+q6qroHWAus6cuzBji3e34hcFiSLFw1JUmSJElL3TAB6j7A9T2vN3dpA/NU1RbgduCh3bz9k3wyyYeS/OgO1leSJEmStETNOcR3B30JeGRV3ZzkycC7kzy+qr7WmynJicCJACtWrGDDhg2LXK0ds2J3OPmgLaOuhoZke00W22vy2GaTxfaaLLbXZLG9JstSbq9xj6dmM0yAegOwX8/rfbu0QXk2J1kO7AncXFUF3A1QVVck+RzwWODy3sJVdRZwFsDq1atrampq/muyE73h/It4zZWLHdtroZx80Bbba4LYXpPHNpssttdksb0mi+01WZZye206dmrUVdhuwwzxvQw4MMn+SXYFjgbW9eVZBxzfPT8SuKSqKsnDuosskeTRwIHAdQtTdUmSJEnSUjLnIYOq2pLkJOBiYBlwdlVdneR04PKqWge8DTgvyUbgFloQC/BM4PQk3wLuBV5cVbcsxopIkiRJkibbUH3aVbUeWN+XdmrP87uAowaUewfwjh2soyRJkiTpfmCYIb6SJEmSJC06A1RJkiRJ0lgwQJUkSZIkjQUDVEmSJEnSWDBAlSRJkiSNBQNUSZIkSdJYMECVJEmSJI0FA1RJkiRJ0lgwQJUkSZIkjQUDVEmSJEnSWDBAlSRJkiSNBQNUSZIkSdJYMECVJEmSJI0FA1RJkiRJ0lgYKkBNcniSa5NsTHLKgPm7Jbmgm39pkpV98x+Z5I4kL1+gekuSJEmSlpg5A9Qky4A3AkcAq4Bjkqzqy3YCcGtVHQCcAby6b/5rgffueHUlSZIkSUvVMD2oBwMbq+q6qroHWAus6cuzBji3e34hcFiSACR5PvB54OoFqbEkSZIkaUlKVc2eITkSOLyqXtS9Pg44pKpO6slzVZdnc/f6c8AhwF3AvwHPAl4O3FFVfzXgPU4ETgRYsWLFk9euXbsAq7Z4brzldr7yzVHXQsNasTu21wSxvSaPbTZZbK/JYntNFttrsizl9jponz1HXYVZHXrooVdU1epB85Yv8nufBpxRVXd0HaoDVdVZwFkAq1evrqmpqUWu1o55w/kX8ZorF/uj00I5+aAtttcEsb0mj202WWyvyWJ7TRbba7Is5fbadOzUqKuw3YZpkRuA/Xpe79ulDcqzOclyYE/gZlov6pFJ/gLYC7g3yV1VdeaOVlySJEmStLQME6BeBhyYZH9aIHo08At9edYBxwMfB44ELqk2dvhHpzMkOY02xNfgVJIkSZK0jTkD1KrakuQk4GJgGXB2VV2d5HTg8qpaB7wNOC/JRuAWWhArSZIkSdLQhhp0XVXrgfV9aaf2PL8LOGqOZZy2HfWTJEmSJN1PDHObGUmSJEmSFp0BqiRJkiRpLBigSpIkSZLGggGqJEmSJGksGKBKkiRJksaCAaokSZIkaSwYoEqSJEmSxoIBqiRJkiRpLBigSpIkSZLGggGqJEmSJGksGKBKkiRJksaCAaokSZIkaSwYoEqSJEmSxoIBqiRJkiRpLAwVoCY5PMm1STYmOWXA/N2SXNDNvzTJyi794CSf6qb/SvIzC1x/SZIkSdISMWeAmmQZ8EbgCGAVcEySVX3ZTgBuraoDgDOAV3fpVwGrq+oJwOHAW5IsX6C6S5IkSZKWkGF6UA8GNlbVdVV1D7AWWNOXZw1wbvf8QuCwJKmqO6tqS5f+QKAWotKSJEmSpKUnVbPHjEmOBA6vqhd1r48DDqmqk3ryXNXl2dy9/lyX56YkhwBnA48Cjquqdw14jxOBEwFWrFjx5LVr1y7Iyi2WG2+5na98c9S10LBW7I7tNUFsr8ljm00W22uy2F6TxfaaLEu5vQ7aZ89RV2FWhx566BVVtXrQvEUfbltVlwKPT/I44Nwk762qu/rynAWcBbB69eqamppa7GrtkDecfxGvudKRypPi5IO22F4TxPaaPLbZZLG9JovtNVlsr8mylNtr07FTo67CdhtmiO8NwH49r/ft0gbm6c4x3RO4uTdDVX0auAP4we2trCRJkiRp6RomQL0MODDJ/kl2BY4G1vXlWQcc3z0/ErikqqorsxwgyaOAHwA2LUjNJUmSJElLypx92lW1JclJwMXAMuDsqro6yenA5VW1DngbcF6SjcAttCAW4BnAKUm+BdwL/HpV3bQYKyJJkiRJmmxDDbquqvXA+r60U3ue3wUcNaDcecB5O1hHSZIkSdL9wDBDfCVJkiRJWnQGqJIkSZKksWCAKkmSJEkaCwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqJIkSZKksWCAKkmSJEkaCwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqJIkSZKksTBUgJrk8CTXJtmY5JQB83dLckE3/9IkK7v0ZyW5IsmV3eOPL3D9JUmSJElLxJwBapJlwBuBI4BVwDFJVvVlOwG4taoOAM4AXt2l3wQ8t6oOAo4HzluoikuSJEmSlpZhelAPBjZW1XVVdQ+wFljTl2cNcG73/ELgsCSpqk9W1Re79KuB3ZPsthAVlyRJkiQtLamq2TMkRwKHV9WLutfHAYdU1Uk9ea7q8mzuXn+uy3NT33JeXFU/MeA9TgROBFixYsWT165du8MrtphuvOV2vvLNUddCw1qxO7bXBLG9Jo9tNllsr8lie00W22uyLOX2OmifPUddhVkdeuihV1TV6kHzlu+MCiR5PG3Y77MHza+qs4CzAFavXl1TU1M7o1rb7Q3nX8RrrtwpH50WwMkHbbG9JojtNXlss8lie00W22uy2F6TZSm316Zjp0Zdhe02zBDfG4D9el7v26UNzJNkObAncHP3el/gXcAvVdXndrTCkiRJkqSlaZgA9TLgwCT7J9kVOBpY15dnHe0iSABHApdUVSXZC3gPcEpVfXSB6ixJkiRJWoLmDFCragtwEnAx8Gng7VV1dZLTkzyvy/Y24KFJNgIvA6ZvRXMScABwapJPddP3LvhaSJIkSZIm3lCDrqtqPbC+L+3Unud3AUcNKPcnwJ/sYB0lSZIkSfcDwwzxlSRJkiRp0RmgSpIkSZLGggGqJEmSJGksGKBKkiRJksaCAaokSZIkaSwYoEqSJEmSxoIBqiRJkiRpLBigSpIkSZLGggGqJEmSJGksGKBKkiRJksaCAaokSZIkaSwYoEqSJEmSxoIBqiRJkiRpLAwVoCY5PMm1STYmOWXA/N2SXNDNvzTJyi79oUk+mOSOJGcucN0lSZIkSUvInAFqkmXAG4EjgFXAMUlW9WU7Abi1qg4AzgBe3aXfBfwB8PIFq7EkSZIkaUkapgf1YGBjVV1XVfcAa4E1fXnWAOd2zy8EDkuSqvpGVX2EFqhKkiRJkjSjYQLUfYDre15v7tIG5qmqLcDtwEMXooKSJEmSpPuH5aOuAECSE4ETAVasWMGGDRtGW6E5rNgdTj5oy6iroSHZXpPF9po8ttlksb0mi+01WWyvybKU22vc46nZDBOg3gDs1/N63y5tUJ7NSZYDewI3D1uJqjoLOAtg9erVNTU1NWzRkXjD+RfxmivHIrbXEE4+aIvtNUFsr8ljm00W22uy2F6TxfaaLEu5vTYdOzXqKmy3YYb4XgYcmGT/JLsCRwPr+vKsA47vnh8JXFJVtXDVlCRJkiQtdXMeMqiqLUlOAi4GlgFnV9XVSU4HLq+qdcDbgPOSbARuoQWxACTZBHwPsGuS5wPPrqprFnxNJEmSJEkTbag+7apaD6zvSzu15/ldwFEzlF25A/WTJEmSJN1PDDPEV5IkSZKkRWeAKkmSJEkaCwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqJIkSZKksWCAKkmSJEkaCwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqJIkSZKksWCAKkmSJEkaC0MFqEkOT3Jtko1JThkwf7ckF3TzL02ysmfeK7v0a5M8ZwHrLkmSJElaQuYMUJMsA94IHAGsAo5Jsqov2wnArVV1AHAG8Oqu7CrgaODxwOHAm7rlSZIkSZJ0H8P0oB4MbKyq66rqHmAtsKYvzxrg3O75hcBhSdKlr62qu6vq88DGbnmSJEmSJN3HMAHqPsD1Pa83d2kD81TVFuB24KFDlpUkSZIkieWjrgBAkhOBE7uXdyS5dpT1GcLewE2jroSG8xLba6LYXpPHNpssttdksb0mi+01WZZye+XVo67BnB4104xhAtQbgP16Xu/bpQ3KsznJcmBP4OYhy1JVZwFnDVGXsZDk8qpaPep6aDi212SxvSaPbTZZbK/JYntNFttrsthe42mYIb6XAQcm2T/JrrSLHq3ry7MOOL57fiRwSVVVl350d5Xf/YEDgf9cmKpLkiRJkpaSOXtQq2pLkpOAi4FlwNlVdXWS04HLq2od8DbgvCQbgVtoQSxdvrcD1wBbgN+oqm8v0rpIkiRJkibYUOegVtV6YH1f2qk9z+8Cjpqh7J8Cf7oDdRxHEzMcWYDtNWlsr8ljm00W22uy2F6TxfaaLLbXGEobiStJkiRJ0mgNcw6qJEmSJEmLzgB1HpIcnuTaJBuTnDLq+mh2SfZL8sEk1yS5OslvjbpOmluSZUk+meRfR10XzS7JXkkuTPI/ST6d5EdGXSfNLMlvd9+FVyX5pyQPHHWddF9Jzk5yY5KretIekuTfkny2e3zwKOuorWZor7/svhP/O8m7kuw1wiqqx6D26pl3cpJKsvco6qb7MkAdUpJlwBuBI4BVwDFJVo22VprDFuDkqloFPBX4DdtsIvwW8OlRV0JDeT3wvqr6AeCHsd3GVpJ9gJcAq6vqB2kXPTx6tLXSAOcAh/elnQJ8oKoOBD7QvdZ4OIdt2+vfgB+sqh8CPgO8cmdXSjM6h23biyT7Ac8GvrCzK6TBDFCHdzCwsaquq6p7gLXAmhHXSbOoqi9V1Se651+n/XneZ7S10myS7Av8FPDWUddFs0uyJ/BM2lXcqap7quq2kVZKc1kO7N7dr3wP4Isjro/6VNWHaXdD6LUGOLd7fi7w/J1ZJ81sUHtV1furakv38j+AfXd6xTTQDPsXwBnAKwAvzDMmDFCHtw9wfc/rzRjsTIwkK4EnApeOuCqa3etoPxL3jrgemtv+wFeBv+uGZL81yYNGXSkNVlU3AH9F6yH4EnB7Vb1/tLXSkFZU1Ze6518GVoyyMpqXXwHeO+pKaGZJ1gA3VNV/jbou2soAVUteku8C3gG8tKq+Nur6aLAkPw3cWFVXjLouGspy4EnA31TVE4Fv4NDDsdWdt7iGdmDh+4AHJfnF0dZK81Xt1gv28kyAJL9HO9Xo/FHXRYMl2QP4XeDUufJq5zJAHd4NwH49r/ft0jTGkjyAFpyeX1XvHHV9NKunA89Lsok2hP7Hk/zDaKukWWwGNlfV9KiEC2kBq8bTTwCfr6qvVtW3gHcCTxtxnTScryR5BED3eOOI66M5JHkh8NPAseX9HMfZY2gH7f6r+++xL/CJJA8faa1kgDoPlwEHJtk/ya60i0usG3GdNIskoZ0f9+mqeu2o66PZVdUrq2rfqlpJ278uqSp7eMZUVX0ZuD7J93dJhwHXjLBKmt0XgKcm2aP7bjwML2o1KdYBx3fPjwcuGmFdNIckh9NOVXleVd056vpoZlV1ZVV9b1Wt7P57bAae1P2+aYQMUIfUnfB+EnAx7Uf97VV19WhrpTk8HTiO1hP3qW76yVFXSlpCfhM4P8l/A08A/my01dFMup7uC4FPAFfSfv/PGmmltI0k/wR8HPj+JJuTnAC8CnhWks/SesJfNco6aqsZ2utM4LuBf+v+d7x5pJXUd8zQXhpDceSBJEmSJGkc2IMqSZIkSRoLBqiSJEmSpLFggCpJkiRJGgsGqJIkSZKksWCAKkmSJEkaCwaokiRJkqSxYIAqSZIkSRoLBqiSJEmSpLHw/wH9uANoHyPzxQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 1152x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tree_utils.plot_sampled_STs(STs, UST_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA6gAAADXCAYAAAAX3XyhAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAuGUlEQVR4nO3de7xldV3/8dcbRhC0BhUbDbBBwRKbUhnB1OwQqVDp+CsskAgL42e/yEzMsAsR3dTyllhGShhRgz+8MOUkljj68xIBanExcsBJBhXk4ijIxZHP74/vOs5ms885+8ycYV94PR+P/dh7f9d37f3Z67vW3vuzvt+1VqoKSZIkSZJGbZdRByBJkiRJEpigSpIkSZLGhAmqJEmSJGksmKBKkiRJksaCCaokSZIkaSyYoEqSJEmSxoIJqvQAkmRDkpFdWyrJ2UkqycqespVd2dmjiquLY6TLZqkkOTDJe5N8uVuuXx11TJpMSWa6dei0RcxzWjfPzE4LTFoC4/LbI+m+TFClCdP9oPbe7krylSSfSvL2JEcm2XUnvfemJJt2xmvvbIOS42nTtfv7gB8H/gn4feA1w8yX5JeSfCTJLUm+meTGJP/ZrVPP7+rNDFj/Frqt3IkfeadJ8ogkL+mS/Y1J7kiyJcnHkpyQZId/P5Os6pbvp7tt+K4k1yX51yQ/lSRL8VkeaJI8IcnvJ7kgyRd61sVlC8z38CRv6r7n7kryxSRnJdl3nnn27ep8sZtnU/caD5tnnoOSvKvbxu5McnUX7x7zzPP0JOu77fOObtt8+Xzf9Ul+stvxtiXJbUkuTnL8fMtAksbBvF/Wksba73f3uwJ7AU8EjgNOAC5NcmxV/XffPD8P7Hm/RXhfr6YlTNePMIa5jHrZLIX9gYOAv66qE4eZofuD+0/AEcBXgfcDm4HdaOvUi4DvA9YBm9i23s3aC/g1YAvwpgFv8dXFfIAx8kLgL4EvAR8GvgCsAH4KeDtwZJIXVtWO9LofDLwA+DfgE7Rl+CjgecC7gXNo6+Wo/DvwBOCmEcawPZ4LnAp8C/gccCfw4PlmSPIIWhs8HrgIWEtb738B+IkkP1RV1/bN87hunu8CLgD+CziEtj0ckeQZVXVz3zyHdq//IOB84DrgR7t4D09yeFXd1TfPGtr6cCdwHnALbR15I/AM2rra/3lOAt4C3Az8HXA3cBRwdpJVVfXK+ZaHJI1UVXnz5m2CbkC1TXfgtBXAu7o6XwC+a4nfexOwaYlfc2UX79k7ebmd3b3PylG34U78jM/qPuNpi5jn57p5PgMsHzB9T+CwIdpvSdeLUd9oScPzgF36yh/VbVsF/PQOvsfuc5R/J3BV9x6HjHpZLPIzndbFPTPCGL4XOBTYo3u+qYtp2Tzz/FVX5/V95S/ryj8wYJ4Lu2m/2lf+hq78bX3lu/a06/N7ynehJasFnDJgXbgRuAtY3VP+YFpyXMDRffOspCWzN/d+3wEPAzZ28/zQqNeVUd/ur98eb968Lf7mEF9pilTVDcDRwAZgP+C3eqdnwHGWaY5P8olumOGd3TDDC5P8bFdnppvve4Dv6RvCeXbPa1X3Ho/qhi5en+RbSV7cTZ93mG2S70vyvm4Y2+3dcMrnDKg353FuGXBcURf77NC2z/fEvmm+ZdOV75LkpUku6YbJ3d49/uVBwzx7lsHeSc5M8qVu6N+VSX5h0OeeT5KDk7y7Gw54V5L/SfIXSR7d/77AR7qnv9fzGU9b4C2e3t2fXVVb+idW1Teq6sPbEfeC69WQr7M8yZ90wyDvTHJr9xo/NqDut4+ZTPKkJO9P8tUk30gbvvz0Qe8xSFVdVFX/WFX39JV/GXhb93Sm570flm1DQw/ui2uXJB/uYjuu57Xu1VPWU/41WvIDcOCwMXfL6k1JNnfL6r+SvCLJY/u3ia7+7Pb42CS/mjZs9I4kG7rpcx6D2q2XH0jy9SRfSxuW/EPDxrozVdXVVXVxVd0xTP0kD6WNPrmdlmD3OgP4H+C5SR7bM8/jgOfQkt+39s3ze91rHZfkIT3lP0Lrkf5oVa3rifce4FXd05cm9xrafRTwSGBtVV3aM8+dwO90T3+57/1/EdgdOKOqNvXMcyvwx7PvwxAWsx0nOaz7zruqWyfuSHJFkt9Lcp8e7N7v8STHJLms21a/mOQNSXbv6v1o9536tW77Pyetx7v/9TZ1t+VJzkj7/bmzi+dlfct1oc+9Z5JXJ/lM2nf+bUk+meSYHVlGkobjEF9pylTVPUn+kPbn+Zgkv15V8w1D/CPa0NvP03pftwCPBp5KGzp2HtuGdr68m+dNPfN/pu/1Hk4bsngb8B7gHuCGIULfH/gkcDmtN+PRwM8C/5zkRVV13hCvMZffpw2l/EHgzWwbdvrVwdXv5RzaMNfraEM7C/hfwF8AzwSOHTDPXsDHacPqzqf9WXwhcFaSe6rqncMEneQnaUP70r3O/9CGhf4ysCbJM6vq8z2fcSUtEf8IbScFPfdzmR2C+PhhYlqEYdareSXZi7YcDwIuoa13ewM/A3wwyS9X1V8NmHU17Q//J2lt9hjgp4EPJXlSVV29Ix8M+GZ3v3W2oKpu7f68fhQ4L8mTq+rr3eTfo22PZ1fVOQu9eJI9aT240LaHBXUJwEXAU4BPA+cCy4HfBn54gdnf3NV5P7CeNjR2vvd6OvCvtGHg76H1yj2Jtq5dNEy8Y+ZpwB7AB3vaDPj29+mFwInAYcDsMN/DuvsPDtiJ8fUkH6clsE8DPtRNmm3TD/QHUFXXJvlv2nb4WOCaheahrWvfAJ6eZPeeHR7zzfPPfXUWspjt+Ddpw6I/QVuXHkwbgnwaMJPkx6pq0Lr1q8CRtOPnN9CW268DD09yAW249fuBM2k71H6O9j1w5IDX2o22bu7Vzbcbbdt/M61n/VcW+sDd985FwJOBTwFn0Xq5nwv8fZInVtXv9Myyw991kvqMugvXmzdvi7sxzxDfnjq70/5EF7B/T/mG/nlpCcpmYM8Br7N33/NNzDOUczY24G8ZMJyOAcNs2TbMqoA/7au/uvsctwLf2VN+GnMMI2SOYVuD3rtv+qBlc0w3z6eAh/aUPwS4tJv2ojmWwduBXXvKD6IlNFcN2c4P7drmW8AP9037ze49PthXPsPih/g+mZZI30NLxn8K+J5FzD+7vDf1lQ+9Xs3z2rPDLv8KSE/5gbQ/gXf1rUuzn7+AF/e91v/uyv9i2M82R0zLaEljAc8dMP1V3bR/6J4f1rXhVYOWRVfngG6d/gPan/Dru9f440XE9buz79u3rPYDvrLANnE9Pd8T861PtJ0l/9WVr+mr/2s9y/8+2+aobiwwxJeWtBTwljmmv7Kb/tqesj/tyk6eY54zuum/3FP2f5lnaDjtWPACjuwpu6QrO3iOea7opj+hp2y2vR8xxzy3ddMHro99dRfz+/DY3nWvp/wPuvf72b7y07ryLX3x7w5c2W03NwM/0jNtF+BfuvmeNEc7f4ye4fO0nabXdNOe1VO+coHt4lV95Q+mJf339L73YpaRN2/ehrs5xFeaQtX2pM/2jD1yiFm+yYBek6ranpOj3A28sqq2Lljz3rYAp/e9/6W0nqC9aL2W97df7O5PqarbeuK6nZYkArxkwHzfAF5RPb0FVXUVrTfwCd2QwoWsof2xOq+q/l/ftNfT/ow9O8ljhvkgc6mqT9N6JG7o7t8NbEpyc9oZbJ+3Ay+/3etVkt26eG4DXl1V1TP/54A/p/WODDqJ0Mer6uy+srNoOwgOGTb4ObwG+H5gfVVdOGD6n9L+xB6d5NW09fcu2p/zb8zxmgfQell/B/glWu/Qb9B6P4d1PO2Pc/+yuo7BJ6/q9bra1hO/kKfTeqI+WlUX9E07g209f5NkeXd/nyHufeV7Tdk8y+eY3m+o7biqru1d93q8sbt/7hyv/+dV9dme17mL1uu4C/D+qvpIz7R7aCd9gjYiZpBXV8/w+aq6hZYkQzvp1Zy6ocM/B1xaVa/rnVZtWPVv0nbSvKhv1qX8DZUe8BziK02v2eNtBv1h6HUubYjVVUneRRse+skacDzikDZV1Y3bMd+nqm94XWcD7c/3k4GhhsYuoafQ/vRvGDDtI7Q/JE8eMO1z1Y4j7Hddd/8wWuK10HvDgCGTVbU1yUdpPQBPpp20Z7tV1buSvJfW2/fM7jWfSRsW/YIkf0vrkVxoXeq1o+vV99JO0PTx7g9mv4toCd2g5X9pf0FVfTPJDbRlv12SvAw4mdaDeNygOlVVSX6eNvR99ni//11Vcw7VraoPtJfPg2jDkY/t5v2RJD9dVXcvENd3Ao8DrqueYw57fGy++Wln6x3W7Hr5kf4JVfWtJB/rYllQ2jHkM33Fm6rq7LTj1F884D1OGzpSLYWht+PueNtfo+1MfDzwHWz7HQLYZ473uM/2Cnyxu79swLTZs8APuvzPVtoQ434buvtB3xe9nko7mdVcx+8/qLt/Qk/ZUv+GSg94JqjSFOqOR3t49/QrC1T/ddpxVb8AnNLdtiZZTxu+tnGRb//lRdafNddxqrOvN+ze/qW0HLhlUILQJYk30S4x0e+rc7zebK/yMNepnf28X5pj+mz5XkO81oKq6pvAB7vb7OVnfprW8/jzwHtpx4gNa0fXqx35/F+dY56tDLfs7yPtsh1vpg3VPXyOpBmAqvpKtwPhaNpIhgWPO+3m+yatB/L0JHcDf0I7i+yfLTDrd3b3c21DCx0DvphtdrZdFtpehzFD6znu9RHaEMuVA6bBfU9itBQW6lGcLf/qBM2zdzft5v4ZWLiHtddQ23G3c+Ui2giFK2g9oF9h2/Hav0cbujvIoDi2DjHtQQOm3VSDj3Md9ndk9uRLT+1uc+kdBbPUv6HSA55DfKXp9EzaDqgb5uhR+baq+lZVvamqfpB2mZqfpiUjzwc+MHsmxUVYTC9brxVzlD+qu+/9ozJ7UpJBO9n22s73H2QL7UQd9/kjlGQZ7U/goJ7SpXpv2Pb5+z26r96S6taLd7FteN6wJ1XpnX9H1quRfv5eSV5Ou6bkFbRL7sybhCU5mpac3kT7w/vn2/G2syezmRmi7uw6ONc2NFf5rMVss7PLe6HtdUFVdVpVpe82003bMGDa0GdhXaTZk2bNdaKw2TMp915XeuTzdN9B+9MStmuHnOfRtGPoN88z5PzbFrEdr6Elp2dX1aqqOrGqfrvr8R50IrOdZe9u51q/Qb8jg8xOf+Og9a/nNnuSrJ3xGyo94JmgSlMm7dIns8eu/f1i5q2qG6vqPVX1M7S94Y+jHW8361tsZw/UEJ6S5DsGlM9095/uKbu1u99vQP3Vc7z+7F71xcT/adr35LMGTHtW91qfWsTrLcbs553pn9D9MZ09M+vOev9Zs8Outzs5GGK9GuRq2rG8P9idVbPf7B/Enfr5k/wmLUn/DC05nXf4epIDaCc6+gptOOFHgZd0SetizA6HXPBY7m44+bXAPhl8CadnLvK95zO7vH+kf0KXGCzle91f/g24A3hG/3dQ9306e6mrD/dMmn38nPRdbqp7jWfQ1t9/65k0O1z/iP4A0i5h83jambqvHWYe2nfQnsAn6t6XLJpvniP76gxtge34gO7+PQNmvc+6shMtY9uls3rNdPefHjCt17/TdoAudObrgbbzu05SHxNUaYok+S7aqfVnaMcl/vEC9XdP8owB5Q9i2xDh3r3sNwOPTLLHkgR8b8uBU/viWE07Hm8LbY/0rNlj5n6hS9Zm6+/X/xo9Zoe6LeakQmd193/SXfpj9n32pJ0sB+Adi3i9xXgfcAvtUkFP65v2clrPyb9W1Q4df5p2/cFn9//J7qY9inbSHmiJ1rCvudj16j66YdXn0o5j+4PeaWnXoHwZbfjgUMNnt0eS36W182W0Yb3znvCkO7HTWtrwv+OrajPtZCo3A3/Vxd1bf+DOlCSPZNv69f4hw/1b2m/6nyTbrvfYbRMvH/I1hvEJ2s6DZyVZ0zftJIY8/nScdCdAO4fWs3ha3+STaMONL6yqa3vmuYY2HH4l9710ye93r3VOd0K1WR8BPktbds+fLey2vdd2T9/Wd6z3+bSe+KN715fuMI4/7J7+Zd/7/w3txFwn9e6wSPIwtl0b+20sYJHb8abufqav7mPZ9tnuL3/S22uZ5OFsu2bs38w3Y7cD6lxgdZLfHdQbm+RxSfbvHu/wd52k+/IYVGlC9ZzAYRfasNYn0novdqMlcMcOcQbBPYCPJdlI+xP+P7RT6T+bdhKIdb1nV6Rdz++ptGFLH6X9CfqPqvrHJfhIsz1Nh9LOdjt7HdRdaCeZ+fZQ2qq6uHv/ZwH/nuQi2tCq5wEXMrhn9UO0M6P+dZJ303oGv1pVZ8wVUFX9ffcn/GeAK5O8jzYc8gW0BPG8qjp3hz713O99W5JfpF2a4iNJ/i9tp8PBtB6dL9MunbKjDqWd2OTL3QluZs/muj/wE7R15ALaH+VhLXa9mssptJ6Mk5I8ldZrNXsd1O8ATlrE2WcXJcnxtLNKfwv4f8DLevK+WZvq3mcLfh2tfd5QVf8MUFXXJ3kx8I+066M+veeY5rd3Zw39d1rbfouW8Pw4bRm+j207SRbyOtp6eTTwvUk+SNvp8zO0besFbBsav926k0CdQLvUx7uT9F4H9XDaGYwH9dzdb5Lszb2P2927u39Hktnk7zVV9V89dX6Llly9IsmTaG3yBNrQ1RsZfP3M/0NL2P88yeG05PNQWu/+f9N3FubuJFK/QOtZOz/J+bR2P5w28uPjbBtSPzvP15L8Em3725BkLW3H1fNpJxI7n77rbFbV55P8Bm1o+aVJzqOdXf0o2omFXl9VnxzwefotZjv+R9p68Iokq2g9lY8BfpK2k2WHzja+CF+iHet6RZJ1tONUj6L9nvxFVQ2zo+0k2nDr04Hjuu/FG4Dvpn3up9IuQfZ5lu67TlKvGoNr3Xjz5m34G9uuMzh7u4u2h/0y4K9pfw53mWPeDfRc65P24/0q2vFuXwDupA1N/DfgpcBuffM/hLa3fjNt6OG9riHXPd8wT+xnM/d1UM+m/aBfQBvC+w3aH7b7XGuym2+v7vPe2C2DK4ATmePadt08r6D9ibyLvmt39i+bnvJdaH9EL+1i+ka3rH9l0HKebxkM+vxDtPdTab3HX6H9yfxC1wbfPaDuDIu/Dup+3Wd5L61n7Gvd+3wJWE+75MLA9amv/XqX5aLWqwXi24vWA/O5rt2+SkuOnrPYz88C1/Htq3sa993W+m8beuo/ryu7BHjQgNd7Qzf9zT1lP0dLMK6lndX5btrZS/+JtnPmPteUHGJZ/Xn3GnfRzjZ8Mu3YwALetJj1cb7lSUvEP0Db0fN14F+BH2KeaxTfXzfufW3luW73iY/W4/VmWpIxuw2cBey7wPbzN13du7t53wQ8bJ55DqLteLqpa6f/pvW67jHPPM+gbY+30oYjX047Oc+u88zzPFqv7deB27t18/hFLMfF/j7sR+t9vL6L8cpu/mX920vfNjaoLV7MgOsZz7de0m3ftB0zb+3iuIv2nf8y+rYn5v+t2I2WqH6Cbddc/gJtR+fL6a4xu9hl5M2bt+FuqVrMuREkSdIk6XrgzgReWlX35wlrpPtNkk0AVbVytJFI2lEegypJ0hRI8t0Dyh4D/C5txMNSDMWXJGmn8hhUSZKmw7u7k7NcRhsKvZJ2DOCewKur6oujC02SpOGYoEqSNB3OAY6jXYdxOe241ouBM6pq0OU/JEkaOx6DKkmSJEkaCx6DKkmSJEkaC2M3xHfvvfeulStXjjqMed1+++085CEPGXUYGpLtNVlsr8ljm00W22uy2F6TxfaaLLbX6Fx22WU3VdUjB00buwR15cqVXHrppaMOY14bNmxgZmZm1GFoSLbXZLG9Jo9tNllsr8lie00W22uy2F6jk+R/5prmEF9JkiRJ0lgwQZUkSZIkjQUTVEmSJEnSWDBBlSRJkiSNBRNUSZIkSdJYGLuz+EqSJKm5/PotvPiU9486jCW36TU/MeoQJI0pe1AlSZIkSWPBHlR928op3EMLcPKqre59liRJkibAUAlqkiOANwO7Am+vqtf0Td8d+FvgYOBm4GeralOSY4Hf6Kn6A8BTquozSxC7JEmSpJ1sWjsxzj7iIaMOQQMsmKAm2RV4K/BsYDNwSZJ1VXVVT7UTgFur6oAkRwOvpSWp5wLndq+zCnifyakkSaMzrcc0TquTV406gp3DhEfSXIbpQT0E2FhV1wIkWQusAXoT1DXAad3j84EzkqSqqqfOMcDaHY5YkiRJGkPuAJos09xek3woWO6dQw6okBwFHFFVL+meHwccWlUn9dS5oquzuXt+TVfnpp461wBrquqKAe9xInAiwIoVKw5eu3a889jbbruNhz70oaMOY8ldfv2WUYewU6zYA264Y9RRLL1V+ywfdQg7xbRuX9PMNpssN96yZSq/E6fVtP6GTSvba7JMc3uN+//Eww477LKqWj1o2v1ykqQkhwLfGJScAlTVmcCZAKtXr66ZmZn7I6zttmHDBsY9xu0xrXuQTl61lddfPn3nA9t07MyoQ9gppnX7mma22WR5y7kXTOV34rSa1t+waWV7TZZpbq9J/p84zGVmrgf263m+b1c2sE6SZcBy2smSZh0N/MP2hylJkiRJmnbDJKiXAAcm2T/JbrRkc11fnXXA8d3jo4CLZo8/TbIL8DN4/KkkSZIkaR4L9mlX1dYkJwEX0i4zc1ZVXZnkdODSqloHvAM4J8lG4BZaEjvrWcB1sydZkiRJkiRpkKEGXVfVemB9X9mpPY/vBF44x7wbgKdtf4iSJEmSpAeCYYb4SpIkSZK005mgSpIkSZLGggmqJEmSJGksmKBKkiRJksaCCaokSZIkaSyYoEqSJEmSxoIJqiRJkiRpLJigSpIkSZLGggmqJEmSJGksmKBKkiRJksaCCaokSZIkaSyYoEqSJEmSxsJQCWqSI5JcnWRjklMGTN89yXnd9IuTrOyZ9gNJPpnkyiSXJ3nwEsYvSZIkSZoSCyaoSXYF3gocCRwEHJPkoL5qJwC3VtUBwBuB13bzLgP+DnhpVT0RmAG+uWTRS5IkSZKmxrIh6hwCbKyqawGSrAXWAFf11FkDnNY9Ph84I0mA5wD/WVX/AVBVNy9R3JKm1OXXb+HFp7x/1GEsuU2v+YlRhyBJkjT2hklQ9wGu63m+GTh0rjpVtTXJFuARwOOBSnIh8EhgbVW9boejlsTKKUziAE5eNeoItFjuVJAkSUslVTV/heQo4Iiqekn3/Djg0Ko6qafOFV2dzd3za2hJ7IuBXwGeCnwD+BDwO1X1ob73OBE4EWDFihUHr127dkk+3M5y22238dCHPnTUYSy5y6/fMuoQdooVe8ANd4w6Cg1rWttr1T7LRx3CTnPjLVtsswkyre01rab1O3Fa2V6TZZrba9x/ww477LDLqmr1oGnD9KBeD+zX83zfrmxQnc3dcafLgZtpva0fraqbAJKsB55CS1S/rarOBM4EWL16dc3MzAwR1ui85dwLeP3Hbh91GDvBMKvD5Dl51VZef/l0frZpNK3ttenYmVGHsNO85dwLbLMJMq3tNa2m9TtxWtlek2Wa22uSf8OGaZFLgAOT7E9LRI8GXtRXZx1wPPBJ4CjgoqqaHdr7qiR7AncDP0I7iZIkPaBM65BscFi2JElaOgsmqN0xpScBFwK7AmdV1ZVJTgcurap1wDuAc5JsBG6hJbFU1a1J3kBLcgtYX1XT+y9NkiRJkrTdhurTrqr1wPq+slN7Ht8JvHCOef+OdqkZSZImxrT2etvjLUkaZwteB1WSJEmSpPuDCaokSZIkaSyYoEqSJEmSxoIJqiRJkiRpLJigSpIkSZLGggmqJEmSJGksmKBKkiRJksaCCaokSZIkaSyYoEqSJEmSxoIJqiRJkiRpLJigSpIkSZLGggmqJEmSJGksDJWgJjkiydVJNiY5ZcD03ZOc102/OMnKrnxlkjuSfKa7vW2J45ckSZIkTYllC1VIsivwVuDZwGbgkiTrquqqnmonALdW1QFJjgZeC/xsN+2aqnrS0oYtSZIkSZo2w/SgHgJsrKprq+puYC2wpq/OGuCd3ePzgcOTZOnClCRJkiRNu2ES1H2A63qeb+7KBtapqq3AFuAR3bT9k3w6yUeS/PAOxitJkiRJmlILDvHdQV8CHlNVNyc5GHhfkidW1dd6KyU5ETgRYMWKFWzYsGEnh7VjVuwBJ6/aOuowNCTba7LYXpPHNpssttdksb0mi+01Waa5vcY9n5rPMAnq9cB+Pc/37coG1dmcZBmwHLi5qgq4C6CqLktyDfB44NLemavqTOBMgNWrV9fMzMziP8n96C3nXsDrL9/Zub2WysmrttpeE8T2mjy22WSxvSaL7TVZbK/JMs3ttenYmVGHsN2GGeJ7CXBgkv2T7AYcDazrq7MOOL57fBRwUVVVkkd2J1kiyWOBA4FrlyZ0SZIkSdI0WXCXQVVtTXIScCGwK3BWVV2Z5HTg0qpaB7wDOCfJRuAWWhIL8Czg9CTfBO4BXlpVt+yMDyJJkiRJmmxD9WlX1XpgfV/ZqT2P7wReOGC+dwPv3sEYJUmSJEkPAMMM8ZUkSZIkaaczQZUkSZIkjQUTVEmSJEnSWDBBlSRJkiSNBRNUSZIkSdJYMEGVJEmSJI0FE1RJkiRJ0lgwQZUkSZIkjQUTVEmSJEnSWDBBlSRJkiSNBRNUSZIkSdJYMEGVJEmSJI0FE1RJkiRJ0lgYKkFNckSSq5NsTHLKgOm7Jzmvm35xkpV90x+T5LYkr1yiuCVJkiRJU2bBBDXJrsBbgSOBg4BjkhzUV+0E4NaqOgB4I/DavulvAP55x8OVJEmSJE2rYXpQDwE2VtW1VXU3sBZY01dnDfDO7vH5wOFJApDkBcDngSuXJGJJkiRJ0lRKVc1fITkKOKKqXtI9Pw44tKpO6qlzRVdnc/f8GuBQ4E7gX4BnA68EbquqPxvwHicCJwKsWLHi4LVr1y7BR9t5brxlCzfcMeooNKwVe2B7TRDba/LYZpPF9posttdksb0myzS316p9lo86hHkddthhl1XV6kHTlu3k9z4NeGNV3dZ1qA5UVWcCZwKsXr26ZmZmdnJYO+Yt517A6y/f2YtOS+XkVVttrwlie00e22yy2F6TxfaaLLbXZJnm9tp07MyoQ9huw7TI9cB+Pc/37coG1dmcZBmwHLiZ1ot6VJLXAXsB9yS5s6rO2NHAJUmSJEnTZZgE9RLgwCT70xLRo4EX9dVZBxwPfBI4Crio2tjhH56tkOQ02hBfk1NJkiRJ0n0smKBW1dYkJwEXArsCZ1XVlUlOBy6tqnXAO4BzkmwEbqElsZIkSZIkDW2oQddVtR5Y31d2as/jO4EXLvAap21HfJIkSZKkB4hhLjMjSZIkSdJOZ4IqSZIkSRoLJqiSJEmSpLFggipJkiRJGgsmqJIkSZKksWCCKkmSJEkaCyaokiRJkqSxYIIqSZIkSRoLJqiSJEmSpLFggipJkiRJGgsmqJIkSZKksWCCKkmSJEkaC0MlqEmOSHJ1ko1JThkwffck53XTL06ysis/JMlnutt/JPlfSxy/JEmSJGlKLJigJtkVeCtwJHAQcEySg/qqnQDcWlUHAG8EXtuVXwGsrqonAUcAf5Vk2RLFLkmSJEmaIsP0oB4CbKyqa6vqbmAtsKavzhrgnd3j84HDk6SqvlFVW7vyBwO1FEFLkiRJkqbPMAnqPsB1Pc83d2UD63QJ6RbgEQBJDk1yJXA58NKehFWSJEmSpG9L1fydmkmOAo6oqpd0z48DDq2qk3rqXNHV2dw9v6arc1NPnSfQelmfVVV39r3HicCJACtWrDh47dq1S/HZdpobb9nCDXeMOgoNa8Ue2F4TxPaaPLbZZLG9JovtNVlsr8kyze21ap/low5hXocddthlVbV60LRhjge9Htiv5/m+XdmgOpu7Y0yXAzf3Vqiqzya5Dfh+4NK+aWcCZwKsXr26ZmZmhghrdN5y7gW8/nIPpZ0UJ6/aantNENtr8thmk8X2miy212SxvSbLNLfXpmNnRh3CdhtmiO8lwIFJ9k+yG3A0sK6vzjrg+O7xUcBFVVXdPMsAknwP8H3ApiWJXJIkSZI0VRbcZVBVW5OcBFwI7AqcVVVXJjkduLSq1gHvAM5JshG4hZbEAjwTOCXJN4F7gP/TO+xXkiRJkqRZQ/VpV9V6YH1f2ak9j+8EXjhgvnOAc3YwRkmSJEnSA8AwQ3wlSZIkSdrpTFAlSZIkSWPBBFWSJEmSNBZMUCVJkiRJY8EEVZIkSZI0FkxQJUmSJEljwQRVkiRJkjQWTFAlSZIkSWPBBFWSJEmSNBZMUCVJkiRJY8EEVZIkSZI0FkxQJUmSJEljwQRVkiRJkjQWhkpQkxyR5OokG5OcMmD67knO66ZfnGRlV/7sJJcluby7/9Eljl+SJEmSNCUWTFCT7Aq8FTgSOAg4JslBfdVOAG6tqgOANwKv7cpvAp5XVauA44FzlipwSZIkSdJ0GaYH9RBgY1VdW1V3A2uBNX111gDv7B6fDxyeJFX16ar6Yld+JbBHkt2XInBJkiRJ0nRJVc1fITkKOKKqXtI9Pw44tKpO6qlzRVdnc/f8mq7OTX2v89Kq+rEB73EicCLAihUrDl67du0Of7Cd6cZbtnDDHaOOQsNasQe21wSxvSaPbTZZbK/JYntNFttrskxze63aZ/moQ5jXYYcddllVrR40bdn9EUCSJ9KG/T5n0PSqOhM4E2D16tU1MzNzf4S13d5y7gW8/vL7ZdFpCZy8aqvtNUFsr8ljm00W22uy2F6TxfaaLNPcXpuOnRl1CNttmCG+1wP79TzftysbWCfJMmA5cHP3fF/gvcDPV9U1OxqwJEmSJGk6DZOgXgIcmGT/JLsBRwPr+uqso50ECeAo4KKqqiR7Ae8HTqmqjy9RzJIkSZKkKbRgglpVW4GTgAuBzwLvqqork5ye5PldtXcAj0iyEXgFMHspmpOAA4BTk3ymu33Xkn8KSZIkSdLEG2rQdVWtB9b3lZ3a8/hO4IUD5vtD4A93MEZJkiRJ0gPAMEN8JUmSJEna6UxQJUmSJEljwQRVkiRJkjQWTFAlSZIkSWPBBFWSJEmSNBZMUCVJkiRJY8EEVZIkSZI0FkxQJUmSJEljwQRVkiRJkjQWTFAlSZIkSWPBBFWSJEmSNBZMUCVJkiRJY2GoBDXJEUmuTrIxySkDpu+e5Lxu+sVJVnblj0jy4SS3JTljiWOXJEmSJE2RBRPUJLsCbwWOBA4CjklyUF+1E4Bbq+oA4I3Aa7vyO4HfBV65ZBFLkiRJkqbSMD2ohwAbq+raqrobWAus6auzBnhn9/h84PAkqarbq+pjtERVkiRJkqQ5LRuizj7AdT3PNwOHzlWnqrYm2QI8ArhpmCCSnAicCLBixQo2bNgwzGwjs2IPOHnV1lGHoSHZXpPF9po8ttlksb0mi+01WWyvyTLN7TXu+dR8hklQd7qqOhM4E2D16tU1MzMz2oAW8JZzL+D1l4/FotMQTl611faaILbX5LHNJovtNVlsr8lie02WaW6vTcfOjDqE7TbMEN/rgf16nu/blQ2sk2QZsBy4eSkClCRJkiQ9MAyToF4CHJhk/yS7AUcD6/rqrAOO7x4fBVxUVbV0YUqSJEmSpt2CfdrdMaUnARcCuwJnVdWVSU4HLq2qdcA7gHOSbARuoSWxACTZBHwnsFuSFwDPqaqrlvyTSJIkSZIm2lCDrqtqPbC+r+zUnsd3Ai+cY96VOxCfJEmSJOkBYpghvpIkSZIk7XQmqJIkSZKksWCCKkmSJEkaCyaokiRJkqSxYIIqSZIkSRoLJqiSJEmSpLFggipJkiRJGgsmqJIkSZKksWCCKkmSJEkaCyaokiRJkqSxYIIqSZIkSRoLJqiSJEmSpLEwVIKa5IgkVyfZmOSUAdN3T3JeN/3iJCt7pr26K786yXOXMHZJkiRJ0hRZMEFNsivwVuBI4CDgmCQH9VU7Abi1qg4A3gi8tpv3IOBo4InAEcBfdK8nSZIkSdK9DNODegiwsaquraq7gbXAmr46a4B3do/PBw5Pkq58bVXdVVWfBzZ2rydJkiRJ0r0Mk6DuA1zX83xzVzawTlVtBbYAjxhyXkmSJEmSWDbqAACSnAic2D29LcnVo4xnCHsDN406CA3nZbbXRLG9Jo9tNllsr8lie00W22uyTHN75bWjjmBB3zPXhGES1OuB/Xqe79uVDaqzOckyYDlw85DzUlVnAmcOEctYSHJpVa0edRwaju01WWyvyWObTRbba7LYXpPF9posttd4GmaI7yXAgUn2T7Ib7aRH6/rqrAOO7x4fBVxUVdWVH92d5Xd/4EDg35cmdEmSJEnSNFmwB7WqtiY5CbgQ2BU4q6quTHI6cGlVrQPeAZyTZCNwCy2Jpav3LuAqYCvwK1X1rZ30WSRJkiRJE2yoY1Craj2wvq/s1J7HdwIvnGPePwL+aAdiHEcTMxxZgO01aWyvyWObTRbba7LYXpPF9posttcYShuJK0mSJEnSaA1zDKokSZIkSTudCeoiJDkiydVJNiY5ZdTxaH5J9kvy4SRXJbkyya+NOiYtLMmuST6d5J9GHYvml2SvJOcn+a8kn03yQ6OOSXNL8uvdd+EVSf4hyYNHHZPuLclZSW5MckVP2cOT/EuSz3X3DxtljNpmjvb60+478T+TvDfJXiMMUT0GtVfPtJOTVJK9RxGb7s0EdUhJdgXeChwJHAQck+Sg0UalBWwFTq6qg4CnAb9im02EXwM+O+ogNJQ3Ax+oqu8DfhDbbWwl2Qd4GbC6qr6fdtLDo0cblQY4Gziir+wU4ENVdSDwoe65xsPZ3Le9/gX4/qr6AeC/gVff30FpTmdz3/YiyX7Ac4Av3N8BaTAT1OEdAmysqmur6m5gLbBmxDFpHlX1par6VPf467Q/z/uMNirNJ8m+wE8Abx91LJpfkuXAs2hncaeq7q6qr440KC1kGbBHd73yPYEvjjge9amqj9KuhtBrDfDO7vE7gRfcnzFpboPaq6o+WFVbu6f/Bux7vwemgebYvgDeCLwK8MQ8Y8IEdXj7ANf1PN+Myc7ESLISeDJw8YhD0fzeRPuRuGfEcWhh+wNfAf6mG5L99iQPGXVQGqyqrgf+jNZD8CVgS1V9cLRRaUgrqupL3eMvAytGGYwW5ReBfx51EJpbkjXA9VX1H6OORduYoGrqJXko8G7g5VX1tVHHo8GS/CRwY1VdNupYNJRlwFOAv6yqJwO349DDsdUdt7iGtmPhu4GHJPm50Ualxap26QV7eSZAkt+mHWp07qhj0WBJ9gR+Czh1obq6f5mgDu96YL+e5/t2ZRpjSR5ES07Prar3jDoezesZwPOTbKINof/RJH832pA0j83A5qqaHZVwPi1h1Xj6MeDzVfWVqvom8B7g6SOOScO5IcmjAbr7G0ccjxaQ5MXATwLHltdzHGePo+20+4/uv8e+wKeSPGqkUckEdREuAQ5Msn+S3Wgnl1g34pg0jyShHR/32ap6w6jj0fyq6tVVtW9VraRtXxdVlT08Y6qqvgxcl+R7u6LDgatGGJLm9wXgaUn27L4bD8eTWk2KdcDx3ePjgQtGGIsWkOQI2qEqz6+qb4w6Hs2tqi6vqu+qqpXdf4/NwFO63zeNkAnqkLoD3k8CLqT9qL+rqq4cbVRawDOA42g9cZ/pbj8+6qCkKfKrwLlJ/hN4EvDHow1Hc+l6us8HPgVcTvv9P3OkQek+kvwD8Enge5NsTnIC8Brg2Uk+R+sJf80oY9Q2c7TXGcB3AP/S/e9420iD1LfN0V4aQ3HkgSRJkiRpHNiDKkmSJEkaCyaokiRJkqSxYIIqSZIkSRoLJqiSJEmSpLFggipJkiRJGgsmqJIkSZKksWCCKkmSJEkaCyaokiRJkqSx8P8BbxU+GQAodAgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 1152x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tree_utils.plot_sampled_STs(STs, MST_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## enumerating partitions on a grid\n",
    "we can use Zach Schutzman's [enumerator](https://github.com/zschutzman/enumerator) to generate a list of all possible partitions of an $n \\times n$ grid into $n$ equal parts. I have pre-computed these enumerations for $3 \\times 3$ - $6 \\times 6$ grids, and have stored them in `./enumerations/{n}x{n}_{n}.txt`. the function `make_partitions(n)` loads in those pre-computed lists and results in a list of all of these partitions. then, we can use the `sp_score()` and `cut_edges()` functions to compute the spanning tree and cut edges score for each partition. try it out below!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 407 ms, sys: 12 ms, total: 419 ms\n",
      "Wall time: 422 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "partitions = tree_utils.make_partitions(5) # 3-5 are instantaneous, 6 takes ~60s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "       sp(part) = 1\n",
      "cut_edges(part) = 20\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAF2CAYAAAB6XrNlAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAUDElEQVR4nO3dv24cdR+F8TO7M5ZxJEfKNsQSaylpgEjGVLEbWhpa48JchCPgKoKELwIXJgVNKkoamyrBUkKkkEjeYp1mE7JSDPL+mbcAI7/IQvbMcXbmu89HSpnfkof1mSSezCZ5nucCAITRmPR/AADAi2EHgGAYdgAIhmEHgGAYdgAIhmEHgGAYdgAIhmEHgGAYdgAIhmEHgGAYdgAIhmEHgGBS94FPXvT13d6Bdp/11Hl5pMEoV9ZM1L42p9WbLX2xsqj33513v2woNPSgowcdPd5mx8T1dMdO70ibOw/0+LCv4+FY4zNObSZSljZ0a+Gqvv18We3WnOOlw6ChBx096OgxiY6WYb+/39XX9/Z1PBxrdI7jmkmimbShu2tL+mxpoezLh0BDDzp60NFjUh1LD/v9/a6+uveL/hyML/xzZ7OGvln7aOrfCDT0oKMHHT0m2bHUsHd6R/p06yf9MRgVPULvZE39eOcTvXdtOv8IR0MPOnrQ0WPSHUvdFbO580DHw4tfjU47Ho61ufOw1Bl1RkMPOnrQ0WPSHQsP+6+HfT0+7J/r743+yyjP9aj7Wk9e9EudU0c09KCjBx09qtCx8LBv/3xQ+op0YjAca3uvYzmrTmjoQUcPOnpUoWPhYd991jvztp0iRrm0+7znOaxGaOhBRw86elShY+F/oNR5eVT0p57poPfGel4duBs+7b5SkiTWM+ug/eUPStLMdh4dPejoUWQbC/+OfTAyXZIu6bw6sP+am/Z/SFwLzi8iSXR0oaNFkZ0oPOxZ03sldp9XB+5f80zaUJ7nU/eDjnSs0o8qbGPhYW+b71FdbF2xnlcHNPSgowcdParQsfCwr95syXVhaibS6o2W57AaoaEHHT3o6FGFjoWHfeP2orLU89TfLG1oY6VtOatOaOhBRw86elShY+FX/+D6vD68Pq9mye96N5NEtxauTuVjP2noQUcPOnpUoWOpy8rW+seaKXllmkkb2lpfLnVGndHQg44edPSYdMdSr9xuzenu2pJms2LHzGZ/PZ5ymh8WREMPOnrQ0WPSHUvfaHryWEme3VwcDT3o6EFHj0l2tH6C0p3vH+pR97UGw7HOuqf+9KeEbK0vT/1V/d9o6EFHDzp6TKKjbdhPPHnR1/ZeR7vPe3rafSU1U82kDS22rmj1RksbK+2p/abKeZ1ueNB7889nI9LwYujoQUePt7mN9mH/v8P//q7wJb4EANTOZW+j52ZLAEBlMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEEyS53nuPPDJi76+2zvQ7rOefjv8XUmaKWsmal+b0+rNlr5YWdT77847XzKc0w07L480GOU0LICOHnT0eJvbaBv2Tu9ImzsP9Piwr+PhWOMzTm0mUpY2dGvhqr79fFnt1pzjpcOgoQcdPejoMYmOlmG/v9/V1/f2dTwca3SO45pJopm0obtrS/psaaHsy4dAQw86etDRY1IdSw/7/f2uvrr3i/4cjC/8c2ezhr5Z+2jq3wg09KCjBx09Jtmx1LB3ekf6dOsn/TEYFT1C72RN/XjnE713bTr/CEdDDzp60NFj0h1L3RWzufNAx8OLX41OOx6OtbnzsNQZdUZDDzp60NFj0h0LD/uvh309Puyf6++N/ssoz/Wo+1pPXvRLnVNHNPSgowcdParQsfCwb/98UPqKdGIwHGt7r2M5q05o6EFHDzp6VKFj4WHffdY787adIka5tPu85zmsRmjoQUcPOnpUoWNa9AU7L4+K/tQzHfTeWM+rA3fDp91XSpLEemYdtL/8QUma2c6jo8c0fk1L1djGwr9jH4ys/2DVfl4d2H/NzcLX6VpzjpEkOppM49e0VI1tLDzsWdP7Oxr3eXXg/jXPpA3leT51P+hYzY7T+DUtVWMbCw9723yP6mLrivW8OqChBx096OhRhY6Fh331ZkuuC1MzkVZvtDyH1QgNPejoQUePKnQsPOwbtxeVpZ6n/mZpQxsrbctZdUJDDzp60NGjCh0Lv/oH1+f14fV5NUvePdBMEt1auDqVj/2koQcdPejoUYWOpS4rW+sfa6bklWkmbWhrfbnUGXVGQw86etDRY9IdS71yuzWnu2tLms2KHTOb/fV4yml+WBANPejoQUePSXcsfcPuyWMleXZzcTT0oKMHHT0m2dH6CUp3vn+oR93XGgzHOuue+tOfErK1vjz1V/V/o6EHHT3o6DGJjpfymafbex3tPu/pafeV1Ew1kza02Lqi1Rstbay0p/abKud1uuFB780/nzFJw4uhowdf0x5v8/1oH/b/O/zv7wpf4ksAeIv4mq4Hz82WAIDKYNgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIJgkz/PceeCTF319t3eg3Wc9/Xb4u5I0U9ZM1L42p9WbLX2xsqj33513vmQ4pxt2Xh5pMMppWAAdPfia9nib70fbsHd6R9rceaDHh30dD8can3FqM5GytKFbC1f17efLarfmHC8dBg096OhBR49JdLQM+/39rr6+t6/j4VijcxzXTBLNpA3dXVvSZ0sLZV8+BBp60NGDjh6T6lh62O/vd/XVvV/052B84Z87mzX0zdpHU/9GoKEHHT3o6DHJjqWGvdM70qdbP+mPwajoEXona+rHO5/ovWvT+Uc4GnrQ0YOOHpPuWOqumM2dBzoeXvxqdNrxcKzNnYelzqgzGnrQ0YOOHpPuWHjYfz3s6/Fh/1x/b/RfRnmuR93XevKiX+qcOqKhBx096OhRhY6Fh33754PSV6QTg+FY23sdy1l1QkMPOnrQ0aMKHQsP++6z3pm37RQxyqXd5z3PYTVCQw86etDRowod06Iv2Hl5VPSnnulp95WSJLGeWXXtL39Qkma28w56b2xn1Yn7vUhHDzp6FOlY+Hfsg5H1H6xKzcLXmNpyjrp0Cf9PasL966ZjNc+riyp0LDzsWdP7u+uZtKE8z6fqh7uh+7y6oKMHHT2q0LHwsLfN96gutq5Yz6sDGnrQ0YOOHlXoWHjYV2+25LowNRNp9UbLc1iN0NCDjh509KhCx8LDvnF7UVnqeepvlja0sdK2nFUnNPSgowcdParQsfCrf3B9Xh9en1ez5J0szSTRrYWrU/nYTxp60NGDjh5V6FjqsrK1/rFmSl6ZZtKGttaXS51RZzT0oKMHHT0m3bHUK7dbc7q7tqTZrNgxs9lfj6ec5ocF0dCDjh509Jh0x9I3j588VpJnNxdHQw86etDRY5IdrZ+gdOf7h3rUfa3BcKyz7qk//SkhW+vLU39V/zcaetDRg44ek+h4KZ95ur3X0e7znp52X0nNVDNpQ4utK1q90dLGSntqv6lyXqcbHvTe/PPZiDS8GN6LHnT0eJsd7cP+f4f//V3hS3wJ4Fx4L3rQ0eOyO3putgQAVAbDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBMOwAEAzDDgDBJHme584Dn7zo67u9A+0+6+m3w9+VpJmyZqL2tTmt3mzpi5VFvf/uvPMlwzndsPPySINRTsMCeC960NHjbXa0DXund6TNnQd6fNjX8XCs8RmnNhMpSxu6tXBV336+rHZrzvHSYdDQg44edPSYREfLsN/f7+rre/s6Ho41OsdxzSTRTNrQ3bUlfba0UPblQ6ChBx096OgxqY6lh/3+fldf3ftFfw7GF/65s1lD36x9NPVvBBp60NGDjh6T7Fhq2Du9I3269ZP+GIyKHqF3sqZ+vPOJ3rs2nX+Eo6EHHT3o6DHpjqXuitnceaDj4cWvRqcdD8fa3HlY6ow6o6EHHT3o6DHpjoWH/dfDvh4f9s/190b/ZZTnetR9rScv+qXOqSMaetDRg44eVehYeNi3fz4ofUU6MRiOtb3XsZxVJzT0oKMHHT2q0LHwsO8+6515204Ro1zafd7zHFYjNPSgowcdParQMS36gp2XR0V/6pkOem+s59WBu+HT7islSWI9sw7aX/6gJM1s503je1Hia9qlCh0L/459MLL+g1X7eXVg/zU3C1+na8056tJ0vhclvqZdqtCx8LBnTe/vDN3n1YH71zyTNpTn+dT94L3oQUePKnQsPOxt8z2qi60r1vPqgIYedPSgo0cVOhYe9tWbLbkuTM1EWr3R8hxWIzT0oKMHHT2q0LHwsG/cXlSWep76m6UNbay0LWfVCQ096OhBR48qdCz86h9cn9eH1+fVLHkXRjNJdGvh6lQ+9pOGHnT0oKNHFTqWuqxsrX+smZJXppm0oa315VJn1BkNPejoQUePSXcs9crt1pzuri1pNit2zGz21+Mpp/lhQTT0oKMHHT0m3bH0jc8nj5Xk2c3F0dCDjh509JhkR+snKN35/qEedV9rMBzrrHvqT39KyNb68tRf1f+Nhh509KCjxyQ6Xspnnm7vdbT7vKeD3pt/Pq9zsXVFqzda2lhpT+03Vc7rdMOn3VdSM9VM2qDhBfFe9KCjx9v8urYPO7xOnv3C/yYgjsv+uvbcbAkAqAyGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIBiGHQCCYdgBIJgkz/PceeCTF319t3eg3Wc9dV4eaTDKlTUTta/NafVmS1+sLOr9d+edLxnO6Ya/Hf6uJM1oWADvRQ86erzNr2vbsHd6R9rceaDHh30dD8can3FqM5GytKFbC1f17efLarfmHC8dBg096OhBR49JdLQM+/39rr6+t6/j4VijcxzXTBLNpA3dXVvSZ0sLZV8+BBp60NGDjh6T6lh62O/vd/XVvV/052B84Z87mzX0zdpHU/9GoKEHHT3o6DHJjqWGvdM70qdbP+mPwajoEXona+rHO5/ovWvT+Uc4GnrQ0YOOHpPuWOqumM2dBzoeXvxqdNrxcKzNnYelzqgzGnrQ0YOOHpPuWHjYfz3s6/Fh/1x/b/RfRnmuR93XevKiX+qcOqKhBx096OhRhY6Fh33754PSV6QTg+FY23sdy1l1QkMPOnrQ0aMKHQsP++6z3pm37RQxyqXd5z3PYTVCQw86etDRowod06Iv2Hl5VPSnnulp95WSJLGeWXXtL39Qkma28w56b2xn1QnvRQ/3+5GOHkW+rgv/jn0wsv6DValZ+BpTW87/+dIl/D+pCd6LHu73Ix09iry/Cw971vReiWfShvI8n6of7obu8+qC92I134909ChyXuFhb5vvUV1sXbGeVwc09KCjBx09qtCx8LCv3mzJdWFqJtLqjZbnsBqhoQcdPejoUYWOhYd94/aistTz1N8sbWhjpW05q05o6EFHDzp6VKFj4Vf/4Pq8Prw+r2bJ73o3k0S3Fq5O5WM/aehBRw86elShY6nLytb6x5opeWWaSRvaWl8udUad0dCDjh509Jh0x1Kv3G7N6e7akmazYsfMZn89nnKaHxZEQw86etDRY9IdS99oevJYSZ7dXBwNPejoQUePSXa0foLSne8f6lH3tQbDsc66p/70p4RsrS9P/VX932joQUcPOnpMouOlfObp9l5Hu897Oui9+efzERdbV7R6o6WNlfbUflPlvGjoQUcPOnq8zY72YQcATJbnZksAQGUw7AAQDMMOAMEw7AAQDMMOAMEw7AAQDMMOAMEw7AAQDMMOAMEw7AAQDMMOAMEw7AAQzP8A2bJtXodef2UAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-9-d6c08f4a3051>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"       sp(part) = {tree_utils.sp_score(partition)}\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"cut_edges(part) = {tree_utils.cut_edges(partition)}\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0mtree_utils\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdraw_plan\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpartition\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdelay\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m~/Desktop/mggg/trees/tree_utils.py\u001b[0m in \u001b[0;36mdraw_plan\u001b[0;34m(partition, delay)\u001b[0m\n\u001b[1;32m     49\u001b[0m             \u001b[0medges\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medge\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     50\u001b[0m     \u001b[0mgraph\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupdate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medges\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0medges\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 51\u001b[0;31m     \u001b[0mdraw\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgraph\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdelay\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mdelay\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     52\u001b[0m     \u001b[0;32mreturn\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     53\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/Desktop/mggg/trees/tree_utils.py\u001b[0m in \u001b[0;36mdraw\u001b[0;34m(graph, delay, edge_colors, node_colors)\u001b[0m\n\u001b[1;32m     37\u001b[0m            )\n\u001b[1;32m     38\u001b[0m     \u001b[0mplt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshow\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 39\u001b[0;31m     \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msleep\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdelay\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     40\u001b[0m     \u001b[0mclear_output\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mwait\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     41\u001b[0m     \u001b[0;32mreturn\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "for partition in partitions:\n",
    "    print(f\"       sp(part) = {tree_utils.sp_score(partition)}\")\n",
    "    print(f\"cut_edges(part) = {tree_utils.cut_edges(partition)}\")\n",
    "    tree_utils.draw_plan(partition, delay=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}