Week6_debruijn_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 6 lab - de novo assembly with De Bruijn graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this week's lab you'll be writing programs to count k-mers and to find the edges of a de Bruijn graph.\n",
    "\n",
    "As a reminder, we have a relevant tutorial document intended for those new to programming or learning Python: <a href=\"kmer_workshop.html\">kmer-counting tutorial</a>. The first couple of challenges below are covered (more gently) in this tutorial. By now you have probably already learned the programming concepts in the tutorial, but you might still find it worth looking at the [Dictionaries: algorithmic considerations](kmer_workshop.html#dictionaries) section. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll define some toy \"reads\" from English strings, which you can use to see your functions in action."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ters_no',\n",
       " 'ers_not',\n",
       " 'matners',\n",
       " 'size_ma',\n",
       " 'tters_',\n",
       " 'atters_n',\n",
       " 'size_m',\n",
       " 'e_matter']"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "yoda_reads = '''\n",
    "ters_no\n",
    "ers_not\n",
    "matners\n",
    "size_ma\n",
    "tters_\n",
    "atters_n\n",
    "size_m\n",
    "e_matter'''.strip().split(\"\\n\")\n",
    "yoda_reads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "caesar_reads = '''\n",
    "_your_e\n",
    "l,nd_me\n",
    "nd_me_y\n",
    "d_me_y\n",
    "omans,_\n",
    "s,_coun\n",
    "me_you\n",
    "eids,_\n",
    "mans,_c\n",
    "our_ea\n",
    "'''.strip().split(\"\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# a version with no read errors\n",
    "caesar_reads_perfect = '''\n",
    "me_your_e\n",
    "ymen,_len\n",
    "_your_e\n",
    "ds,_Roma\n",
    "nds,_Roma\n",
    "trymen,_\n",
    "lend_me_\n",
    "omans,_co\n",
    "n,_lend_\n",
    "riends,_R\n",
    "ntrymen\n",
    ",_country\n",
    "e_your_ears\n",
    "untryme\n",
    "riends,_\n",
    "'''.strip().split(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And some error-free \"reads\" from a very small tRNA gene:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "mt_te_reads = '''TGTAGTTGAAATACAACGAT\n",
    "GGTCGTGGTTGTAGTCCGTGC\n",
    "TGGTCGTGGTTGTAGTCCG\n",
    "TATCATTGGTCGTGGTTGTAG\n",
    "TTGTAGTTGAAATACAACGAT\n",
    "ATCATTGGTCGTGGTTGTAG\n",
    "ATGGTTTTTCATATCATTGG\n",
    "GGTTTTTCATATCATTGGTCGT\n",
    "GGTCGTGGTTGTAGTCCGT\n",
    "TCATTGGTCGTGGTTGTAGTCC\n",
    "GGTCGTGGTTGTAGTCCGTGCG\n",
    "GATGGTTTTTCATATCATT\n",
    "TGGTCGTGGTTGTAGTCC\n",
    "AACGATGGTTTTTCATATCA\n",
    "GGTTTTTCATATCATTGGTCG\n",
    "GTTTTTCATATCATTGGTCGTG\n",
    "ATTGGTCGTGGTTGTAGTCCGT\n",
    "AACGATGGTTTTTCATAT\n",
    "GTTTTTCATATCATTGGT\n",
    "AACGATGGTTTTTCATAT'''.strip().split()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Counting k-mers "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1:**\n",
    "\n",
    "Complete the function below to return all the k-mers from a given string. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_string_kmers(read, k):\n",
    "    '''\n",
    "    Return a set of all k-mers of length k from string read.\n",
    "    '''\n",
    "    # Note that if k > len(read), a negative num_kmers will just return an empty list, which is fine\n",
    "    num_kmers = len(read)-k+1\n",
    "    # We could use a list comprehension for conciseness, set([read[i:i+k] for i in range(num_kmers)])\n",
    "    # but this would potentially make a large temporary list in memory\n",
    "    kmers = set()\n",
    "    for i in range(num_kmers):\n",
    "        kmers.add(read[i:i+k])\n",
    "    return kmers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'_yo', 'our', 'r_e', 'ur_', 'you'}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_string_kmers(caesar_reads[0], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2:**\n",
    "\n",
    "Write a function which applies `get_string_kmers()` to a list of strings and returns all kmers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A version using *list syntax to pass all sets to set.union()\n",
    "def get_kmers(reads, k):\n",
    "    '''\n",
    "    Given a list of strings representing reads, and a value k, \n",
    "    return a set of all k-mers of length k.\n",
    "    '''\n",
    "    return set.union(*[get_string_kmers(r,k) for r in reads])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# A version using a loop and set.update()\n",
    "def get_kmers(reads, k):\n",
    "    '''\n",
    "    Given a list of strings representing reads, and a value k, \n",
    "    return a set of all k-mers of length k.\n",
    "    '''\n",
    "    all_kmers = set()\n",
    "    for read in reads:\n",
    "        all_kmers.update(get_string_kmers(read,k))\n",
    "    return all_kmers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{',_cou',\n",
       " ',nd_m',\n",
       " '_coun',\n",
       " '_me_y',\n",
       " '_your',\n",
       " 'ans,_',\n",
       " 'd_me_',\n",
       " 'e_you',\n",
       " 'eids,',\n",
       " 'ids,_',\n",
       " 'l,nd_',\n",
       " 'mans,',\n",
       " 'me_yo',\n",
       " 'nd_me',\n",
       " 'ns,_c',\n",
       " 'omans',\n",
       " 'our_e',\n",
       " 's,_co',\n",
       " 'ur_ea',\n",
       " 'your_'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_kmers(caesar_reads, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building a graph with networkx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could represent a graph using Python data structures. For instance, here is one way to represent a graph where nodes B and C are linked from A:\n",
    "    \n",
    "    B <- A -> C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = ['A','B','C']\n",
    "edges = [('A','B'), ('A','C')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that a tree is a kind of graph, and we have already built trees using data structures in past labs.\n",
    "\n",
    "This time we'll use a library `networkx` intended specifically for graph manipulation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pylab as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's how to build that same graph in networkx. Note that we use `DiGraph` instead of `Graph`, which gives a directed graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = nx.DiGraph()\n",
    "g.add_edge('A','B')\n",
    "g.add_edge('A','C')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could have explicitly added nodes with code like `g.add_node('A')`, but since every node is connected to at least one edge in this case, networkx automatically adds the nodes for us when the edges are added. \n",
    "\n",
    "Remember you can look at networkx method documentation with `?` or `help()`. Have a look at the documentation for the `add_edge` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "NodeView(('A', 'B', 'C'))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OutEdgeView([('A', 'B'), ('A', 'C')])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a way to draw the graph with a spring layout, where networkx will try to place nodes so they are not too close together. This is a simple layout algorithm - it's easy to see the result for this tiny graph, but may be difficult see for graphs of any size. The layout is somewhat random and for larger graphs, will be different every time you draw it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeEAAAFCCAYAAADGwmVOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGpxJREFUeJzt3XtwlPWh//HPsyokwZpiBbnK/Q7hIvHumAsBEsolEIi5kISEchcEQUAKpaf9lX885zdnpjP9/dHxh9BaFQMh5H4lVisW7LQwPa2247G0jhr8yUEtScnl+f2xZM1CAiHs7vfZ3fdrxnGS7O58nHHmPc+zzz5r2bZtCwAABJzL9AAAAMIVEQYAwBAiDACAIUQYAABDiDAAAIYQYQAADCHCAAAYQoQBADCECAMAYAgRBgDAECIMAIAhRBgAAEOIMAAAhhBhAAAMIcIAABhChAEAMIQIAwBgCBEGAMAQIgwAgCFEGAAAQ4gwAACGEGEAAAwhwgAAGEKEAQAwhAgDAGDInaYHwIEaG6WDB6WzZ6VLl6ToaCkmRlq1ShowwPQ6AAgZlm3btukRcIjTp6UDB6TycvfPzc3f/C0yUrJtKTlZ2r1bio01sxEAQggRhtvPfiZt3y41Nblj2x3Lcgf5xRel9esDtw8AQhCno/FNgC9fvvljbdv9uO3b3T8TYgDoNY6Ew93p01JcnFeAR0r6TNIdku6S9Jik/yNp+LXPjYqSGhqk2bMDMhUAQg1XR4e7Awfcp6CvcULS15I+kXS/pGe6em5Tk/v5AIBeIcLhrLHRfRHWDU6GREhKk/RfXf3RtqWyMunCBT8NBIDQRoTD2cGDN33IZUmvSXqkuwdYVo9eBwBwPS7MCmdnz3p/DKmTJXL/z/G1pIGSKrt7jaYm6dw5v8wDgFDHkXA4u3Sp2z8VSfofSf+S9FNJT0n6tLsHX7zo62UAEBaIcDiLjr7pQ+6QtPTqv9/q7kH9+/tuEwCEESIczmJipIiIGz7ElnRc0kVJk7p6QGSkNG2a77cBQBjgc8LhrLFRGjHiuveFR+qbzwlbkkZI2i0pq6vXiIiQzp/nntIA0AtcmBXOBg503wu6qMjrY0of9fT5liWlpBBgAOgljoTDXRd3zOox7pgFALeF94TDXWys+8sYoqJu6Wktd92lH0VHq+gf/1BzNx9zAgDcGBGG+0sYOkJsWTd+rGVJUVH60+rV2vfJJ0pPT9e9996rpUuX6tSpU4HZCwAhggjDbf1696nl1FT3xVaRkd5/j4x0/z41VWpo0NSf/lT33HOPrly5oqamJhUXF+uVV14xsx0AghTvCeN6Fy64b0V57pz7Rhz9+7s/hpSX53UR1urVq/XSSy9JkiZPnqw//OEPuuOOO8xsBoAgRITRaw0NDYqLi9OSJUv0/vvv6+mnn9a+fftMzwKAoMFHlNBrTzzxhF577TWlpaXpwoULio+Pl2VZ2rt3r+lpABAUOBKGz3z66aeKj49Xdna29uzZY3oOADgeR8LwmUGDBqmurs5zRPzCCy+YngQAjkaE4VODBw9WfX294uLi5HK5tGvXLtOTAMCxiDB8rnOILcvSzp07TU8CAEciwvCLIUOGqL6+XvHx8XK5XNqxY4fpSQDgOEQYfjN06FCvI+Lt27ebngQAjkKE4VedQ+xyubRt2zbTkwDAMYgw/G7YsGGeU9OWZWnr1q2mJwGAIxBhBMTw4cM9H19yuVzasmWL6UkAYBwRRsA88MADXu8Rb9682fQkADCKCCOgOkLccUS8adMm05MAwBgijIAbMWKE1521Nm7caHoSABhBhGHEyJEjvU5Nb9iwwfQkAAg4IgxjOofY5XJp3bp1picBQEARYRg1atQor48vrV271vQkAAgYIgzjRo8e7fUe8Zo1a0xPAoCAIMJwhDFjxqiurk4JCQlyuVxavXq16UkA4HdEGI4xduxYryPigoIC05MAwK+IMBylI8QJCQmyLEv5+fmmJwGA3xBhOM64ceNUW1vrOTWdl5dnehIA+AURhiONHz9etbW1SkxMlGVZys3NNT0JAHyOCMOxJkyYoJqaGk+Ic3JyTE8CAJ8iwnC0iRMneo6IXS6XsrOzTU8CAJ8hwnC8iRMneh0RZ2VlmZ4EAD5BhBEUJk2apJqaGs2ZM0eWZSkzM9P0JAC4bUQYQWPy5Mmqrq5WUlKSLMtSRkaG6UkAcFuIMILKlClTVFVVpaSkJLlcLqWnp5ueBAC9RoQRdKZOnaqqqirNnTtXlmVpxYoVpicBQK8QYQSladOmqbKy0hPi5cuXm54EALeMCCNoxcTEqLKyUvPmzZNlWUpLSzM9CQBuCRFGUJs+fboqKio0f/58WZalZcuWmZ4EAD1GhBH0ZsyYofLyciUnJ8vlcik1NdX0JADoESKMkDBz5kyVlZUpOTlZlmVpyZIlpicBwE0RYYSMWbNmeY6ILcvS4sWLTU8CgBsiwggps2bNUllZmVJSUmRZlhYtWmR6EgB0iwgj5Dz44IMqLS3VggULZFmWFi5caHoSAHTJZXoA4A+zZ89WSUmJCgoKVFJSYnoOAHSJCCNkxcbGqqSkRPn5+SorKzM9BwCuQ4QR0h566CGdOHFCeXl5Ki8vNz0HALwQYYS8hx9+WMXFxcrNzVVFRYXpOQDgQYQRFh555BEdP35cOTk5qqysND0HACQRYYSRRx99VEVFRVq5cqWqqqpMzwEAIozw8thjj+nYsWPKzs5WdXW16TkAwhwRRth5/PHHdfToUWVlZammpsb0HABhjAgjLD3xxBMqLCxURkaGamtrTc8BEKaIMMLWk08+6QlxXV2d6TkAwpBl27ZtegRgUkNDg9LS0nTkyBHFxcWZngMgjHAkjLD31FNP6ciRI1qxYoUaGhpMzwEQRogwICkuLk6vvvqq0tLS9Oabb5qeAyBMEGHgqoSEBE+If/3rX5ueAyAMEGGgk8TERP3qV7/SsmXL9NZbb5meAyDEEWHgGomJifrlL3+ppUuX6u233zY9B0AII8JAF5KSkvSLX/xCqamp+s1vfmN6DoAQRYSBbsydO1eHDx/WkiVL9M4775ieAyAEEWHgBubNm6dDhw5p8eLFOnXqlOk5AEIMEQZuYv78+Xr55Ze1aNEivfvuu6bnAAghRBjogeTkZB08eFALFy7Ub3/7W9NzAIQIIgz0UEpKil566SUtXLhQp0+fNj0HQAggwsAt+O53v6uf//znWrBggc6cOWN6DoAgR4SBW7Rw4UJPiN977z3TcwAEsTtNDwCC0aJFi2TbtlJSUlReXq5Zs2aZngQgCBFhoJcWL14s27aVnJxMiAH0ChEGbsOSJUs8Ia6oqNDMmTNNTwIQRIgwcJtSU1PV3t7uCfGMGTNMTwIQJIgw4APLli2TbduaP3++KisrNX36dNOTAAQBIgz4SFpamleIY2JiTE8C4HBEGPCh5cuXy7ZtzZs3T1VVVZo2bZrpSQAcjAgDPrZixQrZtq25c+equrpaU6dONT0JgEMRYcAP0tPT1d7erqSkJNXU1GjKlCmmJwFwICIM+ElGRoZs2/aEePLkyaYnAXAYIgz4UWZmpmzb1pw5cwgxgOsQYcDPsrKyvI6IJ02aZHoSAIcgwkAAZGdnq729XXPmzFFtba0mTpxoehIAByDCQIDk5OR4Tk3X1tZqwoQJpicBMIwIAwGUm5sr27aVmJiouro6jR8/3vQkAAYRYSDA8vLy1N7e7gnxuHHjTE8CYAgRBgzIz8+XbdtKSEggxEAYI8KAIQUFBV6npseOHWt6EoAAI8KAQatXr1Z7e7sSEhJUX1+vMWPGmJ4EIICIMGDYmjVrPKem6+vrNXr0aNOTAAQIEQYcYO3atV4hHjVqlOlJAAKACAMOsW7dOrW3tys+Pl4nT57UyJEjTU8C4GdEGHCQDRs2yLZtxcfHq76+nhADIY4IAw6zceNGr4u1RowYYXoSAD8hwoADPfPMM54j4pMnT+qBBx4wPQmAHxBhwKE2b97s9R7x8OHDTU8C4GNEGHCwZ5991us9YkIMhBYiDDjc1q1bvU5NDxs2zPQkAD5ChIEgsG3bNq9T00OHDjU9CYAPEGEgSGzfvt3r1DQhBoIfEQaCyI4dO7w+vjRkyBDTkwDcBiIMBJmdO3d6vUc8ePBg05MA9BIRBoLQrl27PO8R19fXE2IgSBFhIEi98MILXl/6MGjQINOTANwiIgwEsT179ni9R3z//febngTgFhBhIMjt3bvXc0RcV1dHiIEgQoSBELBv3z6vI+KBAweangSgB4gwECL279/v9R7xgAEDTE8CcBNEGAgh+/fv9xwR19XVeYe4sVE6eFA6e1a6dEmKjpZiYqRVqySCDRhh2bZtmx4BwHds29bevXtVXFysuro63fff/y0dOCCVl7sf0Nz8zYMjIyXblpKTpd27pdhYM6OBMEWEgRBk27b27NmjqEOHtOeLL2Q1N7tj2x3Lcgf5xRel9esDNxQIc5yOBkKQZVn6X8OHq+Wzz2S1tt78CbYtXb4sbd/u/pkQAwHBkTAQik6fluLi3GG9RpykP0j6VFLfrp4bFSU1NEizZ/tzIQBJLtMDAPjBgQNSU9N1v/5I0q8lWZKKu3tuU5P7+QD8jiNhINQ0NkojRnhfgHXVv0mqlPSwpA8klXT3GhER0vnzXDUN+BlHwkCoOXiw2z8dkpR19Z9KSZ9190DLuuHrAPANIgyEmrNnuzwKfkvS3yStkPSgpDGSXunuNZqapHPn/LUQwFVEGAg1ly51+euXJc2VdN/VnzOv/q5bFy/6dBaA6/ERJSDUREdf96smSa9LapPU8YWH/5L0P3JfKT29q9fp398/+wB4cCQMhJqYGPeFVZ0USbpD0n9J+v3Vf/4k6Um53ye+TmSkNG2af3cC4OpoIOR0cXX0fElTJP37NQ99XdJmSf/QNafFuDoaCAgiDISipUuloqIb36qyO5YlpaZKhYW+3wXACxEGQtEN7ph1M3ZkpKw33+SOWUAA8J4wEIpiY91fxhAVdUtP+9edd+rfBw/WVxMm+GkYgM6IMBCq1q//JsSWdePHWpYUFaW7/vM/9UFiolJSUvTVV18FZicQxjgdDYS6M2fc94IuK3PHtvM9pTu+Tzglxf19wrNnq729XWvXrtX777+vsrIy3X333ea2AyGOCAPh4sIF960oz51z34ijf3/3x5Dy8q67Crq9vV1r1qzRX/7yF5WWlhJiwE+IMIAutbe3a/Xq1frwww9VWlqqfv36mZ4EhBwiDKBb7e3tKigo0EcffaSSkhJCDPgYEQZwQ21tbSooKND58+dVUlKiqFu84hpA94gwgJtqa2vTqlWr9PHHH+vEiROEGPARIgygR9ra2pSXl6dPPvlEJ06cUGRkpOlJQNAjwgB6rK2tTbm5uWpsbNTx48cJMXCbiDCAW9LW1qacnBx9/vnnKioqIsTAbSDCAG5Za2urVq5cqYsXL6qoqEgR13x1IoCeIcIAeqW1tVXZ2dm6dOmSjh07RoiBXiDCAHqttbVVWVlZ+uqrr3Ts2DH17dvX9CQgqBBhALeltbVVmZmZ+uc//6mjR48SYuAWEGEAt62lpUUZGRlqbm5WYWEhIQZ6iAgD8ImWlhY9/fTTamlp0ZEjRwgx0ANEGIDPtLS0KD09XW1tbTpy5Ij69OljehLgaC7TAwCEjrvuukuvvvqqXC6XVqxYoStXrpieBDgaEQbgU3369NFrr70mSUpPT1dLS4vhRYBzEWEAPtenTx+9/vrramtrI8TADRBhAH7Rp08fHTlyxHPlNCEGrkeEAfhN37599cYbb6i5uVmZmZmEGLgGEQbgV3379lVhYaEuX76srKwstba2mp4EOAYRBuB3HSH++uuvCTHQCREGEBARERE6evSovvzyS61cuZIQAyLCAAIoIiJCx44d0xdffKGcnBxCjLBHhAEEVEREhIqKivT5558rNzdXbW1tpicBxhBhAAEXGRmp48ePq7GxkRAjrBFhAEZ0hPjTTz/VqlWrCDHCEhEGYExUVJSKi4v18ccfKz8/nxAj7BBhAEZFRUXpxIkT+vvf/66CggJCjLBChAEY1xHiv/3tb/re976n9vZ205OAgCDCAByhX79+Kikp0YcffkiIETaIMADH6Nevn0pLS/XXv/5Va9asIcQIeUQYgKN0hPiDDz7Q2rVrCTFCGhEG4Dh33323ysrK9Oc//1nr168nxAhZRBiAI3WE+I9//KM2bNhAiBGSiDAAx/rWt76l8vJynTt3Tps2bZJt26YnAT5FhAE4WkeIf//73xNihBwiDMDx7rnnHlVUVOh3v/udnnnmGUKMkEGEAQSFjhCfOXNGW7ZsIcQICUQYQNCIjo5WZWWl3n33XT377LOEGEGPCAMIKh0hfuedd7R161ZCjKBGhAEEnW9/+9uqqqrS22+/reeee44QI2gRYQBBqSPEb775prZv306IEZSIMICg1b9/f1VXV+vkyZN6/vnnCTGCDhEGENQ6QlxbW6udO3cSYgQVIgwg6N17772qqalRdXW1du/eTYgRNO40PQAAfKEjxImJibIsSz/5yU9kWZbpWcANEWEAIeM73/mOJ8Qul0s//vGPCTEcjQgDCCn33XefamtrlZCQIMuy9KMf/YgQw7GIMICQ0xHijiPiH/7wh4QYjkSEAYSkAQMGeI6IXS6X9u/fb3oScB0iDCBkdYQ4Pj5elmXpBz/4gelJgBciDCCkDRw4UHV1dZ73iPft22d6EuBBhAGEvPvvv191dXWKj4+Xy+XS97//fdOTAElEGECY6Bxiy7K0Z88e05MAIgwgfAwaNMjriHj37t2mJyHMEWEAYWXw4MGqr69XXFycLMvSrl27TE9CGCPCAMJOR4g7joiff/5505MQpogwgLA0ZMgQr/eId+zYYXoSwhARBhC2hg4d6jk17XK59Nxzz5mehDBDhAGEtc4htixL27ZtMz0JYYQIAwh7w4YN87xHbFmWtm7danoSwgQRBgBJw4cP9/r40pYtW0xPQhggwgBw1QMPPOB1anrz5s2mJyHEEWEA6KQjxB1HxJs2bTI9CSGMCAPANUaMGOH18aWNGzeanoQQRYQBoAsjR470OjW9YcMG05MQgogwAHSjc4hdLpfWrVtnehJCDBEGgBsYNWqU18eX1q5da3oSQggRBoCbGD16tNd7xGvWrDE9CSGCCANAD4wZM0Z1dXVKSEiQy+XS6tWrTU9CCCDCANBDY8eO9ToiLigoMD0JQY4IA8At6AhxQkKCLMtSfn6+6UkIYkQYAG7RuHHjVFtb6zk1nZeXZ3oSghQRBoBeGD9+vCfElmUpNzfX9CQEISIMAL00YcIE1dbWKjExUZZlKScnx/QkBBkiDAC3YeLEiaqpqdGcOXPkcrmUnZ1tehKCCBEGgNs0adIkVVdXa86cObIsS1lZWaYnIUgQYQDwgcmTJ3uOiC3LUmZmpulJCAJEGAB8ZPLkyaqurlZSUpIsy1JGRobpSXA4IgwAPjRlyhRVVVUpKSlJLpdL6enppifBwYgwAPjY1KlTVVVVpblz58qyLK1YscL0JDgUEQYAP5g2bZoqKys9IV6+fLnpSXAgIgwAfhITE6PKykrNmzdPlmUpLS3N9CQ4DBEGAD+aPn26KioqNH/+fFmWpWXLlpmeBAchwgDgZzNmzFB5ebmSk5NlWZaWLl1qehIcgggDQADMnDlTZWVlnhCnpqaangQHIMIAECCzZs3yHBG7XC4tXrzY9CQYRoQBIIBmzZqlsrIypaSkyLIsLVq0yPQkGESEASDAHnzwQZWWlmrBggWyLEsLFy40PQmGuEwPAIBwNHv2bJWUlKigoEAlJSWm58AQIgwAhsTGxqqkpET5+fkqLS01PQcGEGEAMOihhx7SiRMntGrVKpWVlZmegwAjwgBg2MMPP6zi4mLl5eWpoqLC9BwEEBEGAAd45JFHdPz4ceXk5KiystL0HAQIEQYAh3j00UdVVFSklStXqqqqyvQcBAARBgAHeeyxx3Ts2DFlZ2erurra9Bz4GREGAId5/PHHVVhYqMzMTNXU1JieAz8iwgDgQE8++aQKCwuVkZGh2tpavffee3rqqafU0tJiehp8yLJt2zY9AgDQtYaGBi1evFhXrlxRW1ubiouLNW/ePNOz4CMcCQOAg/Xr109XrlxRU1OTrly5osOHD5ueBB/iSBgAHCwuLk6nTp3SlStXZNu2IiMj9eWXX+rOOzvd+r+xUTp4UDp7Vrp0SYqOlmJipFWrpAEDjG3HzRFhAHCw1tZWnTx5Ui+//LLeeOMNNTc369ChQ1q5cqV0+rR04IBUXu5+cHPzN0+MjJRsW0pOlnbvlmJjzfwH4IaIMAAEiZaWFh0+fFiJiYkaUVYmbd8uNTW5Y9sdy3IH+cUXpfXrAzcWPUKEASDY/Oxn7gBfvtzz50RFEWIHIsIAEExOn5bi4q4L8CuS/kPSnyV9S9IMSXskPdH5QVFRUkODNHt2YLbiprg6GgCCyYED7lPQnfyHpGclvSDpM0nnJW2QdPza5zY1uZ8Px+BIGACCRWOjNGKE1wVYlyQNlfR/JS3vyWtEREjnz3PVtENwJAwAweLgwet+9Y6kZkmpPX0Ny+rydWAGEQaAYHH2rPfHkCT9P0n3Sbqzyyd0oalJOnfOx8PQW0QYAILFpUvX/eo7kj6X1Horr3Pxoo8G4XYRYQAIFtHR1/3qUUkRkopu5XX69/fRINwuIgwAwSImxn1hVSfRkv5N0ka5Q3xZUoukcknPd/UakZHStGn+3Yke4+poAAgWXVwd3eGXkv63pD/J/TnhB+X+nPBj1z6Qq6MdhQgDQDBZulQqKrrxrSq7Y1lSaqpUWOj7XegVIgwAwaSbO2b1CHfMchzeEwaAYBIb674HdFTUrT2v497RBNhRevzRMgCAQ3R8CQPfohT0OB0NAMHqzBn3vaDLytyx7XxP6Y7vE05JcX+fMEfAjkSEASDYXbjgvhXluXPuG3H07+/+GFJeHldBOxwRBgDAEC7MAgDAECIMAIAhRBgAAEOIMAAAhhBhAAAMIcIAABhChAEAMIQIAwBgCBEGAMAQIgwAgCFEGAAAQ4gwAACGEGEAAAwhwgAAGEKEAQAwhAgDAGAIEQYAwBAiDACAIUQYAABDiDAAAIYQYQAADCHCAAAYQoQBADCECAMAYAgRBgDAECIMAIAhRBgAAEOIMAAAhhBhAAAMIcIAABhChAEAMIQIAwBgCBEGAMAQIgwAgCFEGAAAQ4gwAACGEGEAAAwhwgAAGPL/Ac/z1n0U2v/1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nx.draw_spring(g, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeEAAAFCCAYAAADGwmVOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAG0VJREFUeJzt3XmQ1OWdx/F398zQjMOlIOC5WgpeKN7gtR4hukZUFDUeMV5kdTWa6BoLORQMiMaoidG4SSrJqhvQQleN5RU1q1EjHlFRZIBRg0gEosQRGIZmjt/+8WQSNUigp6efPt6vqq5GavrXX6uUD9/nTCVJkiBJkgouHbsASZIqlSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRWIIS5IUiSEsSVIkhrAkSZEYwpIkRVIduwBJkjZGkkBbW3hPEkilwquqKryXEkNYklTUkgRaWyGbDe9J8sU/m0pBdTVkMuG92EM5lSTr+9eRJCmOJAnBm81Ce/vGfz6dDmGcyRRvGBvCkqSi09oKTU25he/npdNQVxc642JjCEuSikaSQHNz6H7zLZOB2tri6ooNYUlSUUiS0P22tHTdd9TUhK64WILYLUqSpOgKEcAQnt/UtP7FXYVkCEuSomtu7voA7tDSEr6vGBjCkqSoOrYfFVLHdqfYDGFJUjQdw9AxFMOwtCEsSYom1z3A+dDeXvgO/PMMYUlSFB2HccSUzcbthg1hSVIUra3xuuAO7e1x54YNYUlSFJ3pgu+9dzpHHLEv22zTg1122YKTTz6aWbOeK3gdnWUIS5KiyLUDve22mxg37ttceuk45s1bxhtvLOK88y7kkUcezOl5bW251ZEPnpglSSq4JIHGxo3/3IoVn7Dbblvxox/9klGjTs5bPX36xDlFy05YklRwuXafL730AmvWrGHkyBOKop7OMoQlSQWX6xjsxx8vp2/fflTn+UqkWGPChrAkqeByDb1NN+3L8uUf0ZrnJc2GsCSpYuQ6/7r//gfQvXt3Hn74gaKop7MMYUlSweUaer169Wbs2Gu44oqLePjhB1i9ejUtLS088cSjXH31FQWvp7NcHS1JKrhcV0d3mDnzV9x++80sWFBPjx49GTp0Hy67bDzDhh2Y0/NirY42hCVJUTQ2xr9AASCdht69I313nK+VJFW6PC9wzllVVbzvNoQlSVFkMrErCGLWYQhLkqKorg5DwTGl03E7ckNYktT1/vhHGDYMdt0VBg2C/v1J9agj07Q8almZTLyV0QBFMiIvSSpr/frB3LmwatXff2/oUDIDNyO7Ms6Vhul0/CFxO2FJUtdbuBC23fbvbeemm8KTT5JKp6iri1NSXV3cLhgMYUlSV/rjH+HMM+HLX4Zzz4W+faFbN7j77tAdE+ZkC92RZjLFsTq7CEqQJJWdZctgyhSYPh0uuQR+/GPo2RN22AFmz4Yjj/zMj9fWhiHplpauL62mJnxfMfCwDklS/nzyCXz/+yF0v/51GDcONt98gz6aJNDU1LVBXFNTHMPQHRyOliR13po1cOONYeXz4sXw6qtw880bHMAQgrGuruuGpjOZ4gpgcDhaktQZra1wxx0waRLsuy/83//Bbrvl/LhUCjbZJEwbNzXlZ9V0Oh3CtxjmgD+vCEuSJBW9JIH//V8YPx4GDoSZM2H48Lw9vroaevWCbDa8cgnjji1IsfcCr49zwpKkjfPUUzB2LLS1wbRpYZFVF6ZckoSGO5sNX7m+QE6nw1nQHaufizV8OxjCkqQN8/LLYaHVwoVh5fPJJ0c5dzJJQhgnSXilUuFVVVX8oft5LsySJK3fvHlw0kkwalR4nzsXvvrVaAc/p1Khy62pCXPHNTWl0fWuiyEsSVq399+HMWPgkENg//2hoQHOPz+knvLCEJYkfdby5XD55bDnntC/PyxYAFdcEZYtK68MYUlSsGpVmOvdaSdYvRrmzIFrrw3nPKtLGMKSVOnWroVbbw0HbcydC7NmhROvttgidmVlz33CklSp2tpgxgy46irYeWd49NEwBK2CMYQlqdIkCTz8cNhu1KMH/PKXcOihsauqSIawJFWS554LB200Nob53mOPLc29PWXCEJakSjB7djhi8q23YPJkOOOMcLqFonJhliSVs3feCYF71FHhNW9euGLQAC4KhrAklaOlS+Gii2DYsLDoqqEBLr646+4JVE4MYUkqJ42NYdh5t92ge/fQ+U6cCD17xq5M62AIS1I5aG6GG26AwYNDF/zaa3DjjdCvX+zKtB4uzJKkUtbaGrYYTZ4chp6feQZ22SV2VdpAhrAklaL2drjvPpgwAbbaKvx62LDYVWkjGcKSVEqSBJ58Eq68MvzzrbfCiBHu9S1RhrAklYqXXgrhu3gxTJ0Ko0cbviXOhVmSVOzq60Pgjh4Np50WDtw46SQDuAwYwpJUrBYtgvPOC+c6H3BAuNd3zBiodhCzXBjCklRsPvoILrsM9torXCe4YAFcfjnU1sauTHlmCEtSsVi5Eq65JpxwtXZtGHaeMgX69IldmbqIISxJsWWzcMstMGhQ6HpffDGseh44MHZl6mJOLEhSLG1t8KtfwVVXwZAh8PjjMHRo7KpUQIawJBVaksBDD8G4cWGo+a674JBDYlelCAxhSSqk3/0Oxo4N87/XXQfHHONWowpmCEtSIbz+euh86+vhu98N+32907fiuTBLkrrS22/D6afD0UfDV74C8+fD175mAAswhCWpayxZAhdeCMOHh7t9Gxrgm9+Ebt1iV6YiYghLUj41NoZh5yFDoK4udL7jx0OPHrErUxEyhCUpH1avhu99L+z1/fDDMAd8ww3Qt2/sylTEXJglSZ3R0gK/+EU46erAA+HZZ8OJV9IGMIQlKRft7TBzJkyYANttBw88APvtF7sqlRhDWJI2RpLAb34T7vWtqoLbb4cRI2JXpRJlCEvShpo1K4TvkiUwdSqceKIHbahTXJglSf/MW2/BCSfAySeHPb5z5sDo0QawOs0QlqQv8t57cM45cPjhcPDB4Yaj886DagcRlR+GsCR93ocfwqWXwt57w9Zbh4M2/vM/obY2dmUqM4awJHVYuRImTw5bjFpbYe7ccM5z796xK1OZMoQlKZuFH/wgHLTx9tvw8svwox/BgAGxK1OZc2JDUuVqawt3+V59NQwdCk88AbvvHrsqVRBDWFLlSRJ48MFwpvNmm8H06XDQQbGrUgUyhCVVlqefhrFjobk5nO189NFuNVI0hrCkyvDqq+F2o4aGsNjq1FMh7bIYxeV/gZLKW0NDCNyRI+G446C+Hk4/3QBWUfC/Qknl6YMP4IIL4IADYI89QhhfeCF06xa7MulvDGFJ5eXjj8Oc7+67Q69eMH9+GIauq4tdmfQPDGFJ5aGpCaZNg8GD4S9/gdmz4Xvfg759Y1cmfSFDWFJpa2kJ1wkOGgSvvw7PPw8//Wk4blIqcq6OllSa2tvhnntg4kTYYQd46CHYZ5/YVUkbxRCWVFqSBB57LNzrm8mErveII2JXJeXEEJZUOn7/+xC+f/4zXHstjBrlQRsqac4JSyp+c+bA8ceH/b5nnw1vvgknnGAAq+QZwpKK18KFcNZZ8KUvwWGHwYIFcM45UO0gnsqDISyp+CxbBpdcEhZabbddOGjj0kuhe/fYlUl5ZQhLKh4rVsBVV8Guu4ah5vp6mDw5HLohlSFDWFJ8a9bATTeFvb7vvQd/+AP88IfQv3/syqQu5cSKpHhaW+HOO2HSJNh7b3jqKRgyJHZVUsEYwpIKL0ng/vth/PjQ7d5zT7hoQaowhrBUQZIE2trCe5KEaddUCqqqCrjb57e/DXt9166Fm2+Go45yq5EqliEslbEkCSO+2Wx4T5Iv/tlUKuz8yWTCe95z8ZVXwm1G774LU6bAKad4p68qXipJ1ve/paRSlCQheLPZcMTyxkqnQxhnMnkI4/nzw/nOzz0XVj6fdx7U1HTyoVJ58K+hUplpbQ07fZqbcwtgCJ9rbg7PaW3NsZDFi+Eb34CDDgqLrhoa4IILDGDpUwxhqUwkCaxeDStX5h6+n9feHp63evX6h7I/Y/ly+M53YI89wl2+CxbA2LFQV5efoqQyYghLZSBJwp322WzXPD+bDc9fbxA3NcHUqbDTTiG533wTrrsONtusa4qSyoAhLJW4jgBuaena72lp+YIgXrsWbrsNdtwxBO8LL8B//RdstVXXFiSVAVdHSyWuubnrA7hDS0v4vk02IYxVz5gRFl0NHgwPPxzmfiVtMENYKmEd248KKZtN6PbS81R/6yKorYWf/xwOP7ywRUhlwi1KUolKkrB6OV+LsDZYezvppX+i19uvkTruWA/akDrBEJZK1Jo1YWg4joTa2pQ3C0qd5MIsqQR1HMYRT4psdiO2LUlaJ0NYKkGtrRGGoT+nvb0TB3lIAgxhqSR1pgs+9tjD2H77TcnmoZWO241Lpc8QlkpQrh3ookULeeGFZ0mlUjz66K87XUdbW6cfIVU0Q1gqMR3XEObi7rvvZN99h3PaaWdz9913dLqW9nbnhaXOcHW0VGJaW8OpkLnYZ58dufDCy9hnn2EceeRw5sxZTP/+AzpVT8+e4epDSRvPTlgqMbn+tXnWrOd4//33GDXqFPbccx+2334H7r13erR6JBnCUsnJNfRmzLiDww8/kr59+wEwevTpeRmSNoSl3DkcLZWYlhZYtWrjPtPc3MzOOw+kvb2NuroeAGSzWT75pJHf/e51hgwZmnM9PXp4RbCUK2dypBKTyymRjzzyAFVVVTz//JvU1HT72++fe+4p3H33nUyZcmNB65EUOBwtlZiqqo3/zIwZd3D66eew9dbbMmDAwL+9xoz5Jvfe+ytaO3HqRi71SAocjpZKUGNjcczFptPQu3fsKqTSZScslaBi2RJkFyx1jiEslaBMBiB+KxzqkJQrQ1gqNUlC9WMPkV66JGoZ6XTxdORSqTKEpVLy7LNw8MGkrrySzKqPiNkNZzKujJY6yxCWSsHs2XDMMfD1r8P558Ps2WT23YN0Ok4KptMORUv5YAhLxeydd+CMM+Coo+Df/g3mzQtBXFVFKgV1dXHKqquzC5bywRCWitGSJXDRRTBsGOy8MzQ0wMUX/0P7WV1d+I40k3EuWMoXQ1gqJo2NMH48DBkC3buHznfixHBV0ReorS3csZE1NeH7JOWHISwVg+ZmuOEGGDwYli6F116DG2+Efv3+6Uc7hqW7OohrahyGlvLNEJZiam2Fn/0MBg2CWbPgmWfg5z+HbbfdqMd0BHFXDU1nMgaw1BWc2ZFiaG+H++6DCRNgq63Cr4cN69QjUynYZBPo1g2amsJXdFY6HcLXOWCpa3h2tFRISQJPPAFXXhlSc9o0GDEi7y1mkkA2G165hHHHFiT3AktdyxCWCuXFF0P4/ulPMHUqjB7d5QmXJGHEO5uFtrb1B3I6Hc6C7lj9bPhKXc8QlrpafX1Y8fzSSzBpEpx9drTx3SQJYZwk4ZVKhVdVlaErxeDCLKmrLFoE554Lhx4KBx4Y9vqOGRN1gjWVCl9fUxPmjmtq7HqlmAxhKd8+/BAuuwz22gu23BIWLIDLL3eDraR/YAhL+bJyJVxzTTjhau1aeOstmDIF+vSJXZmkImUIS52VzcItt4S9vgsWhLnfW2+FgQNjVyapyLn7T8pVWxv8z//A1VeHYyYffxyGDo1dlaQSYghLGytJ4Ne/Diue+/SBu+6CQw6JXZWkEmQISxvjmWdg7NhwJNV114U7fl1aLClHhrC0IV57DcaNg/nz4bvfhVNPDZtrJakTXJglrc/bb8Npp8FXvgIjR4arBc84wwCWlBeGsLQuH3wA//EfMHx4WHTV0AAXXRROuJCkPDGEpU/7+ONwvvPuu0OPHmH4efz48GtJyjNDWAJYvRquvx4GD4aPPoLXX4cbboC+fWNXJqmMGcKqbC0t8JOfhIM2XnkFnn0WfvYz2Gab2JVJqgCujlZlam+HmTNhwgTYbjt44AHYb7/YVUmqMIawKkuSwG9+E+Z9q6rg9tthxIjYVUmqUIawKsesWSF8lyyBqVPhxBM9aENSVM4Jq/y99RaMGgWnnAJnnglz5sDo0QawpOgMYZWv996Ds8+Gww+Hf/3XcMPRueeGW+wlqQgYwio/f/4zfPvbsPfesO224aCNyy6D7t1jVyZJn2EIq3ysWAGTJsEuu4TVz3PnwjXXQO/esSuTpHUyhFX61qyBH/wg7PV9992w3/eWW2DAgNiVSdJ6OTmm0tXWFu7yvfpqGDoUnnwyHDcpSSXCEFbpSRJ48MFwpvNmm8H06XDQQbGrkqSNZgirtDz9NIwdC83N4Wzno492q5GkkmUIqzS8+iqMGxdWOl9zTbjjN+2SBkmlzT/FVNwaGuDUU2HkSDjuOKivhzPOMIAllQX/JFNx+uADuOACOPDAsOiqoQEuvBC6dYtdmSTljSGs4vLxx2HOd/fdw/7e+fPDec91dbErk6S8M4RVHJqaYNo0GDw4BPEbb8D114fVz5JUpgxhxdXSEq4THDQIXn8dnn8efvIT2Gqr2JVJUpdzdbTiaG+He+6BiRNhhx3goYdgn31iVyVJBWUIq7CSBB57LMzzZjLw05/CEUfErkqSojCEVTi//30I3w8/hKlTwx2/HrQhqYI5J6yuN2cOHH982O979tlh0dUJJxjAkiqeIayus3AhnHUWfOlLcNhhsGABnHMOVDsAI0lgCKsrLFsGl1wSFlptt104aOPSS6F799iVSVJRMYSVPytWwFVXwa67hqHm+nqYPBl69YpdmSQVJUNYnbdmDdx0U9jru2gR/OEP8MMfQv/+sSuTpKLm5Jxy19oKd94JkybB3nvDU0/BkCGxq5KkkmEIa+MlCdx/P4wfH7rde+6BAw6IXZUklRxDWBvnt78Ne33XroWbb4ajjnKrkSTlyBDWhnnlFRg3Dt59F6ZMgVNO8U5fSeok/xTV+s2fHwL3+OPhxBPDiudTTzWAJSkP/JNU67Z4MXzjG3DwwWHRVUMDXHAB1NTErkySyoYhrM9avhy+8x0YOhT69QunXI0dC5tsErsySSo7hrCCpqZwqcJOO8GqVfDmmzBtGmy6aezKJKlsGcKVbu1auO022HHHcNHCCy/A7bfDllvGrkySyp6roytVezvMmAETJ4bu95FHYK+9YlclSRXFEK40SRICd9y4MM/7i1+EG44kSQVnCFeS554LB2385S9w7bVw3HEetCFJERnCleCNN8IRk2++GW41+trXoKoqdlWSVPFcmFXO3n0XzjwTjjwSRowIB2+cdZYBLElFwhAuR8uWwcUXw/77h+sFGxrgW9+CTCZ2ZZKkTzGEy8knn8CECbDrruFkq/p6uOoq6NkzdmWSpHUwhMtBczN8//uh6/3gA3j1VbjpJth889iVSZLWw4VZpay1Ff77v8Niq/32g6efDl2wJKkkGMKlKEngvvvC0PMWW8DMmTB8eOyqJEkbyRAuNU8+Gfb6trXBLbfAl7/sXl9JKlGG8AZIkpB5SRJeqVR4VVUVMP9efjmE76JFMGUKnHSSd/pKUokzhNchScJ0azYb3pPki382lYLq6rD7p7q6C0J53rww7DxrVljpfM453ukrSWXCVupTkgTWrIEVK8Jtfi0t6w/gjs+0tISfX7EifP6ffWaDvP8+jBkDhxwS9vsuWAD//u8GsCSVEUP4r1pbQ4g2N4cLhnLR3h4+v2JFeF5Oli+Hyy+HPfeEAQPCQRtXXBEuW5AklZWKD+EkgdWrYeXK3MP389rbw/NWr15PV9zY+NkvXLUqzPXutFNI8jlzYOpU6NMnP0VJkopORYdwkkBTU5j77QrZbHj+PwRxY2MI20mTYO1auPXWcNBGfT28+CLcdlvYeiRJKmupJMnLDGbJ6Qjglpau/66aGqir++uirSSBUaPg0UfDbwwcCEOGhK53zz27vhhJUtGo2NXRzc2FCWAI39Pc/Ndp3TvvhMcfD7+ZSsHee8P99xemEElSUanITri1NczZFlrPD9+heudBoRvOZMI+35YWWLoU+vYtfEGSpKgqrhPuGIaOoanvv9Dr/AtI7bYr1NZCt27Qowf06hWnIElSVBXXCa9ZE4aGY6mthe7d432/JKl4VNTq6CTpupXQGyqbzdNhHpKkkldRIdzamr+9wLlqb+/EQR6SpLJSUSGcaxc8dOh2bLllLdts04Ptt9+Ur371GBYvfr/gdUiSyktFhXBnOtDp0x/i/fdXUV+/hM03H8DYsRfn/Ky2ttzrkCSVj4oJ4Y5rCDure/fuHH/8ScyfPzfnZ7S3Oy8sSaqgEM5X97l69Wruv/8e9t13eFHUI0kqXRWzT7izneeZZ46iqqqapqZVbL55f+699/Go9UiSSl/FdMKdDb277nqAhQsbWbo0y/XX38rIkYeybNnSaPVIkkpfxYRwKpWf51RVVXHssSdSVVXFrFnPRa9HklS6KmY4Ol+hlyQJjz76axobP2bw4F2i1yNJKl0VE8JVVZ37/OmnH0tVVRWpVIqtt/4XfvzjO9hll92i1SNJKn0VdXZ0Y2NxzMWm09C7d+wqJEmxVcycMEB1kfT9dsGSJKiwEM5kYlcQFEsdkqS4KiqEq6vDUHBM6XTxdOSSpLgqKoRTqfhdaCbjymhJUlBRIQwhBGN1w+l0/L8ESJKKR8WFcCoFdXVxvruuzi5YkvR3FRfCEOZkC92RZjLOBUuSPqsiQxigthZqagrzXTU14fskSfq0ig3hjmHprg7imhqHoSVJ61ZRJ2atS5JAczNks/l/diYTOmADWJK0LhUfwh1aW6GpCdrbO/+sdDp0v84BS5LWxxD+lCQJHXE2m1sYd2xBci+wJGlDGMLrkCShM85moa1t/YGcToezoDtWPxu+kqQNZQhvgCQJYZwk4ZVKhVdVlaErScqdISxJUiQVu0VJkqTYDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRIDGFJkiIxhCVJisQQliQpEkNYkqRI/h/RYnZR2pGnygAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nx.draw_spring(g, with_labels=True, node_size=1200, node_color='#eeeeff', edge_color='red')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3:**\n",
    "\n",
    "Write functions `get_suffix()` and `get_prefix()` which just return the `k-1`-length strings which are, respectively the suffix and prefix of the supplied k-mer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_prefix(kmer):\n",
    "    '''Return the prefix of the string (all but the last character).'''\n",
    "    return kmer[:-1]\n",
    "\n",
    "def get_suffix(kmer):\n",
    "    '''Return the suffix of the string (all but the first character)'''\n",
    "    return kmer[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'GGTA'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_suffix('AGGTA')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AGGT'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_prefix('AGGTA')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a set of reads and a value k, build a directed graph, using networkx, where nodes are the prefixes/suffixes of kmers and an edge exists for every kmer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_graph(reads, k):\n",
    "    '''\n",
    "    Given a set of reads and a value k, return the networkx de Bruijn graph object.\n",
    "    '''\n",
    "    kmers = get_kmers(reads, k)\n",
    "    graph = nx.DiGraph()\n",
    "    for kmer in kmers:\n",
    "        graph.add_edge(get_prefix(kmer),get_suffix(kmer))\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "yoda_graph = build_graph(yoda_reads, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAecAAAFCCAYAAADL3BUJAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl4U1X+P/D3vUmahrZQdmhpKYgCglQW2URkRh1BRUVWEWVRAX8oKI7AiDrgwoAziuCCCioo4oIoDiIyynwVmUEBkcXCsJcCBQW1tg1tSJr7++N4u9ElSXPvPWner+fJU9omuaehzfuec8/5HEXTNA1EREQkDdXqBhAREVFZDGciIiLJMJyJiIgkw3AmIiKSDMOZiIhIMgxnIiIiyTCciYiIJMNwJiIikgzDmYiISDIMZyIiIskwnImIiCTDcCYiIpIMw5mIiEgyDGciIiLJMJyJiIgkw3AmIiKSjN3qBhARRRJNA4qKxEdNAxRF3Gw28ZEoHBjORERV0DTA5wM8HvFR0yq/r6IAdjvgdIqPDGsKlaJpVf2qERFFJ00TgezxAH5/8I9XVRHSTidDmoLHcCYiKsfnA9zu0EK5PFUF4uJET5ooUAxnIqLfaRpQUCB6y+HmdAIuF3vRFBiGMxERRDC73YDXa9wxHA7Ri2ZAU3W4lIqIop4ZwQyI53e7q55URgQwnImIUFBgfDDrvF5xPKKqMJyJKKrpy6TMpC/LIqoMw5mIopY+nG0FDm9TVRjORBS1Ql3DHA5+v/k9doocDGciikp6kREreTzsPVPFGM5EFJV8Put6zTq/n9eeqWIMZyKKSkb1mhs0UHD48EHL20GRjeFMRFFJlh5rUZHVLSAZMZyJKOro2z1WJT09Dc8//w/06dMJLVvWw7hxw1FYWAgAWLZsMbp2bYPWrRtg5MgbcfJkNgDg+uv7AgD69k1HSko8PvzwvWrb4vfzujOdj+U7iSjq+HxAXl7V90lPT0Pjxk3w1lurERsbi/79L8fEiVNwwQUXYdy4YVi16l9o164DHnvsz/jhh51Yu3YjADGsvW3bAbRu3Sbg9iQkcGMMKou/DkQUdQLtkowfPxnNmycBAPr3H4jdu3dg+/atuO22cUhP7wIAePTRv6F16/rIyspEamqaoe2h6MFhbSKKOoGGYZMmzYr/7XLVgdudj1OnspGS0rL46/Hx8WjQoCGys08Y3h6KHgxnIoo6NdkVqlmzJBw7drT4c7fbjV9++RlJScmWtIdqJ4YzEUWdmoThkCEjsWLFG9i9ewc8Hg+eeOJhdO3ao3hIu0mTpsjMPGxae6h2YjgTUdSx2UJ/7JVXXoWHH34Co0cPRvv2zZGZeQhLlrxb/P3p02dh0qTRSEtLxEcfvW94e6h24mxtIopKOTlyXOtVVaBePatbQbJhz5mIopIsS5fYa6aKMJyJKCo5nVa3QJClHSQXhjMRRSW7XQwpW0lV5enBk1wYzkQUlRTF+l6r08mZ2lQxhjMRRS2n07res6paf3JA8mI4E1HUUhQgLs6aY8fFsddMlWM4E1FUs9vN78E6nbzWTFVjOBNR1HO5AIfDnGM5HOJ4RFVhOBNR1NOHtx12DYBxlUkcDg5nU2AYzkREXi+U119DXPMEOP/7f4YcwulkMFPgeNWDiKLXuXPA0qXAo48COTlQvF7UsXsRkwC43YDfX/NDqKoIZV5jpmCwtjYRRa/nnwcmTy753OEATp4EGjaEpgEej7iFEtL6UimuZaZQMJyJKHoVFQH33w+88IL4vEED4Oefy9xF0wCfT4R0UVHVQa2qola2PhuboUyh4kALEUUFTRPhqmnipiiAogG2gwehjBgBfPIJ0KnTeY9TFNGh1mdzV/g8ighlhjGFC3vORFQrle7x+nyVbA/pKQRsdigOG+zeQjjdP8PesgVDlizHcCaiWoXXiqk2YDgTUa3h83GWNdUODGciiniaBhQUiN5yuDmdoqIXe9FkJoYzEUU0TRO9Za/XuGOwsheZjRXCiChimRHMgHh+t7uSSWVEBmA4E1HEKigwPph1Xq84HpEZGM5EFJH0ZVJm0pdlERmN4UxEEUcfzrYCh7fJDFwkQETSK1+Vy+sNz3KpUPj9ogcdG2vN8Sk6MJyJSDoBVfeykMfDIiVkLIYzEUmjptW9zOL3i5MGvd42UbgxnIlICuGs7mUGj4fhTMZhOBORpYys7mWkoiKrW0C1GcOZiCxjVhERI/j9JVtGEoUbl1IRkSUiOZh17D2TURjORGQJI6t7LVgwDx06JCM1NQHdu7fFV19tqPS+c+fOwtixw3DPPXcgNTUBvXp1wPffbwvoOLLNIqfag+FMRKYzsrrXgQP7sHjxC/jii63IysrDBx+sR2pqWpWP+eyzf+KWW0bgyJEcDBhwI6ZNuzegYzGcySgMZyIyldHVvWw2G86d82Dfvj3wer1ITU1Dq1YXVPmYnj374JprroPNZsOwYbcjI2NnQMfi9WYyCsOZiExl9Brm1q3bYM6c5zBv3ixcdFET3HnnCJw8mV3lY5o0aVb87zp16qCwsBC+AIpoM5zJKAxnIjKNXmTEaEOGjMS6dZuwc+dRKIqC2bOnG3Icm82QpyViOBOReXw+44uMHDiwDxs3/hsejwexsbGIjXXBZkCKqip7zmQcrnMmItOY0Ws+d86Dxx+fgf3798Jud6B7996YP//VsB+HvWYykqJpnG9IRObIyak9M5xdrpLes6KIsGZPmsKFPWciMoW+3WNtUVBw/tcUBbDbxY5VdjvDmkLHa85EZIqaVNNKT0/D88//A336dELLlvUwbtxwFBYWFn9/2bLF6Nq1DVq3boCRI288b3b20KEDkJISf97t2WfnhN6oCuh7TefnA7m5QGFh7TohIfNwWJuITKGHVijS09PQuHETvPXWasTGxqJ//8sxceIUjB07ERs3/hvjxg3DqlX/Qrt2HfDYY3/GDz/sxNq1G8P7A4RIVYG4ONGTJgoUf12IyBQ17QaMHz8ZzZsnAQD69x+I3bt3AABWrnwbt902DunpXQAAjz76N7RuXR9ZWZnVVgYzg98P5OWJoW6Xi0PdFBgOaxORKWoaSqULhbhcdeB2i274qVPZSElpWfy9+Ph4NGjQENnZJ2p2wDDzeERlNI5VUiAYzkRkCqN6jM2aJeHYsaPFn7vdbvzyy89ISko25oA14PUyoCkwDGciMoVR64KHDBmJFSvewO7dO+DxePDEEw+ja9ceUgxpV8TrrXimN1FpDGciMoW+HjjcrrzyKjz88BMYPXow2rdvjszMQ1iy5N3wHyiMPB5RLY2oMpytTUSmyc83bg/nSKOqQN26nCBGFWPPmYhM43Ra3QJ5+P3mlDOlyMSlVERkGrtd9Bgr2vzi+PEs9Op1cYWP27x5D1q0SDW4debzeMQJC3vPVB6HtYnIVIWF1k6IiokBHA5RsaxUkTHLxMeL9hCVxmFtIjKV0yl6z1ZQVaBOHRHQNSknGk4c2qaKMJyJyFSKIspZWiEurmQIWZbZ0rKcJJBcGM5EZDp95yYz6TtFAaHtkOUzKM39fhYlofMxnInIEi6XeddaHQ5xPF2gvdX09DQsWDAPffp0QosWcViwYB46dEhGamoCundvi6++2hCW9rH3TOVxtjYRWUIf3na7jV377HCUHc4Gguuprlr1Dt59dy1ycn7BiBE34IsvtqJ58yRkZWWiKEypyp4zlcdwJiLL6AFdUGDMxKjKdoIKJgzHj5+MFi1ScO6cB+fOebBv3x40atQ4rOVBGc5UHoe1ichSiiJmUCckhG8Wt6qK56tTp+I1xMGsK05OTgEAtG7dBnPmPId582bhooua4M47R+DkyeywtJfrnKk8hjMRScFuF+UsXa7QQ1pVxePr1i2Z/FWRYMJQKXXnIUNGYt26Tdi58ygURcHs2dNDa2gN2kPRgcPaRCQNRQFiY8VwtM8nhrqLiiquKKZTVbHjlT4bO5CgC2WHrAMH9uHkyRPo0eNyxMbGIjbWBU2romFBMGrHLopcDGciko6iiIlc+mxuTRMhrS+B0ne4stlC63Xqjw/mWu+5cx48/vgM7N+/F3a7A92798b8+a8Gf/ByVLVmPedwvzYkB5bvJKKoJMsOWQ6HKOEZKE0rGVXw+ao+wVCUkjXlgY4qkBzYcyaiqOR0yhHOgRZj0TQRyB5P1cP85R/j9YqbqopjcaONyMAJYUQUlfQdsmpq6NABSEmJP+/27LNzqn2sqlY9cU3n8wG5uWLJWaDBXJ7fLx6fmytP6VKqHIe1iShqWb1DlsslJsBVRtPMXwNOcuCwNhFFLaczuGHi8NGg/ngKzhfmAK3SgIYNxa1fP7FAGyKYjayepv/c5aunkRzYcyaiqObzAXl55h834baBsK/7RIxtx8YCZ88Cq1cDN91keDCXVlF5U7Iew5mIot7Zs+buq+x0AnV+PAJcfLEYWweAli2Bw4cBVbWmPXXMOx5VjxPCiCjqWbJDVqtWwOzZIhVjYsRi5UGD4Ms6YWowAyXLskgeDGciinr6BhxGB/R5Q8hTpwJpacBttwEHD0Lr1RvunGoWLxvE7eYGHDLhsDYR0e8smR3tdhdXCSksBArO+gHFmn5TdbPHyTwMZyKicnw+kZnhmMWtqqK3XN16Zk0Ta5DNnzleQlXFpiGcHGY9LqUiIipH3yEr2IpcpQVbkcvnszaYAXF8n8+86+9UOYYzEVEFzNohS2f2JLDKeDwMZxkwnImIqmD0Dlk6WWZLFxVZ3QICGM5EREHRd3oKJz3ow8nn88EeQkP9/pKTDrIOl1IREVksmN7qyZPZuOOOwbjwwsa49NJWeOWVhQCAuXNnYfToIZgwYRRSU+tixYql+O67LfjjH7shNbUu2rZtipkzp4a9PWQM9pyJiCwWaK/Z7/dj5MiBGDDgJixZ8g6ys49j0KCr0aZNWwDAunUf4403VmLRojfh8Xhw001/xIQJUzB8+O3Iz8/H3r0/hLU9ZBz2nImILBZoGG7fvhVnzpzGtGmPISYmBmlprXHHHXfjww/fBQBcdlkvXH/9zVBVFS6XCw6HA4cPH8TPP59BfHw8LrusZ1jbQ8ZhOBMRWSzQ67vHjh3FqVPZSEtLLL7Nnz8Hp0//CABITk4pc/+FC1/DoUP70aNHO1x11WVYv/6TsLaHjMNhbSIiiwUahsnJKWjZshW2bTtw3vfmzp0FpdwTXXDBhViy5B34/X6sWfMhxowZgoMHf0ZcXFxY2kPGYc+ZiMhiNltg9+vatTsSEupiwYJ5KCgoQFFREfbs+QHbt2+t8P7vv78cZ86chqqqqFcv8fdjVX+wQNtDxmE4ExFZTF8rXR2bzYYVK9Zg9+4d6Ny5Fdq0aYQpU+5Cbu5vFd5/w4bP0Lt3B6SkxOMvf5mCJUveRWw1xbNVlT1nGbC2NhGRBPLzAa/X6laIYivx8Va3gthzJiKSgNNpdQsEWdoR7RjOREQSsNvFkLKVVDX81c8oNAxnIiIJKIr1vdZAd9Ai4zGciYgk4XRa13vWt7gkOTCciYgkoShANUuQDRMXx16zTBjOREQSsdvN78Hq+0+TPBjORESScblK9o82msMhjkdyYTgTEUlGH942OqAdDg5ny4pFSIiIJKVpQEEB4PGE/7mdTtFjZjDLieFMRCQ5nw9wuwG/v+bPpXo9iKsfA7uDqSwzDmsTEUnObgfq1hU93VCXWqmqeHzdVg1g73wJkJUV3kZSWDGciYgigKIAsbEipOPjxfXi6oJaVUtqZdetKx6vxMQAGRlA+/bAiy+GpztOYcdwJiKKIIpSErj16gGJiUBCAhCfcxxxj09DfJyGhATx9Xr1SoK8+Npyo0bi49mzwP33A+PGWfazUOUYzkREEUxRxLC3Y9oDiHnu73D8379gt1cx0SsxseTfF14ITJliSjspOAxnIqJId+IEsGaN+PeDD4pp3pVp3hyoXx/o3x/o3Rvo3NmcNlJQWBOGiCjSzZ4NFBWJf2dmAp99BgwYUPF9X39dzAzzeoF27YDt24EuXUxrKgWGS6mIiCKZ2y16wg4HUFgoPnbrBmzaVP1jFy8Gli0Dvv6aC54lw3AmIopgml9D0fc7of10BtrbK6BMmQylfiJsF6RVn7dFRcBllwHTpgEjRpjSXgoMw5mIKIJomihK4vGIj8Xv4P4i0YtOqFt8X32ymL6xRYVhvWkTMHIksHevdVti0XkYzkREEUDTRCB7PKEtTdb3a3Y6KwjpW28VM7cffzwsbaWaYzgTEUkurOU7VdFBLrNF5LFjwKWXAt99B6Sl1fwgVGMMZyIiSZm68cUTTwC7dgErV4b/YBQ0hjMRkYQ0TfSWvV7jjlFmy8iCAlHSc+lSoF8/4w5KAWEREiIiyZgRzIB4frf790llLhfwj3+IimE+n7EHpmoxnImIJFNQYHww67xecTwAwODBQIMGYv0zWYrD2kREEvH5gLw884+bkPD7JLFdu4BrrhFLqxo0OO9+miaWR2uauCmKuNlsrGMSTgxnIiJJaBqQm2vNLo6qKraVVBQA/+//iaReuLDyddUVCGhdNQWE4UxEJInCwlJDzBZwucSezzhzBlr6pfBs2gJPg6Twr6umajGciYgkYGWvWaf3nouKAHf2b/A7YoBYV42f87x11VQthjMRkQS8XiA/3+pWiOVVYjKaBiB8Xd7z1lVTlThbm4hIAkYUGglFySzx8Kaox1Nq2RZVi+FMRCQBs5YW+yxcw1xmXTVVieFMRGQxfVlSddLT0/D88/9Anz6d0LJlPYwbNxyFhYUAgPXrP0HfvpciLS0R117bGxkZu8o8bsGCeejTpxNatIizPKCtnPQWKRjOREQWKyoK/L4ff/w+Vq78DDt2HEFGxi68885S7Ny5HffdNw7PPvsKDh36GWPGTMDIkTfCU2qsfNWqd/Duu2tx5EgO7BbPztKXZVHlGM5ERBYLZph3/PjJaN48CfXrN0D//gOxe/cOvPnmYowePQHduvWAzWbDrbeOhtPpxLZt35R5XIsWKXC5ajb7Olw4vF01Tm4nIrJYMCHVpEmz4n+7XHVw6lQ2fv31F7z77jIsXvx88fe83nM4dSq7+PPk5JSwtDVc/H7Rg46NtbolcmI4ExFZrKbLi5KTUzB16kw8+ODMKo4h3xomj4dFSirDYW0iIovVNJzuuONuvPHGy9i27Vtomga3241//Wst8qwo0h0Ev5/XnivDcCYispjNVrPHd+7cDc89txjTp9+LVq3qo1u3NlixYmlY2paenoYvv/wiLM9VEVnWd8uGFcKIiCSQkyPnBCmxDGsJ+vW7OqjHaZoGTdOgqlX3AVUVqFevJi2sndhzJiKSgIy1pydOvB3Hj2dh5MiBSEmJx8KFT2Pr1m9w7bW9kZaWiCuuSMemTV8W33/gwH548smZ6N//ciQn10Fm5uFqj+H3y3lSYjX2nImIJCBLbe3ySvecs7NP4IorOuHll9/CVVf1x1dfbcBdd43At9/+D40aNcbAgf2QmXkY77+/Dhde2BaapsHhcFR7jOK9pKkYe85ERBKw28UQr8xWrlyOa665Dtdccx1UVcUf/nANLr20Gz7//NPi+9x66xi0b98Bdrs9oGAG2HOuCM9ViIgkoChiWZHMpS2PHTuKjz9eic8+W1P8NZ/Piyuu+EPx56Gsp2Y4n4/hTEQkCadTzF62ck/n8kqvj05OTsGwYbdjwYLFAd0/8GOE1LRaTfJBFCKi6KEoQFyc1a0oq3HjpsUTu4YOHYX169dgw4b1KCoqQmFhITZt+hInThyv0TEYzudjOBMRScRuFz1oWTzwwF/wzDNPIi0tER999B6WL/8Y8+fPwYUXNsYll6Tg+ef/Dk2rWVe/puu8ayPO1iYikoymiY0hvF6rW2I8rnOuGHvORESS0Ye3A5zsHNHYa64Yw5mISEJ6QBs1xC1L8Ms0hC8ThjMRkaQUBahTRxTpCNcaaFUVzxcXZ/26alVl8ZHKMJyJiCRntwN1t22Aa8ZkqEWhXYhWVcDlAurWFc+nr6u2EreLrBwnhBERyUzTgPnzgRkzAJ8P2g8/wHfhxfB4gKKiqtdEq6q4put0lgRy+afOzbVmXbWqihMFhnPFOKBARCSrwkLgjjuAtWvF1O06daAUFsLhKLlmrGkipDVN3BRF3Gy26oNPv65t+rbPfj/ixg6F0qkDcNllQKdOQGoqk7oU9pyJiGS1YwfQs6fo2nq9Ys3Rp58CvXuH9TBnz5q7r7JTO4s6TesBPh8QHy/OLmJigOPHxechqsmJimx4zZmISFaXXgpkZwPNmokLxnl5ojcdZi6XebO3HQ7AVb8O8Ne/ikDOzxchfdNNQQezppXs5pWTI255eeJzt1t8zMsr+V5+vrh/JHRJGc5ERDLbu1ck2k8/AcuWAV26hP0QZq2rdjjEcRQFwP33l8xIUxSx40eA4+uaJs5RcnMDD9zSQZ6bKx4vc0gznImIZDZvHvDnP4te5ahRQGKiIYcxel2101kqmAHx88yYIb6xZYv4ubp2Bb7/vsrn8flEuBYUhD6Rze8Xj8/NFc8nI15zJiKSVUYGcNVVwJEjYuzZJD6fGBYOxyxuVRWhXOF6Zq8XOHoUaNNGfP7OO8DkycDs2cA995S5UKxpIlCNuDbudIqXV6br0gxnIiJZjR0rgmvmTNMPrWkiCEPdwlJVRegFvZb5wAFg2DDxcy9ZAtSrZ0qt8TJD7hJgOBMRyej4cbHE6NAhoH59y5qhaaInHY511QErLAQefBD47DNo770Hd7tupmwCIlNAM5yJiEwU8HKfBx8Ud3j2WcvaWhFTlyt98AHOHj4Fz5gJpk0ndzpFyVSrMZyJiAxUuufp81U9Q1hRft/P2ZsH+wUtoezcCaSkmNdYyfh8QF6uH1DMnbuckGB9zW+Gcw3UpgXvRBReNbpme84DNT8PzuRGUVt/OtpLizKcgxDSGXBNr70QUcQxbbZzLVZYKGZnW8XlAmJjrTs+wzkAls1aJKKIEm3LfYxiZa9ZZ3XvmeFcDZ4BE1EgonG5j1H0Sl5Wi483r6xpeawQVglNE8Xg8/LCd/bm94vnO3tW7rJxRBQcM4IZEM/vdtf+949ARx7S09Pw5ZdfAACysjLRoIECXxhLfpm5GUh5DOcK6H9oRv3HeDzR8QdGFC0KCowPZp3Xa+21WDPIUlKzqMi6YzOcy+EZMBEFQ58kaiZ9UmptpK9+qc7Eibfj+PEsjBw5ECkp8ejV62IAQKtWiUhJiceWLZsBAMuXv44ePdqjVav6GDz4Whw7djTgtvj91r1HM5zL4RkwEQVKP5m3Qm09uQ+0t/ryy2+hRYtUrFixBseO5WPz5j0AgCNHcnDsWD66d++FtWtXY/78OXjzzQ9x4MBp9Op1Be6661ZD2hNuDOdSeAZMRMEIdQVHOPj91l4TNUo4TziWLn0F99//F7Rt2x52ux1Tpz6MH37YEVTvmT1ni/EMmIiCoS+xtJLHU/veO8L58xw7dhQPPzwFaWmJSEtLROvWDaBpGrKzT1jSnmBwUc/vZDgDtnLBu45Vz4gC4/NZuw4XEMf3+axb7mOEYN5nlFJ3Vip4YHJyCh58cCaGDr3NlPaEE3vOiO4zYE0rWVOYkyNueXnic7dbfMzLK/lefr64f207WycKltXvGTpZ2hEuwYRh48ZNkZl5GADQsGFjqKpa/DkAjB07EfPn/w1792YAAHJzf8Pq1SsNa084MZxR8zPgZ5+dg8mT76pRG/QzYLNomiiPl5sbeOCWDvLcXPF4hjRFq+r+XkuvwTWSlct9jGCzBX7fBx74C5555kmkpSXitddewtSpMzFgwOVIS0vE1q3f4IYbBmHKlOm4664RSE2ti969O+KLL9YZ1p5wYoUwlIST1RwOUZHGaKx6RlQzmiZGkqqSnp6GBQuWoF+/qw1vT2Ji7brslJMjx4m/qgL16ll0bGsOKxdZZksbfQbMqmdE4VHd32r5NbgLFz6NBg0UvPPOMlxySSratGmEZ555qvj+fr8fzz03F126XIALLmiIsWOH4ddffwlbeyKNLCf7VvWaAYZzwAvedQsWzEOHDslITU1A9+5t8dVXGzB37ixMmDAKADBt2r1ISYkvvjVubMfcubMCem4jF7yz6hlR+FT3e15+De7NNw8DAHzzzSZs2bIPq1dvwN///jj27dsLAHjllYVYu3Y11qz5Cnv2ZCMxsT4eemhS2NoTaZxOq1sgWNmOqA/nYM44DxzYh8WLX8AXX2xFVlYePvhgPVJT08rc5+mnX8CxY/k4diwfn366CYmJ9XHddTcZ0p5AseoZUXiF+js+bdpf4XK50LFjOjp2TMcPP+wEINbjPvLIU0hObgGn04np02fhn//8IOA60bXtb85uF0PKVlJVa3vwkgweWCeYX2qbzYZz5zzYt28PGjVqfF4wl3bmzGmMGnUz5s59Hp06dTakPYGyoupZnTrmHI/ICqFe323atFnxv12uOnC7xdZLx48fxe23D4JaKpFsNht++ulHJCUlG9YeWSmK6LVaWUHR6i1+o77nHEwYtm7dBnPmPId582bhooua4M47R+Dkyezz7uf1ejFmzBAMGTISgwePMKw9gWDVM6LwC+RNu6J1t5VJTk7B+++vQ2ZmTvHt5MnCgII50PZEGqfTut6zqlo/tB714RzsL/WQISOxbt0m7Nx5FIqiYPbs6efdZ/r0+xAfn4CZM580vD1VYdUzImMEMlGo9Brc6owZMxFPPTWzuKzkmTOn8emnH4e1PZFGUcRKECvIsGc2wzmI/4ADB/Zh48Z/w+PxIDY2FrGxLtjK/VUsXfoK/vOfr/DqqyvKDFEFxOeF8uOpsKWaDFXPiGojvXJeVUqvwf344w+qvO/EiVPQv/+NGDz4T0hNTcCf/tQT3333bUBtUVXrg8Qodrv5PVinU47Z4lG/zjmQ9Yq6jIxdmDLlLuzfvxd2uwPdu/fG/PmvYtmyV3HkyEG88spyDBzYD1u3boajVD29Bx54GFOnPlz9AYp8SLzsIii/5QCXXgp07iw+Xnop0K5dxTX6jh4FnnoKePppsdix1M+Vm2tteUFVBerWrb1vHBTdoq0+glXMmtAKiNdShl4zwHAGIOGC9x9/BHbsKLl9/z2QlQVcfHEl7qg+AAAZx0lEQVRJWHfuDHTqBLz3HnDPPUDjxsDateLrKKnkVZ1evTrg739/EX369DPkZ4qPr111f4l0gf6NGS0a/sbMCGiZghlgOAOIkDNgtxvYtatsYGdkiItNeXniPjExwKxZwIwZyHcr8v9MRBGMo1Pm0jQxe9uIy2VOJ+ByyfU6MpwRwWfAPh/Qvj1w8KD4XFXFO8Xq1ci58ia5RgMMwl20yEqFhdYu93G55NjNzkzRUn446ieEARG84N1uB86cEYuKb7gBeOMN4NQpaDcGHsx6cf60tMTiqmYtWsShQQMFWVmZAID16z9B376XIi0tEdde2xsZGbsCbmK4q55xFy2SSbQv97GC3S5GC1yu0F97VRWPr1tXzmAGWIQEQIQveM/IAJo2LbOWoiiENcaZmSWz4p544mF8880mNG+ejJ07t+O++8ZhxYo16Ny5G95/fzlGjrwRW7bsgzPAd4aiopr/AejbegYzA10Pcq+35I3M6sICVEv4/UBWFpTPP0fczUOQZ69vehNkuj5qNkURIwZOZ0kth6JzPvj9SqXrylRVfEufjS37a8ee8+8i9gw4Kem8X8aa9BI//PA9fPDBCixbtgoOhwNvvrkYo0dPQLduPWCz2XDrraPhdDqxbds3AT9nTXutPp+4tldQEPpQlt8vHp+bywIpFKKiImDMGOCii0S368ILgfHjYd+6OWqX+1hNUX6f1xKnod7AK5GYEo+EohzEx4uTl/h4ICFBLGSpV6/k0qHswQwwnIvVpgXvoYbhrl3fY/r0e/HWWx+hUaPGAIBjx47ipZeeQVpaYvHtxIljOHXq/Mpo4W4Pd9EiqagqsHs3cOgQcO6cOMvr3Ru47jq4XObNmHY4xLkBlfL668C2bVB8Ptg/WQ2HQ8yPdTgio5dcEYZzKbVlwXsov4hnzpzG7bcPwrx5L5SpBZ6cnIKpU2eWKSt44sRZDB58q6Ht4S5aJB1FASZOLPmlcbmAl14q/lZcnPEBLdtyHyns3w9MnlxywrR8udUtCguGczm14Qw4lD/c0aMHY+jQ23DLLcPLfP2OO+7GG2+8jG3bvoWmaXC73fjXv9YiT1++ZUB7uIsWSaegAJg0Cfjb34A5c8Qv9R//CKSnF99FD2ijTvCdTgZzhWbPFn/M+uW9jRvF0FiE41WLcvQ/sEhe8B5snd2srExs3vw1du78Dq+8sqD465s370Hnzt3w3HOLMX36vTh06ABcLhd69OiDXr36GtYe7qJFUsnIAEaMADp0EPUF9IuX119/3l0VRfwuxcREx3IfKSxZAkydClxzDTB4MPDTT2KNW4T/UXOdcyUifcG7NFXPFA31EgP/QX2+kpoqZkpI4JsflaNpwOLFwMyZwLx5wNixQf3RhrLCoDSuMAhCbi7QvLl487B6XWyY8O2oEpF+Bmy3S1D1zO+H7dPVwJb/A4YMAfr0KelGDx0K9O0L3Hdf8d2t3kUrWiotRTpTCs/8+itw992iwM/XX4va9kGqcLlPUdXvJZG23Ecae/eK/6NaEswAw7la+oL3SDsDdjolCGdVhbN3VyBrL3D//cDJk8DNNwNXXw3885+iFrjPBzzwAAA5dtGKtmpLkUDTSsLN56t6REhRSiZ2hhxumzYBt90GDBokJhfV8JdCX+6jz2VhVTsD7Nkj9h6oRTisHYTSbxKynwFLWff30CFg1Soxw/Wo2LcWTicwaxa06TPkay9ZyvRh4aIiscPbSy+J65g33BD8QclwFZ7cvPA8bN5CKNMesrp5YcNwrgHZz4Clrft7+eXAf/9b5kveZSuQPzDw5VlGiYYdfiKB6fWTjx8XvWWbTfSWk5JqfmAKi4BGTs66gVgXFJta85ETSTCcazEre89V9kIvv1ysSbzkEnFr0gT51w2BF9YXCuYuWtayZCLm6tXAhAni0su0acEvLyBDRPuEOoZzLRcps5+lmV1u8C5aVDnT9+wtKAD+/Gdg3TpgxQqgZ0/jDkxBiZadp6pSe6a2UYUioeqZfllABuHeRYsCY3rhmYwMoHt3savb9u0MZkmwZG8J9pyjgFlvfEBoxVWs6t1XhmuezXf2rHGlWs/j88L5+iLUaRwf9NplMo7pIyeSY885Cshe9zeQ08MPP3yveL/plJR4NGvmxMCB/eDxePDoo3/GJZekom3bppg6dSIKajgLjqer5tIn+5jG7oDn7nvhu2NcZLxLRwGW7D0fe85RRNaqZ+fOBVd8JDc3F9dc0wP33HM/9u3bi6NHD+PFF5fCbndg/PiRaN++Ix577G/BN+R3cXGi+AwZT9pJi2QqU0dOIN6vZK/uyXCOQrJNtvB6gfz8wO7r9/sxcuSNSE5OwT/+8RJSUuLx9de70KrVBQCALVs2Y/z4kdix40jI7eFyKvNIu9yPTBMpk1bNJnHTyCiyVT0L5vFPPjkT+fl5mDt3Ic6cOY2zZ8/iD3/oWvx9TdPg9xeZ1h4Knb5UxkoeT+QutakNWLK3cgznKCVT3d9Al5WuWvUuVq16Bxs2bIXD4UDDho3gcrnw3/9mICkpOTyNCaI9VDM+n7UV4QBxfJ+PIyVWYcneynFCWJTT6/7Gx4v1vYmJYrgnPl4MV8fHi88TE0t2ynM4wnu2qVdWq8quXd9jxoz7sHz5ajRq1BgAoKoqbr/9bsyc+QBOn/4JAJCdfQIbNqwPuS2qKu+ZdG1jda9ZJ0s7oo0sIyeyXthlOFMZ+sYBDoeYFOVwmFMGr7prP59++jFycn7Fddf1KZ6xPXToAMyaNQ+tW7fBn/7UE6mpdTFo0NU4eHBfyO1gr9k8Pl9oj1uxYikGDOgTtnYU1ewqCIVIppETGXFCGEkhmElhRuJkMHNomqgKF4oVK5birbeWYN26TWFrT2IiR0zMlp8vwc55kLdkL3vOJAW73fqtWFXVmNmbeuF+r1csG/N6q9/6sLYLpLf63HNz0aXLBUhNTUDPnhfjk08+wr59e/HggxOxdetmpKTEIy0tEQAwadIYPPTQJAwffj1SUxNw9dU9cOTIobC2h8Krpj3WikZQJk0ag6eeeiSo55H1/57hTFJQlPCWGX322TllipaUHgqvkL8obLN2Na1kJCAnR9zy8sTnbrf4mJdX8j29BxFNYR3Iz5qWdgHWrv0amZm/Ydq0v2LixFGoVy8RzzzzMi67rBeOHctHZmZJ93vVqncwbdpfcfjwr2jdug2efHJmWNtD4cOSvdXjsDZJw7KCFJoG9XgW6r78NJQnHgcaNgz1aaRZnia7YAvPAEDfvpdixozZyMn59bxh7UmTxsBms2PhwiUAgM8//xSPPDIV3377v4Cem4VnzBXM2ubnnpuLN99cjDNnfkJSUgoeeeQpXHhhO/Tr1xlerxculws2mx2zZj2NadMmQVEUxMTEoE+fP+Cdd9YEdAwZ1zxL1hyKZnqZUdMLEigK4lIaQLHbgPbtgccfB+6+u2R2mL5ZdxXCUdjF7y+p4BaJu+gEI5CTj3fffRMvvfQssrIyAQBudz5+/vkMbJXM2mvatFnxv12uOsgPYhJDbT8Zkk0wXUJ9BKVp02ZYvXolJk4chW3bDuKZZ14+7yRt69b/IimpBWbOfNKw9piFw9okFct20aqfACxcCHz+OfD222LHom++EXcYPhyYMaPCx3IXndBUF4bHjh3F/fffjaeffgGHDv2MzMwctG/fEZqmQTEgSRnO5grm9/rmm4eiefMkqKqKW24ZjtatL8T27Vssa49ZavG5OUUql0sElFm7aLlcpb6Qng5s3Cj29x08GOjUCfjyS/HuPXw40Llz8V2NLtavD49Hyi46wahuyZrb7YaiKGjYUKxpf/vtN7B37w8AgMaNmyI7+zjOnTuHmDCNRXMJnbmC+X0OdgTF6PaYhT1nko7lu2gpCnDbbcCuXcB//lNSAHrEiOIpptxFp2aqKzzTrt3FmDTpQVx7bS+0bdsUe/bsRo8elwMA+vb9I9q164B27ZqhTZtGNW6LLIVnomlWf6Cvd/AjKKH9R8rw/18ee84kJT2gLd1F6513ys5a2r8fuO8+YNEiFBSYt0bT6xWvg+y76ATLbq/6NXzkkafwyCNPVfi9995bW+bzF19cWubzPn36ISPjeEDtsKrXrIexx1N9COvFgcJdOtcUhYXnLccI9DUPdgSlSZOmyMw8HHQTZRw5YTiTtBRFBFJMjEW7aPXpIyaHnToFnDwJZGQA339v/v7DEMeLialdk8ScTgmKUPiL4PzuG+DYEeDnn4GffhL/7wMqWXIXBqHM6teX53m9ETirf/Jk4LXXgFatgN69gc6doVxxBZQ23aodFSg9gqKqKoYPv6PCERRVVXHw4BmMGnUnxo4dirS0RPTp0w/Ll6+utnmyjJyUx6VUFBFkWabE/YfDx8rXUqeePIG6HVpA0QvGFxUBf/0r8OijhhxPtu1aTfHqqyKgS5/R9u2L/LVfWX9yBnkrhMn+30oEQJ5dtLiLTvjoI51W7ufsbF4fSlKSGBnRNPFLk5YmfrnCONapaeG/RKPP6g/oEo2Z/H5g926x8uGLL4BNm8RFdED88t56K7B4MZwmTfqsjtmrQwLFnjNFNE0T76N6xSF9opHNFv43Kyl6euw9h03xa5l1VMzC//VXMVs/NlaE9fjxwJ13As2aVf9kVTBj8mClkxvNcvy4COPPPwc2bBAv7DXXiFu/fsAllwCnT4sRiZkzAUXh31M1GM5EAeLmHMYIplpUOJWpCrV9u7jW/NlnQN++wPffA4sWAStXioC55x4RMkG+i5s1qx8wOaBzc8USwy++EIF8+jRw1VXitbr6ajH6UNrLL4sUHDmyzJf1hRBWcbnkHYliOBMFiLvoGOfsWXMn2TmdFcx+d7tFupX222/A8uUiqH0+YOJEYPRooH79gI4jxc8VDl4vsGVLSRjv3An06FESxp07h7RzjRQjJxL2mgGGM1HAcnLkWHOqqkC9ela3Iryk72FqmljzvmgRsHYtMGiQ6E1fdlmlTyTFiECoNA3Yt68kjL/6SvSG9aHqPn3CdhYQ0a+TgRjORAGoyf7DRqiN+w9HzLXZ06eBN94AXnlFnCXdc4+Y5FRqOCMie4Q//STCWA9koCSMr7oKaNIk7G3V1ZoRhjBiOBMFoKqz+5MnszF9+n3YvHkj4uLicc89D2DChMmVPtfcubPwv/9lwOl0Yt26j5GSkoZly1ZhzZpVWLRoPmJinFi48DX88Y9/qvQ5ZD/rD5URs5p1YZ/V7PeLEFu0SJR8HTlSDHt37BgZ11LPnhUzqfWJXJmZwJVXlgTyRReZdgYo/ciJBVi+kygAlZ3C+v1+jBw5EB07piMj4wRWr96Al19+Dhs2rK/y+davX4Nhw27H4cO/olOnzhgy5Fr4/X5kZJzAQw89hqlTJ4TUnkinF55JSAjpEmaFVFU8X506YX5DVlXg2muB1atFqdeGDYFrr4V2xRXw/BLkfphh5vFU8Dvi9wPffQfMnVvSE378cdHjf/FFMSLw8cfAvfcCbduaml6Wl+yVEHvORAGobP/hbdu+xdixQ7F7d1bx1+bP/xsOHtyPF198o8Lnmjt3Fr799j/46CMxdPjZZ2tw9923IjPzN9hsNuTl5aFly7o4cuRX1KuXWOFzRMP+w7IUngmK1wvv15uR364b4LJ23DQ+HnCcyCzpGf/730DjxiWTuPr1E+PfEomokROD1cKBMaLwq+wP+tixozh1KhtpaSUh6vcXoWfPK6p8viZNmhb/OzbWhQYNGhXvsuP6fZus/Pz8SsM5Ut5gakKWwjNBcTjg6d4XsHpWv98Pz8o1cDwwXgTxddcBzzwDpKRY3LCqWV6yVyIR1lwia1T2Jp+cnIKWLVth27YDUrRHNuEoEqMoYjhSH/I0s/BMKH7fuMwwkyaNQVJSC8yc+WTld1JVFF3TXxRTCdf1ARPZ7aJTH3EjJ2HEcCYKQGWVHLt27Y6EhLpYsGAexo+fjJiYGOzbtxeFhQXo0uUy09tjNTN2WtIfJyP9hEEGfrsTmhLqJorWi8iRkzCKvFMqIgtUtv+wzWbDihVrsHv3DnTu3Apt2jTClCl3ITf3N8PaohaehXLO5G2xqqFpotpTbm5JsZbqQkrfaSk/XzyusFCeYAtVUVHl30tPT8PChX9Hnz6d0KJFHO6770789NOPGDp0AFJTEzBo0NXIyfkVADBmzFC0a9cMLVvWw/XX98XevRkAgKVLX8XKlW9j4cKnkZISj1tvHRhyeyKFPnISHy9WriUmigl+8fFiuDo+XnyemCi+r1fQi+RgBjghjChgUlQI8/vh2PgF4scNF9saDhokPlpYMiwqd1qqRFUlXtPT09CkSTO8/fbH8Pl86NevM5KSWmDhwtfQtu3FGDZsAHr3vhLTp/8Vy5e/jptuGoqYmBjMmjUd//nPl9i4cQeAAIe1f1fbSr1GE/aciQIkxe41qgrnDX8C9u4Va1KXLAGSkoCbbgKWLQN++cW0pmiaWCqblxe+Yhv6Tktnz0ZmL7q6No8ffx+aNGmKpKRk9Ox5Bbp27YFOnTrD6XTi+usHYffu7wEAo0aNQ0JCApxOJ2bMmIUfftgZ0mhMJL6GJDCciQJktwc+t2bo0AFISYk/7/bss3Nq1AZV/b1X2awZMGECsH49cPQoMGSIWKOql1hctEhMBjKIXjTCqKpOHo94fqnDpYJhlOqGUhs3Lpml73K5ynweG+uC252PoqIizJ49A126XIDU1LpIT08DAPz885mgmxjpQ7vRLEIHj4jMF8z+wytXrjOkDRXOPK1fH7j9dnFzu0Vgf/gh8PDDwMUXA7fcIoa/W7cOSxvMqubk9ZbsRSFdyJw4AaSmAh06ACNGADfeCHToACUMDf3ggxX49NOP8dFHXyA1NQ25ub+hVav6KLkCGfgxpHvdKGAMZ6IgOJ2hL+2oKX1pSJXi4kQY33KLqJzy738DH30E9OoFNG9e8r0OHUJ+5y4oMO/au9crjiddHeTGjcXrt3s3sGeP2KfY4YDt9BkANbv+n5+fB6fTifr1G+Ls2bN44omHy3y/SZOmyMw8HNBzyTqrn6rHYW2iIOhlBq0QdA8yJgbo319s0JCdDTz/PPDrr8D114vyjDNmiG0Ay48dnz1bsvFBOfqSFjPpy7IsU1Agyl6+8QbwwAOiqEeLFiWvW1GRuNbw0ENQEuJr3FsdPvwOpKS0RMeOyejV62J069azzPdHjboT+/btQVpaIkaNurnS51FV9pwjGWdrE4UgonfR0TRg+3Yx9L1qlRg7HjRI3K64QoTQ+PHA008DDz1U5mERt9NSMDRNXL/ftUvcdu8WHzMzxSYQl1wCdOpUcrv3XuCf/wSSk8U2kh07ApBkVj9q577f0YThTBSCWrWLzt69Iqg//BDIyhJjoT/+KAoRz5wpbkBk7LQUqNxcEb56AOthnJBwfgi3bVtxIfP33hOhvGhRmeGUqpZTmYnLqCIbw5koRBGz/3Awdu0CunQpqV6hqsCIEdCWv21Zr1kXUu+5qAg4cKBsCO/aJXZguvjisiF8ySViZ6kasnKEQWfKSAMZihPCiEKkX3+uVbvo7N8vPsbHix8sPh7YsQM+n7VhA4jj+3xV9AZPnz4/hPfuFcvO9AC+4w7xsXVrw2ZLBTOr3yiRWk+aSrDnTBQGtaZK1o8/At9+K4ZyW7cuTkKprqM6PMD//lc2hHftEmlYvifcsaMYqjZZrb8+T4ZjOBOFSUTuPxygnBw5CoKo2cdRr9uF4sShdBB36iRmUEv0wvl8otqZ2RISIrf8KZVgOBOFWemdmWrDLjqaJsJZCpqGRJcHiitcM8OMFdGz+slSXOdMFGa1bRedYHc2Cmb3JaDyHZgqpCgockRGMANizoBZM6YdDnE8qh0YzkQG0/cfdjjEihyHQ95eckVCGVtbs2YVPvzwc2zZsh/r16/BsGED8Oijc3DgwBn4/X688srC4vteffUAbN16APv3/4ROnbpgwoTbwt4eq+iTBo0OaNNn9ZPheGWCiKoUShjquy8BQM+eV6Bx4ybo1KkzAOD66wdh48YNxfcdNWpc8b9nzJiFVq3qIzf3N9StWy9s7bFSrZzVT4Zjz5mIqhTKm34guy8BCGkHpkgMIUUR14ITEgLf2aw6qiqer06dyHxNqGoMZyKqkpFv/KV3YDp69Dfs3JkJAKhqnmokB5HdLpY5uVyhh7SqisfXrctZ2bUZ/2uJqEpG7mxU3Q5MZrfHDIoiypA6nbVrVj+FF3vORFQlRTEuDKrbgam82rTTUm2b1U/hxXXORFQtqSqEcacligLsORNRtZxOq1sgyNIOIqPxmjMRVctuF0PK+nXR48ez0KvXxRXed/PmPWjRIjXsbVBVToCi6MFhbSIKSK3az5lIchzWJqKAOJ3hW6MbLH1TEKJowXAmooDola6swNKUFG0YzkQUMLvd/B6svraXKJownIkoKNxpich4DGciCgp3WiIyHmdrE1FINI07LREZheFMRDXi8wFud9W1oQOlqqK3zGvMFO0YzkRUY5ometAeT2ghrS+VcjrZWyYCGM5EFEaaxp2WiMKB4UxEhtE0EdKaJm76Dlc2G8OYqCoMZyIiIslwKRUREZFkGM5ERESSYTgTERFJhuFMREQkGYYzERGRZBjOREREkmE4ExERSYbhTEREJBmGMxERkWQYzkRERJJhOBMREUmG4UxERCQZhjMREZFkGM5ERESSYTgTERFJhuFMREQkGYYzERGRZBjOREREkmE4ExERSYbhTEREJBmGMxERkWQYzkRERJJhOBMREUmG4UxERCQZhjMREZFkGM5ERESSYTgTERFJhuFMREQkGYYzERGRZP4/rOy9KAGm1d4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nx.draw_spring(yoda_graph, with_labels=True, node_size=1200, node_color='#eeeeff', edge_color='red')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Challenge:** If you want a challenge, you can try to extract contigs from your graph as described in lectures. To extract a contig, we need to find an unbalanced node, then walk along the directed graph only so long as our path is unambiguous.\n",
    "\n",
    "You can find the in-degree and out-degree of nodes (number of edges leading in and out), and the edges themselves, with networkx methods like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = nx.DiGraph()\n",
    "g.add_edge('A','B')\n",
    "g.add_edge('A','C')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.in_degree('A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.out_degree('A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "OutEdgeDataView([('A', 'B'), ('A', 'C')])"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.out_edges('A')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}