{ "cells": [ { "cell_type": "markdown", "id": "aa4fcf88", "metadata": {}, "source": [ "## Basic Data Structures\n", "\n", "So far in the class you have only really come across one type of data storage - arrays. In practice there are much more sophisticated ways of storing data depending on the application." ] }, { "cell_type": "markdown", "id": "20d3cd98", "metadata": {}, "source": [ "Here we will go over a couple of basic types that turn up all the time (you will be surprised how often).\n", "\n", "The first is the stack. The idea here is imagine a stack of paper, you add always to the top and remove from the top. This is the so called last in first out idea (LIFO)." ] }, { "cell_type": "code", "execution_count": 1, "id": "f41b9cdc", "metadata": {}, "outputs": [], "source": [ "struct Stack\n", " data\n", "end\n", "\n", "function Base.show( io::IO, stack::Stack )\n", " print( stack.data )\n", "end" ] }, { "cell_type": "code", "execution_count": 2, "id": "aad23a31", "metadata": {}, "outputs": [], "source": [ "function Base.push!( stack::Stack, item )\n", " push!( stack.data, item )\n", "end" ] }, { "cell_type": "code", "execution_count": 3, "id": "bf03b361", "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]" ] } ], "source": [ "stack = Stack( [1,2,3] )" ] }, { "cell_type": "code", "execution_count": 4, "id": "3d88d47a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4-element Vector{Int64}:\n", " 1\n", " 2\n", " 3\n", " 4" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "push!( stack, 4 )" ] }, { "cell_type": "code", "execution_count": 5, "id": "0eef7afc", "metadata": {}, "outputs": [], "source": [ "function Base.pop!( stack::Stack )\n", " pop!( stack.data )\n", "end" ] }, { "cell_type": "code", "execution_count": 6, "id": "cdc3cabd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pop!( stack )" ] }, { "cell_type": "code", "execution_count": 7, "id": "081b499f", "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]" ] } ], "source": [ "stack" ] }, { "cell_type": "markdown", "id": "d97f71c8", "metadata": {}, "source": [ "The second type is something called a queue. Imagine you are queueing up, then you enter at the end but are processed from the front in the order you arrived. This is the so called first in first out (FIFO)." ] }, { "cell_type": "code", "execution_count": 8, "id": "be5ba469", "metadata": {}, "outputs": [], "source": [ "struct Queue\n", " data\n", "end\n", "\n", "function Base.show( io::IO, queue::Queue )\n", " print( queue.data )\n", "end" ] }, { "cell_type": "code", "execution_count": 9, "id": "a8a322a3", "metadata": {}, "outputs": [], "source": [ "function Base.push!( queue::Queue, item )\n", " prepend!( queue.data, item )\n", "end" ] }, { "cell_type": "code", "execution_count": 10, "id": "4c7052a6", "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]" ] } ], "source": [ "queue = Queue( [1,2,3] )" ] }, { "cell_type": "code", "execution_count": 11, "id": "791f583a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4-element Vector{Int64}:\n", " 4\n", " 1\n", " 2\n", " 3" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "push!( queue, 4 )" ] }, { "cell_type": "code", "execution_count": 12, "id": "9ecf9d33", "metadata": {}, "outputs": [], "source": [ "function Base.pop!( queue::Queue )\n", " pop!( queue.data )\n", "end" ] }, { "cell_type": "code", "execution_count": 13, "id": "0cda7964", "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "[4, 1, 2]" ] } ], "source": [ "pop!( queue )\n", "queue" ] }, { "cell_type": "markdown", "id": "fedad9e0", "metadata": {}, "source": [ "Why are these useful? Many reasons, for example parts of computer memory are structured as a stack. We will see one use very soon." ] }, { "cell_type": "markdown", "id": "d51199a4", "metadata": {}, "source": [ "## Graph Algorithms" ] }, { "cell_type": "code", "execution_count": 14, "id": "6bc4d8c8", "metadata": {}, "outputs": [], "source": [ "struct Vertex\n", " neighbors::Vector{Int} # Indices of neighbors of this Vertex \n", " coordinates::Vector{Float64} # 2D coordinates of this Vertex - only for plotting\n", " Vertex(neighbors; coordinates=[0,0]) = new(neighbors, coordinates)\n", "end\n", "\n", "function Base.show(io::IO, v::Vertex)\n", " print(io, \"Neighbors = \", v.neighbors)\n", "end" ] }, { "cell_type": "code", "execution_count": 15, "id": "8cf761a9", "metadata": {}, "outputs": [], "source": [ "struct Graph\n", " vertices::Vector{Vertex}\n", "end\n", "\n", "function Base.show(io::IO, g::Graph)\n", " for i = 1:length(g.vertices)\n", " println(io, \"Vertex $i, \", g.vertices[i])\n", " end\n", "end" ] }, { "cell_type": "code", "execution_count": 16, "id": "176e64c8", "metadata": {}, "outputs": [], "source": [ "using PyPlot\n", "\n", "function PyPlot.plot(g::Graph; scale=1.0)\n", " fig, ax = subplots()\n", " ax.set_aspect(\"equal\")\n", " \n", " xmin = minimum(v.coordinates[1] for v in g.vertices)\n", " xmax = maximum(v.coordinates[1] for v in g.vertices)\n", " ymin = minimum(v.coordinates[2] for v in g.vertices)\n", " ymax = maximum(v.coordinates[2] for v in g.vertices)\n", " sz = max(xmax-xmin, ymax-ymin)\n", " cr = scale*0.05sz\n", " hw = cr/2\n", " axis([xmin-2cr,xmax+2cr,ymin-2cr,ymax+2cr])\n", " axis(\"off\")\n", "\n", " for i in 1:length(g.vertices)\n", " c = g.vertices[i].coordinates\n", " ax.add_artist(matplotlib.patches.Circle(c, cr, facecolor=\"none\", edgecolor=\"k\"))\n", " ax.text(c[1], c[2], string(i),\n", " horizontalalignment=\"center\", verticalalignment=\"center\", fontsize=round(Int, 14*scale))\n", " for nb in g.vertices[i].neighbors\n", " cnb = g.vertices[nb].coordinates\n", " dc = cnb .- c\n", " L = sqrt(sum(dc.^2))\n", " c1 = c .+ cr/L * dc\n", " c2 = cnb .- cr/L * dc\n", " arrow(c1[1], c1[2], c2[1]-c1[1], c2[2]-c1[2],\n", " head_width=hw, length_includes_head=true, facecolor=\"k\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "id": "9c57fa94", "metadata": {}, "source": [ "The code above is copied word for word from Prof. Persson's notes.\n", "\n", "A graph is a set of vertices and edges connecting them. They are extremely widely used in pretty much everything. For example one application is traffic flow between cities, facebook friends where each node represents a person and an edge between two nodes representing the fact that they are friends, ... list goes on." ] }, { "cell_type": "code", "execution_count": 17, "id": "4ece8f2c", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAE1CAYAAAB6EON6AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAA9hAAAPYQGoP6dpAAAtR0lEQVR4nO3deVTU9f4/8OewyKJoiqLljkgpcRVmUuy6ZCF1M5X04r6RGaB+21yuafm1ksrqWzflDmp4pVy6Ui6ES4ZbgFe4MIqglisq4HXJDZVhYGY+vz/6SZKgMNvn85nP83GO53hkeH9enCPwnPfzs6gEQRBAREREiuUi9gBEREQkLoYBIiIihWMYICIiUjiGASIiIoVjGCAiIlI4hgEiIiKFYxggIiJSOIYBIiIihWMYICIiUjiGASIiIoVjGCAiIlI4hgEiIiKFYxggIiJSOIYBIiIihWMYICIiUjiGASIiIoVjGCAiIlI4hgEiIiKFYxggIiJSOIYBIiIihWMYICIiUjiGASIiIoVjGCAiIlI4hgEiIiKFYxggIiJSOIYBIiIihWMYICIiUjiGASIiIoVzE3sAInurrKzE4cOHce7cOej1egiCAE9PT/j5+aFHjx7w8fERe0QikolLly6hoKAA169fh8FggJubG7y9vREYGIiuXbvCxUWe77EZBsjpGI1GbNmyBdu3b4dOp0NhYSEqKytrfa1KpUJgYCDUajWeeuopjB49muGAiKqVlpZizZo12L9/P3Q6HUpKSup8rY+PD0JCQqDRaPDXv/4VYWFhUKlUDpzWcipBEASxhyCyhQsXLiApKQnLly9HSUkJunfvjl69ekGtVkOtVqNLly7w9vaGSqVCRUUFSktLodPpqv/85z//QePGjTFp0iTExcWhe/fuYn9JRCQCQRCwd+9e/OMf/8DmzZvh4eGBPn36QKPRQK1WIyQkBL6+vvDw8IDRaMStW7dw9OhR6HQ65OXlYf/+/SgtLUVISAimTZuGMWPGoHHjxmJ/WfcnEMlcRUWFMG/ePMHd3V3w9vYWpk6dKhw4cKDB65w7d06YP3++4OfnJwAQoqKihIsXL9phYiKSqoKCAkGj0QgAhG7dugkJCQnCjRs3GrSGyWQStm/fLgwZMkRQqVRC8+bNheTkZMFsNttpausxDJCs5ebmCkFBQYK7u7uwcOFC4dq1a1avaTAYhFWrVgm+vr5Cy5YthZSUFOsHJSJJq6ysFN5//33B3d1dCAoKEnbu3GmTX95FRUXChAkTBADC4MGDhdLSUhtMa3sMAyRLZrNZiI+PF1xdXYXQ0FChoKDA5se4ePGiMGLECAGAMHr0aEGv19v8GEQkvuLiYkGtVguurq7CvHnzhIqKCpsf4/vvvxfatGkjPPTQQ0JqaqrN17cWwwDJjslkEl599VUBgPDOO+8IlZWVdj3ev/71L8HLy0sYOHCgUFZWZtdjEZFjHT9+XOjYsaPQsWNHITc3167HunLlivDiiy8Krq6uwldffWXXYzUUTyAkWREEAa+//jqWLl2KxMRExMTEOOS4WVlZGDx4MEJCQrB9+3Z4eXk55LhEZD9nzpxB37594ePjg/T0dLRr187uxzSZTIiNjcXKlSuxdu1ajBkzxu7HrA+GAZKVTz75BHPmzIFWq0VcXJxDj71v3z4MGjQIzz33HDZs2CCbS4aI6F5lZWXQaDQwmUzIzMzEI4884rBjm81mREdHY926dfjxxx8xcOBAhx27LgwDJBsFBQXQaDR44403sHjxYlFm2LRpE4YPH47k5GRMmjRJlBmIyHoxMTFYu3Yt8vPzERAQ4PDjG41GDBo0CEVFRSgsLBT9/iYMAyQLVVVV6N27NyorK6HT6eDh4SHaLBMmTEBaWhqOHDmCtm3bijYHEVkmPT0dERERouww3q2oqAjBwcEYP348li1bJtocAMMAycSiRYuwcOFCZGdnQ6PRiDrL1atXERQUhNDQUGzZsoV1AZGM3Lx5E48//jgCAgKQnp4u+u2DtVotpk+fjvT0dISHh4s2B8MASV5ZWRkeeeQRxMXF4ZNPPhF7HADAxo0bMWLECPz73/9Gnz59xB6HiOrp//7v/zBv3jwcO3YMnTp1EnscmM1mDBgwAFVVVcjOzhZtDnk+UYEUZfXq1aioqMAbb7wh9ijVIiMj0aVLF2i1WrFHIaJ6MpvNSExMxMiRIyURBADAxcUFs2bNQk5ODnQ6nXhziHZkonoQBAFarRYvvviiRWf7lpaW4u9//zsiIiLQoUMHNGrUCG3atMGIESOQk5Nj8VwuLi6IjY1FSkoKLl++bPE6ROQ46enpOHXqlM3OE/j444+hUqmgUqmselc/ePBgtG/fHomJiTaZyxIMAyRpmZmZOHr0KKZNm2bR5y9duhRvvPEGTp8+jUGDBmHmzJno27cvUlNT8eSTTyIlJcXi2aKjo6FSqbBq1SqL1yAix0lMTESPHj1sUu39/PPPWLBggU0eQOTm5oaYmBisW7cO169ft3o9SzAMkKTt3LkTfn5+eOqppyz6/F69eiEjIwMnT57EypUr8eGHH+K7777Dnj174Orqiri4OBgMBovW9vX1xaBBg7Bz584Gf25FRQVSU1Mxbtw4zJs3z6LjEynJrVu3MG7cOLz22mvIysqC2Wxu0OebzWbs3r0bo0aNsvqkX5PJhEmTJqFHjx548cUXrVrrjlGjRkGv12P//v02Wa+hGAZI0nQ6HdRqtcXfvMOHD0e/fv3u+fd+/fph4MCBuHr1KgoLCy2e74knnoBOp0N9zsO9OwD4+voiMjIS33zzDT799FOLj0+kFMePH8e6deuQkJCAfv364eGHH25QMDhx4gRu3rxpk6uRFi9ejEOHDuGf//wnXF1drV4PALp06YKHHnpItPMGGAZIsgRBQF5ent0uJXR3dwfw2xadpdRqNa5evYozZ87U+vE7AWDs2LHVASAlJQXl5eUAUK8QQUS/u/OL/9KlS9BqtfUOBnl5eQB++561xuHDh/Huu+/i7bffRlBQkFVr3U2lUkGtVjMMEP3R+fPncenSJau/eWtz7tw57Ny5E23atEFwcLDF69yZ7e5v4NoCwLffflsdAIxGo3XDExGA37+X6hMMDhw4gM6dO6NFixZWHW/y5Mno1q0b5s6da/X8fyRmGLD8LRGRnf33v/8FAHTo0MGm61ZVVWHChAkwGAz4+OOPrdrma9OmDRo1aoTi4mKkpqZi/fr1SE1NRXl5Odzc3Kp/WDEAENnXH4PBkiVL4Ofnh9GjRyMqKgrnz59Hx44drTrGBx98gEOHDiEnJ6d6Z9GWOnbsiAsXLth83fpgGCDJqqioAACbPiHQbDbjpZdeQkZGBqZOnYoJEybYZM0333zznn+vbwCoqqriXQyJbOjuYLBkyRIsWbIEAKza1j906BAWLVqEWbNmITQ01CZz/pGnpyeqqqpgMplsdi5CfbEmIMUQBAFTp07FmjVrJHEvcCKSj0mTJqFLly5YuHCh2KPYBXcGSLI8PT0BAHq93uq1zGYzXn75ZaxatQpjxoxBcnKyze5J7uLigs8++wz+/v5ISUnB5s2b76kJ7sfd3R2VlZU2mYXIWR04cKDe5w/d+d67UxOMHDkSCQkJVm3BHzp0CMDvP5f+6M69CzZt2oTIyEiLjlFRUQF3d3eH7woADAMkYQ8//DCA3072CwkJsXidu4PAqFGjsHr1apt9s124cAGVlZVo3749hg0bhmHDhqGiogI7duywKBgQkWVqCwB9+vSpDv0bN2606q6jU6ZMqfXfMzIycOLECQwdOhStWrWy6jbHZ8+eRZs2bSz+fKsIRBJlNpsFPz8/4Z133rF4DZPJJEyePFkAIERFRQlVVVU2nFAQtmzZIgAQTp8+XevH9Xq9kJqaKowdO1bw9vYWAAhubm4CgOo/7u7uNp2JyBnpdLoa3zd3fy/5+fkJr732mpCVlSWYTKZaP3/NmjUCAOHKlSs2nWvSpEkCAGH//v1Wr/XMM88IkZGRNpiq4bgzQJKlUqmg0Wiqrw+2xHvvvYfk5GQ0adIEgYGBWLRo0T2viYyMRM+ePS1aX6fToUWLFnW+G/D09MTQoUMxdOhQVFRU4Mcff8T69eurdwx44iBRw7i4uMBsNsPPzw9jxoxBVFRUjR2Auty5X4lOp8OgQYMcMWqDCIIAnU6HmTNninJ8hgGSNLVajeXLl0MQBIt+cd65GdCtW7cQHx9f62s6depkcRjIzc2t9x0SawsGKSkpNr90ksgZBQYGYty4cWjZsmW9A8DdunbtCh8fH+Tl5UkyDJw6dQrXr1+3y31V6kMlCLwFGklXRkYGBgwYgN27d2PgwIFij1PDlStX0LZtW7z33nuYM2eO2OMQ0QNERkaiqKgI+fn5ktuVi4+PR3x8PM6fP4+HHnrI4cfnpYUkaf369UP37t2h1WrFHuUeq1atgiAIiI6OFnsUIqqHuLg4FBQUiPYwoLoYjUYsX74cY8eOFSUIAAwDJHEqlQrTpk3Dpk2bcP78ebHHqWY2m7Fs2TKMHDkSrVq1EnscIqqHQYMGoUuXLkhMTBR7lBq2bt2K4uJiix/VbgsMAyR5EyZMgKenJz7//HOxR6m2efNmnDp1StRvXiJqGBcXF8TFxSElJaXOh4s5mtlsxqefforevXvb7c6G9cFzBkgWFi1ahIULFyI7O9tuTzGsr6tXryIoKAihoaHYsmWL5LpHIqrbzZs38fjjjyMgIADp6ek2u/mYpbRaLaZPn4709HSEh4eLNgfDAMlCVVUVwsLCYDAYoNPp4OHhIdosEyZMQFpaGo4cOYK2bduKNgcRWSY9PR0RERHQarWIi4sTbY6ioiIEBwdL4vboDAMkG4WFhVCr1XjjjTewePFiUWbYtGkThg8fjuTkZEyaNEmUGYjIejExMVi7di3y8/MREBDg8OMbjUYMGjQIRUVFKCwshI+Pj8NnuBvDAMnKJ598gjlz5oiS6LOyshAREYHnnnsOGzZsYD1AJGNlZWXQaDQwmUzIzMzEI4884rBjm81mREdHY926dfjxxx8lcdk0TyAkWZk1axZee+01TJ8+3aHballZWRg8eDB69eqFtWvXMggQyVzTpk2Rnp6OyspKPP300ygpKXHIcU0mE1555RWsXr0aX3/9tSSCAMAwQDKjUqnw2Wef4X/+538QFxeHBQsWoKqqym7HEwQB//rXvxAREQG1Wo20tDR4eXnZ7XhE5DgdO3bEnj17UFFRgb59+1p16/P6uHr1KqKiopCcnIzk5GSMGTPGrsdrCIYBkh0XFxf8/e9/R3x8PD744AOEhYWhsLDQ5se5ePEinnzySYwZMwbDhg3Dtm3bRO/1iMi2AgICkJWVhZYtWyIsLAxz5syBwWCw+XHS0tIQFBSEPXv2YOPGjZg4caLNj2ENhgGSJZVKhXnz5iE7OxsGgwFqtRrvvvsurl27ZvXalZWVSE5ORvfu3ZGdnQ0AWLduXZ3PMScieWvXrh2mT58OAPj0008RGhqKXbt2wRan1J05cwYTJkzA0KFDoVarceTIEQwdOtTqdW2NYYBkTaPRQKfTYfbs2YiPj0fbtm0xdepUHDhwoMFrnTt3DvPnz0f79u0RHR2N8PDw6oeGvPrqq7YenYgkwGAwIC4uDi+99BJMJhPGjh0Lb29vhIeHIygoCAkJCbhx40aD1jSbzdi+fTuGDBkCf39/bN26FV999RXS0tIceqJiQ/BqAnIaFy5cwMqVK7Fs2TKUlJSge/fueOKJJ6BWq6FWqxEQEAAvLy+4uLhAr9ejtLQUOp2u+k9ubi6aNGmCSZMmITY2Ft27d4fRaIS7uzsA4PTp0+jcubPIXyUR2UpxcTEiIyORn58Ps9kMANiyZQuef/55/PTTT/jHP/6BTZs2wcPDA2FhYdBoNFCr1QgJCYGvry88PT1RVVWF27dv48iRI9U/S/bv34/S0lKEhIRg+vTpGD16NBo3bizyV3t/DAPkdIxGI7Zs2YIffvgBOp0OBQUFqKysrPW1KpUKjz76KNRqNQYMGIAxY8agSZMmNV6TmZmJ/v37A/gt8fNKAiL527lzJ6KionDr1i0YjUYAgJubG65du1bjZ8D58+exevVqZGdnQ6fTobi4uM41fXx8EBoaCrVajaioKPTu3Vs2Py8YBsjpVVZW4siRIzh37hz0ej3MZjO8vLzQqlUr9OjRo14nBYaFhSEnJwczZszA0qVLHTA1EdmD2WzGRx99hLfffhsqlap6R0ClUqFv377IyMi47+dfunQJBQUFuHHjBioqKuDu7g5vb28EBgYiICBA9NsbW4phgKgeWBcQyd/169cxYcIEbNmy5Z6Pubq64v3338dbb70lwmTik2eEIXIwNze36ncM/v7+NjnLmIgcp6CgAD179sT27dtr/bjJZEJERISDp5IOhgGieurXrx969+4NgFcXEMnJ6tWr0atXL5SUlMBkMtX6mmbNmiEkJMTBk0kHawKiBmBdQCQfBoMBr7/++gNvXe7q6ooRI0Zg/fr1DppMergzQNQArAuI5OH27dt48sknsWLFige+1mQy4dlnn3XAVNLFMEDUQKwLiKRPr9cjPz+/3q8fNGiQ/YaRAdYERBZgXUAkfbm5uRg/fjxOnDhx3128gIAAnDhxwoGTSQ93BogswLqASPqeeOIJFBQU4G9/+1udN/9xc3PD888/7+DJpIdhgMhCrAuIpM/DwwMffvhhnYHdaDQq+pLCOxgGiKyQlZUFAEhISEBRUZHI0xBRbZKSkqr/PnfuXKhUKri6ugL4bWdgwIABYo0mGTxngMhKfHYBkXSVlZWhWbNmAIAbN26gadOm1ecSHD9+HP369XvgLYiVgDsDRFZiXUAkXXeCQFJSEpo2bQrg93MJli1bhpUrV4o5nmRwZ4DIBnh1AZH0JCUlYerUqQDAk3wfgGGAyEZYFxBJR231ANWNNQGRjbAuIJKO2uoBqht3BohsiHUBkfhYDzQcwwCRjbEuIBIP6wHLsCYgsjHWBUTiYT1gGe4MENkB6wIix2M9YDmGASI7YV1A5DisB6zDmoDITlgXEDkO6wHrcGeAyI5YFxDZH+sB6zEMENkZ6wIi+2E9YBusCYjsjHUBkf2wHrAN7gwQOQDrAiLbYz1gOwwDRA7CuoDIdlgP2BZrAiIHYV1AZDusB2yLOwNEDsS6gMh6rAdsj2GAyMFYFxBZjvWAfbAmIHIw1gVElmM9YB/cGSASAesCooZjPWA/DANEImFdQFR/rAfsizUBkUhYFxDVH+sB++LOAJGIWBcQPRjrAftjGCASGesCorqxHnAM1gREImNdQFQ31gOOwZ0BIglgXUB0L9YDjsMwQCQRrAuIfsd6wLFYExBJBOsCot+xHnAs7gwQSQjrAiLWA2JgGCCSGNYFpGSsB8TBmoBIYlgXkJKxHhAHdwaIJIh1ASkR6wHxMAwQSRTrAlIS1gPiYk1AJFGsC0hJWA+IizsDRBLGuoCUgPWA+BgGiCSOdQE5M9YD0sCagEjiWBeQM2M9IA3cGSCSAdYF5IxYD0gHwwCRTLAuIGfCekBaWBMQyQTrAnImrAekhTsDRDLCuoCcAesB6WEYIJIZ1gUkZ6wHpIk1AZHMsC4gOWM9IE3cGSCSIdYFJEesB6SLYYBIplgXkJywHpA21gREMsW6gOSE9YC0cWeASMZYF5AcsB6QPoYBIpljXUBSxnpAHlgTEMkc6wKSMtYD8sCdASInwLqApIj1gHwwDBA5CdYFJCWsB+SFNQGRk2BdQFLCekBeuDNA5ERYF5AUsB6QH4YBIifDuoDExHpAnlgTEDkZ1gUkJtYD8sSdASInxLqAxMB6QL4YBoicFOsCciTWA/LGmoDISbEuIEdiPSBv3BkgcmKsC8gRWA/IH8MAkZNjXUD2xHrAObAmIHJyrAvInlgPOAfuDBApAOsCsgfWA86DYYBIIVgXkC2xHnAurAmIFIJ1AdkS6wHnwp0BIgVhXUC2wHrA+TAMECkM6wKyBusB58SagEhhWBeQNVgPOCfuDBApEOsCsgTrAefFMECkUKwLqCFYDzg31gRECsW6gBqC9YBz484AkYKxLqD6YD3g/BgGiBSOdQHdD+sBZWBNQKRwrAvoflgPKAN3BoiIdQHVivWAcjAMEBEA1gVUE+sBZWFNQEQAWBdQTawHlIU7A0RUjXUBAawHlIhhgIhqYF2gbKwHlIk1ARHVwLpA2VgPKBN3BojoHqwLlIn1gHIxDBBRrVgXKAvrAWVjTUBEtWJdoCysB5SNOwNEVCfWBcrAeoBkGwaMRiN+/vln6HQ6nDhxAuXl5TAajfDw8ECzZs3wpz/9CWq1Gm3btuX2JpEVWBc4N9YDBABuYg/QEFevXkVycjK+++475OfnQ6/XQ6VSoX379mjSpAnc3NxgMBhw5coV/PrrrwAAPz8/9OnTB9HR0XjhhRfg6uoq8ldBJC936oKcnBy8+uqrWLp0qdgjkQ2xHiBAJjsDBw4cQEJCAr755huYTCYMHToUTz75JDQaDUJCQuDj41Pj9YIgoLS0FDqdDnl5edixYwdyc3PRoUMHxMTE4OWXX4afn59IXw2R/LAucE6sB+gOSYeBsrIyzJ49GytWrECHDh0QGxuLKVOmWPSLPC8vD4mJiVi3bh08PDzwxRdfYOLEidzyJKon1gXOhfUA3U2yVxPs3LkTwcHBWLduHbRaLU6fPo233nrL4nf0Go0GK1euRHFxMYYOHYrJkydjyJAhKC0ttfHkRM6JVxc4F9YDdDfJ7QwIgoB33nkH8fHxePrpp7Fy5Up06tTJ5sdJS0tDTEwM9Ho9UlNTq9/xEFHdWBc4B9YD9EeSCgOCIGDGjBnQarX46KOPMGfOHLtuRV67dg1RUVHYt28fNm7ciL/85S92OxaRs2BdIG+sB6g2kqkJBEHArFmzoNVqsWLFCvztb3+z+w+Z5s2bY8uWLYiIiMDw4cOxd+9eux6PyBmwLpA31gNUG8nsDCxfvhyxsbFYunQpZsyY4dBjGwwGvPDCC8jJycGhQ4e49Un0AKwL5In1ANVFEmGgqKgIwcHBGDduHJYvXy7KDGVlZQgODkZAQADS09Ph4iKZTRMiSWJdIC+sB+h+RP+NZzabMWXKFPj6+uKTTz4RbY6mTZsiKSkJu3fvFi2QEMkJ6wJ5YT1A9yP6zsCKFSsQExOD9PR0hIeHizkKACAmJgZr167F0aNH0aFDB7HHIZI01gXywHqAHkTUMGAymdC1a1eEhYVh3bp1Yo1RQ1lZGTp16oSXX34ZH3/8sdjjEEke6wJpYz1A9SFqTbBjxw4UFRXhtddeE3OMGpo2bYro6GisXLkSer1e7HGIJI91gbSxHqD6EHVnYPDgwbh48SJyc3Mtejdx/fp1LFiwALm5uSgqKsK1a9fQsmVLPProo5g+fTqGDx9u0bonTpxAYGAgvvrqK0ycOLHBn0+kNKwLpIn1ANWXaGGgpKQEHTp0wJdffokpU6ZYtMbJkyfRs2dPhIWFISAgAC1atMClS5eQlpaGS5cuYerUqVixYoVFaz/77LMoLy9HZmamRZ9PpDSsC6SF9QA1hGhh4Ntvv8XIkSNx4cIFtG7d2qI1TCYTBEGAm1vNJzHfvHkTYWFhOHr0KA4fPoygoKAGr7106VLMmjULN2/eRKNGjSyaj0hpwsLCkJOTgxkzZvBRxyK7E8aSkpIsfsNFyiHaOQM6nQ7t2rWzOAgAgKur6z1BAAB8fHzw7LPPAvht98ASarUalZWVOHz4sMXzESlNVlYWACAhIQFFRUUiT6NcSUlJ1X9nEKD6EDUMqNVqu6xdUVGB3bt3Q6VSoXv37hat0bNnT7i4uECn09l4OiLn5ebmhoyMDACAv78/e2oRlJWVVZ8ncOPGDZGnIbkQLQzk5+cjNDTUJmtdv34dCxcuxIIFCxAbG4vAwEAcOnQICxYsQNeuXS1a09vbG926dcPBgwdtMiORUvDqAnHx6gGyhCjnDNzp+bVaLWJiYqxe78yZMzXOXnZ3d8cHH3yAmTNnWnUS09NPP43WrVvjm2++sXpGIiXh1QXi4NUDZClRdgaMRiPMZjM8PDxssl6nTp0gCAKMRiOKiorw3nvvYf78+RgxYgSMRqPF63p5efFeA0QWYF3geKwHyBqihAFXV1cAv11+ZOt1O3XqhLlz52LRokXYtGkTvvzyS4vXMxqNtZ6gSEQPxrrAsVgPkDVECQMuLi5o1KgRysvL7XaMiIgIAMDevXstXqO8vBxeXl42mohIeXh1gWPw6gGylmgnEHbu3BnHjh2z2/rnz58HAIvf2QuCgGPHjsHf39+WYxEpCusC+2M9QLYgWhhQq9XIy8uzao38/Pxa//NfvXoV8+bNAwD85S9/sWjt4uJiXL582W6XPxIpBesC+2I9QLYgWiGuVquxadMmq3r55ORkJCUlYeDAgejYsSMaN26Ms2fPYuvWrbh16xZGjBiBsWPHWrT2nfsLMAwQWS8rKwvu7u5ISEjAm2++yasLbIT1ANmKaGFAo9FAr9ejoKDA4vsN/PWvf8WNGzeQnZ2NjIwMlJeXo0WLFujbty8mTpyI0aNHW3xpYU5ODlq3bo1HHnnEos8not/dqQv69+8Pf39/PrvABlgPkC2J9mwCg8GADh06YPTo0fjiiy/EGKFOVVVV6NSpE1544QUsX75c7HGInAafXWA7fPYA2ZKojzCeP38+EhISUFpaiiZNmog1xj02btyIESNG4ODBg+jZs6fY4xA5Dd6MyDZ4cyGyNVHDwNmzZ+Hv74/ExES88sorYo1xj/DwcOj1euzbt0/sUYicDh91bB0+mpjsQbSrCQCgY8eOGDJkCD7++GO73nOgIbKysrBr1y5MmzZN7FGInBKvLrAOrx4gexB1ZwAAjh07hp49eyI2Nhaff/65mKOgvLwcPXr0gJ+fHzIyMqrvlEhEtsW6wDKsB8heRN0ZAIBHH30UixYtwhdffIHMzExRZ5k3bx5KSkqwatUqBgEiO+LNiBqOVw+QPYkeBgDg9ddfR58+fRAdHY0rV66IMsOOHTuwZMkSxMfHIzAwUJQZiJSEdUHDsB4gexK9Jrjj5MmT6NOnDzp37oxdu3bBx8fHYcfOzs5GeHg4+vfvj7S0NO4KEDkI64L6YT1A9iaZMAAABw4cwMCBA9GtWzds27YNLVq0sPsxf/rpJwwZMgQ9e/bEDz/8AG9vb7sfk4h+x6sL7o9XD5AjSKImuCM0NBS7d+/GqVOn8Oc//9nqZxfcj9lsRmJiIp577jn06tUL27ZtYxAgEgHrgvtjPUCOIKkwAPz2LIB9+/ahcePGCAsLw/z582EwGGx6jKKiIoSHh2PatGmYPHkytm7dKqmbHhEpDR91XDs+e4AcRVI1wd2qqqqwePFivPfeewgMDMSCBQsQGRmJRo0aWbzmxYsX8eWXX+Kjjz6Cr68v/vnPf+KZZ56x4dREZCnWBTWxHiBHktzOwB3u7u54++23kZeXh5YtW2LUqFHo2LEjFixYgLNnz9Z7HZPJhMzMTIwdOxbt27dHfHw8oqOjcfjwYQYBIglhXVAT6wFyJMnuDPzR4cOHkZiYiK+//hq3bt1C27ZtoVaroVarERQUhMaNG8Pd3R0VFRW4cuUKDh48CJ1OhwMHDuD27dsICAhAXFwcJk+e7JATE4mo4Xh1wW949QA5mmzCwB03b97Ejh07oNPpkJeXB51Oh2vXrt3zOn9/f2g0GqjVaoSFhaFv375wcZHsRggR/X9KrwtYD5AYZBcG/kgQBFy5cgV6vR5VVVXw9PSEj4+PQ+9TQES2peRHHfPRxCQG2YcBInI+Sq0LWA+QWBgGiEiSlFYXsB4gMbFEJyJJUtrVBbx6gMTEnQEikiyl1AWsB0hsDANEJGnOXhewHiApYE1ARJLm7HUB6wGSAu4MEJHkOWtdwHqApIJhgIhkwdnqAtYDJCWsCYhIFpytLmA9QFLCnQEikg1nqQtYD5DUMAwQkazIvS5gPUBSxJqAiGRF7nUB6wGSIu4MEJHsyLUuYD1AUsWdASKSHTc3N2RkZAD47XHld/9iLSkpwbBhwzBz5kyxxqtVWVlZdRC4ceOGyNMQ1cQwQESy9Me6QBAErFq1Ct26dUNaWho+//xzXL16VeQpf8d6gKSMNQERydbddcGAAQPw008/1fh4SkoKoqKixBitBtYDJHXcGSAi2XJ1dcX06dMB4J4g4Obmhh07dogxVg2sB0gO3MQegIjIEiUlJZgyZQp+/PHHWj9uNBqxbds2CIIg6uWHrAdIDrgzQESys3r1anTr1g27du267+v++9//4vjx4w6a6l5JSUnVf58yZYpocxA9CM8ZICLZefjhh3HhwoUHvk6lUmHJkiWYMWOGA6aqiTcXIjnhzgARyc6yZcvQpEkTuLq63vd1KpUKP/zwg4Omqon1AMkJdwaISJZOnjyJYcOG4ZdffoHZbK7zdV5eXrh+/ToaNWrksNl49QDJDXcGiEiWAgICkJubizFjxtz3dXq9HtnZ2Q6ailcPkDwxDBCRbHl7e2P16tXQarVwc3OrtTZwc3Or84oDe2A9QHLEmoCInEJOTg4iIyNx+fJlmEymGh8LDQ2FTqez+wysB0iuGAaIyGlcvnwZI0eOxE8//VTjl7FKpcKvv/6KFi1a3PM5RqMRP//8M3Q6HQ4cOIDLly+joqICKpUKXl5eaN++PdRqNdRqNTp37lznPQt49QDJGWsCInIarVq1ws6dOzF37lwAqP7FLQhCjXsSVFVVYcOGDYiIiEDTpk3xpz/9CdHR0dixYwcuXrwIg8EAvV6PkpISrFmzBiNHjkSXLl3g6+uLcePGYd++ffe882c9QHLGnQEickrff/89xo0bB71eD7PZjJdeegkffvghtFotVqxYgfPnz+PPf/4zhg8fDrVajZCQkDp/iV+8eBE6nQ7/+c9/sHbtWpw8eRLBwcGYNm0aoqOjsXr1atYDJGsMA0TktO5cfnj06FE0b94cKpUKBoMB48ePR1xcHHr06NHgNc1mM3bt2gWtVovvv/8egYGB+OWXXwCwHiD5YhggIqd25swZ9O/fH8XFxRg+fDgSExPh5+dnk7ULCwsRFRWFY8eO4fnnn8fGjRvh4eFhk7WJHInnDBCR0yooKECfPn1QXl6O9evXY8OGDTYLAgAQHByMgoIC/O///i/S09PRv39/XLlyxWbrEzkKdwaIyCnl5uYiIiIC/v7+2LZtG1q3bm3X4+Xl5eH555+Hn58fdu/ebdPQQWRvDANE5HQOHz6MAQMG4LHHHsO2bduqz/S3t2PHjmHgwIFo3bo19uzZg4ceesghxyWyFsMAETmVsrIyBAcHo3nz5ti7d6/DfyHfCSJ9+vRBWlpanfclIJISnjNARE5l9uzZuHLlCjZv3izKO/PHH38cycnJ2Lp1K77++muHH5/IEtwZICKnkZ6ejoiICGi1WsTFxYk6y8SJE/H999/jyJEjaNu2raizED0IwwAROYWKigo8+uijCAgIQHp6OlxcxN34vHr1KoKCgtC7d29s3rxZ1FmIHoQ1ARE5hZSUFJw7dw5arVb0IAAALVq0wEcffYTU1FQcP35c7HGI7os7A0TkFMLCwtCsWTPs2LFD7FGqVVRUoF27dpg4cSI+++wzscchqpP48ZmIyEo6nQ45OTmYNm2axWusWbMGMTEx0Gg08PDwgEqlQnJyslVzeXp6YsqUKVi1ahXKy8utWovInhgGiEj2kpOT0a5dOwwePNjiNd5++22sWLECZ8+excMPP2yz2WJjY3H9+nWeN0CSxjBARLK3f/9+PPPMM3Bzc7N4jaSkJJw5cwaXL19GbGyszWbr3LkzAgMDkZ2dbbM1iWyNYYCIZM1gMKCgoAAajcaqdcLDw9GxY0cbTVWTRqOBTqezy9pEtsAwQESydvjwYVRVVUGtVos9Sp3UajUOHjwIo9Eo9ihEtWIYICJZKygoAAD06NFD5EnqFhISAr1ej5MnT4o9ClGtGAaISNZu3LgBb29veHt7iz1KnXx9fQH89twEIiliGCAiWTMYDPDw8BB7jPu6M19FRYXIkxDVjmGAiGTNzc1N8l38nfnc3d1FnoSodgwDRCRr3t7eKC8vh9lsFnuUOt2+fRsA4OXlJfIkRLVjGCAiWevatStMJpOk7/9/5MgRqFQqBAQEiD0KUa0YBohI1u5cUijl6/h1Oh0ee+wxNGnSROxRiGpl+e26iIgkoHnz5vD390deXh7GjRtn8TpJSUnIysoCABQWFlb/2969ewEAkZGRiIyMtGhtnU4n6fsgEDEMEJHsaTQa/Pvf/7ZqjaysLHz11Vc1/m3fvn3Yt28fAKBTp04WhYHbt28jPz8fo0aNsmo+InviI4yJSPa+/fZbjBw5EgUFBQgODhZ7nBq+/PJLxMbG4vTp03a73TGRtRgGiEj2qqqq0KFDB7z44ovQarVij1NNEASEhoaiQ4cOSE1NFXscojrxBEIikj13d3e88sorWL16NW7evCn2ONWys7ORn5+PadOmiT0K0X1xZ4CInEJJSQn8/f0xe/ZsxMfHiz0OzGYzwsPDUVJSgl9++QUuLnzvRdLF/51E5BTatWuHBQsWYPHixcjLyxN7HCxbtgx79uxBYmIigwBJHncGiMhpVFVVISwsDAaDATqdTrRnFhQVFSE4OBjjx4/HsmXLRJmBqCEYBojIqRQWFkKtVuOVV17B0qVLoVKpHHp8vV6P8PBwlJaWorCwED4+Pg49PpEleJ8BInIqwcHBWLp0KWJjY9GyZUssXLjQYceurKxEVFQU8vPzsWvXLgYBkg2GASJyOjExMbh27RreeustGAwGfPDBB3bfISgvL8eIESOwe/dupKWlISwszK7HI7IlhgEickpz585Fo0aNMHPmTBw/fhyJiYnw8/Ozy7EKCgowefJkHD9+HNu2bcMzzzxjl+MQ2QtPcSUip/Xmm2/iu+++Q0ZGBrp3747169fDlqdJVVVV4f3334dGo0FlZSUyMzMZBEiWGAaIyKmNGDECR44cwVNPPYXRo0fjhRdewK5du6wKBQaDAWvXrsUTTzyBd999F7Nnz4ZOp0NISIgNJydyHIYBInJ6fn5++O6775CSkoKzZ88iPDwc3bp1wxdffIHi4uJ6BQOz2YyjR4/irbfeQvv27TF+/Hj4+voiOzsb8fHxol3GSGQLvLSQiBRFEARkZmZCq9Viw4YNMBqNaNWqFdRqNdRqNdq2bQtPT0+YzWbo9XqcOnUKOp0OBw8exK1bt9CsWTNMnjwZsbGxeOyxx8T+cohsgmGAiBTr0qVL2L9/P3Q6HXQ6HQ4cOIBff/0VRqMRANCoUSO0b9++Oiio1WqEhYWhcePGIk9OZFsMA0REf2A0GqFSqeDq6ir2KEQOwTBARESkcDyBkIiISOEYBoiIiBSOYYCIiEjhGAaIiIgUjmGAiIhI4RgGiIiIFI5hgIiISOEYBoiIiBSOYYCIiEjhGAaIiIgUjmGAiIhI4RgGiIiIFI5hgIiISOEYBoiIiBSOYYCIiEjhGAaIiIgUjmGAiIhI4RgGiIiIFI5hgIiISOEYBoiIiBSOYYCIiEjhGAaIiIgUjmGAiIhI4RgGiIiIFI5hgIiISOEYBoiIiBSOYYCIiEjhGAaIiIgU7v8BaRhAD3Qxt1YAAAAASUVORK5CYII=", "text/plain": [ "Figure(PyObject
)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "v1 = Vertex([4], coordinates=[1,0.5])\n", "v2 = Vertex([1,4], coordinates=[0,2])\n", "v3 = Vertex([], coordinates=[-1,1])\n", "v4 = Vertex([2], coordinates=[2,2])\n", "g = Graph([v1,v2,v3,v4])\n", "\n", "plot(g)" ] }, { "cell_type": "markdown", "id": "cdd28301", "metadata": {}, "source": [ "This is called a directed graph, in that the edge goes from 2 to 1 but not the other way around. An undirected graph is when if 1 goes to 2 then 2 also goes to 1." ] }, { "cell_type": "markdown", "id": "dbf74c44", "metadata": {}, "source": [ "One of the most widely used graph algorithms is depth-first search (DFS). What DFS does is to search from each node to its neighbours, and traverses to each of its neighbours as far as possible before backtracking. If you think about it you will realise that the algorithm in Project 2 is actually DFS in disguise!" ] }, { "cell_type": "code", "execution_count": 18, "id": "923ea46b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "dfs (generic function with 1 method)" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function dfs(g::Graph, start)\n", " visited = falses(length(g.vertices))\n", " tovisit = Stack( [start] )\n", " function visit(ivertex)\n", " visited[ivertex] = true\n", " println(\"Visiting vertex #$ivertex\")\n", " for nb in g.vertices[ivertex].neighbors\n", " if !visited[nb]\n", " visited[nb] = true\n", " push!( tovisit, nb )\n", " end\n", " end\n", " end\n", " \n", " while length(tovisit.data) > 0\n", " visit( pop!(tovisit) ) \n", " end\n", " return nothing\n", "end" ] }, { "cell_type": "markdown", "id": "a3c062a2", "metadata": {}, "source": [ "Now let's generate a fairly complicated graph:" ] }, { "cell_type": "code", "execution_count": 19, "id": "f5e60362", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAR4AAAGFCAYAAAAraJxWAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAA9hAAAPYQGoP6dpAAA3yUlEQVR4nO3deVxU9f4/8Ncs7GAgKiq4sIqoCI4raqap6TW7al/NVhVNuxZldStbzDJvRTfN7Vsu5HLVyqUsf5Gmpoa7MgmKuOCKGy4IIsg65/37w++Z68Iy+5w55/18PHw8ZOZ8lpkD73nNWVVERGCMMQdSO3sCjDHl4cLDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh9M6ewLMNZw7dw7btm2DXq/HX3/9hby8PFRUVMDd3R3BwcHQ6XTQ6XTo06cPmjZt6uzpMolT8Q39WE0EQcDvv/+Or7/+GqmpqSAiREVFoWPHjmjevDnc3d1RXl6OM2fOQK/X49SpU9BoNBgyZAgmTpyI3r17Q6VSOftlMCkixqpx/Phx6t69OwGguLg4WrRoERUWFtbaJj8/n+bNm0cxMTEEgPr160fnzp1z0IyZK+HCw+4hCALNmjWLPD09KSIigv744w8SBMHsPn799VcKCQkhPz8/Wrx4sZ1my1wVFx5mJAgCJSUlEQB69dVXqaSkxKr+CgsLKTExkQDQhx9+aHYBY/LFG5cZAICI8Oabb2Lu3LmYP38+JkyYYHWfDz30EL799ltERUVh8uTJcHNzwwcffGCD2TKX5+zKx6RhxYoVBIDmzZtnl/6nTZtGACg1NdUu/TPXwnu1GPLy8hATE4PHHnsM33//vV3GICIMGDAAR44cQVZWFvz9/e0yDnMNfAAhQ1JSEtzc3DB37txal1uxYgUmTJiAjh07wsPDAyqVCkuXLjVpDJVKhUWLFqGoqAhvv/22DWbNXBkXHoU7deoU1q5di08//RQNGjSoddkPPvgACxcuxLlz59CkSROzx2revDmmTJmCpUuX4urVq5ZOmckAFx6Fmz9/PgICAvDMM8/UuWxKSgrOnj2La9eu4aWXXrJovMTERGg0Gnz77bcWtWfywIVHwQwGA5YsWYIxY8bAy8urzuX79u2LFi1aWDVmYGAgRo4ciZSUFKv6Ya6NC4+CnThxAvn5+Rg0aJBDx/3b3/6G06dP48qVKw4dl0kHFx4F0+v1AIAOHTo4dNyOHTveMz5THi48CpaZmYmwsDCH79pu2bIlAgICkJGR4dBxmXRw4VGwgoICNGzY0OHjqlQqNGjQAIWFhQ4fm0kDFx4FMxgMUKud8yugVqthMBicMjZzPi48Cubl5YWSkhKnjH379m2T9qQxeeLCo2BRUVE4ceIEqqqqHDruzZs3cf78eURFRTl0XCYdXHgUTKfToaysDNnZ2Q4d9+DBg8bxmTLxZTEULD4+HiqVCrt370ZsbGydy6ekpGDnzp0AgMOHDxsf2759OwBgyJAhGDJkSJ397Nq1C97e3oiOjrZ47sy18dnpCjdo0CBcuXIFBw4cqPP6yKNHj8ayZctqfH7q1Kn46KOPau1DEARERkYiISEBy5cvt2TKTAa48ChcamoqHn/8cezbtw+dO3e2+3gbN27EwIEDsXv3bnTr1s3u4zFp4sKjcAaDAZGRkYiMjMTGjRvtelcIg8GA7t27o6KiAnq9nu9AoWC8cVnhNBoN5s2bh02bNmHJkiV2HWvmzJnYv38/5s6dy0VH4TjxMADAmDFj8NNPP0Gv1yMiIsLm/WdmZqJLly54+eWXMWPGDJv3z1wLFx4GACgsLETXrl1RVlaGtLQ0NG/e3GZ9Hz9+HL169UJwcDB27tzJBw4y/qrF7vD398fmzZuhVqvRo0cPm53AuXv3bvTs2ROBgYHYuHEjFx0GgAsPu0uzZs2wY8cO1K9fH506dcLHH3+MiooKi/oqLS3FW2+9hZ49eyIyMhJpaWlOOSGVSZRT7m3BJK28vJymTJlCKpWKfHx8aNasWVRUVGRS2xs3btC0adPI09OT3NzcKDk5mSorK+08Y+ZqeBsPq1ZeXh6Cg4MhCAIAwNfXF4MGDULHjh3RsWNHNG/eHB4eHigvL8fp06eh1+tx4MAB/PbbbygvL4cgCPD09MSlS5cQEBDg5FfDpIYLD3tAXl4eEhIScObMGQB3To9Ys2YNtmzZgoyMDNy+ffuBNr6+voiPj8djjz2Gvn37omvXrgCAdu3a4c8//+Tiw+7BhYfdIy8vDw8//DBycnIA3Ckot27dMj5fVVWFY8eO4cqVK6ioqICHhweaNm2KqKgo47V9qqqq4OHhYUxL7du3x7Zt27j4MCMuPMxILDqnT582XqSrY8eOOHDggNl9hYWFGROTRqNB27ZtufgwI96rxQBUX3TUajVat25tUX93tzMYDMjKykLv3r1RUFBgk/ky18aFh1VbdIA7hcfSo5gjIyPh5uZm/JmLD7sbFx6Fq6noAHe21URGRlrUb2Rk5ANXNuTiw0RceBSstqIjsjTxREREoLrNh1x8GMCFR9GWL1+OnJycWu/2YM1XrZoYDAZkZmZi3bp1FvXNXB8XHgV79tlnMWrUKKjVamg0mgeef+ihhyzeC9W8efNq+9RoNNBqtZgwYQKeeOIJi/pmro93pzOcPHnSmFA0Go3Vu9JFd+9SV6vVxuN6zp07Z9Oz35nr4cTDUFxcbPz/c889ZzwQ0NqLsYvttVotXnzxRePjWi3fY0DxnHSOGJMQlUpFAGjOnDlERJSTk0OTJ0+m48ePW9VvZmYmvffee3Tu3DkiInrllVcIAPn4+Fg9Z+ba+KuWwmVkZCA+Ph4Aqt0LZWviJU8vXryIpk2b2n08Jk38VUvhOnToAACYM2eOQ8Z75ZVXAIDvIqpwnHgUzNFpR8Sph3HiUTBHpx0Rpx7GiUehnJV2RJx6lI0Tj0I5K+2IOPUoGyceBXJ22hFx6lEuTjwK5Oy0I+LUo1yceBRGKmlHxKlHmTjxKIxU0o6IU48yceJREKmlHRGnHuXhxKMgUks7Ik49ysOJRyGkmnZEnHqUhROPQkg17Yg49SgLJx4FkHraEXHqUQ5OPAog9bQj4tSjHJx4ZM5V0o6IU48ycOKROVdJOyJOPcrAiUfGXC3tiDj1yB8nHhlztbQj4tQjf5x4ZMpV046IU4+8ceKRKVdNOyJOPfLGiUeGXD3tiDj1yBcnHhly9bQj4tQjX5x4ZEYuaUfEqUeeOPHIjFzSjohTjzxx4pERuaUdEace+eHEIyNySzsiTj3yw4lHJuSadkSceuSFE49MyDXtiDj1yAsnHhmQe9oRceqRD048MiD3tCPi1CMfnHhcnFLSjohTjzxw4nFxSkk7Ik498sCJx4UpLe2IOPW4Pk48LkxpaUfEqcf1ceJxUUpNOyJOPa6NE4+LUmraEXHqcW2ceFyQ0tOOiFOP6+LE44KUnnZEnHpcFyceF8Np516celwTJx4Xw2nnXpx6XBMnHhfCaad6nHpcDyceF8Jpp3qcelwPJx4XwWmndpx6XAsnHhfBaad2nHpcCyceF8BpxzScelwHJx4XwGnHNJx6XAcnHonjtGMeTj2ugROPxKSmpmLFihWoqqoCwGnHXPennoqKCnz77bfYunWrM6fF7sOJR0JKS0vh7e0NAAgLC0NiYiI++OADAJx2zCGmnhkzZmDmzJm4ePEiPD09cfv2beNzzLm48EhIVlYW2rVrB+DOH4+4aoYNG4ZVq1ZBq9U6c3ouoaKiAj179sT+/fsB3Ps+8tcv6eCvWhJy8uRJ4//v/jz46aef0KpVK6xcudIZ03IJRIRFixYhLCzMWHTEx0V3v7/MubjwSEhOTg40Gk21z50+fRrPPfccbt265eBZuYYLFy5g/PjxuHjxYo3L5OTkOHBGrDZceCQkJyen1m0QEyZMgI+PjwNn5DqaNGmCESNG1Pj+ubm5ceGREC48EnL8+HHj3qz7TZgwAV9//TXUal5l1dFqtVi5ciWGDx9ebfExGAxceCSEf4sl5Pjx49U+zkXHNLUVH0EQcPToUSfNjN2P92pJxN270u/GRcd8VVVVePbZZ7FmzZp7Ni7zLnXp4N9miTh16tQDj3HRsUxNyaesrAyXL1924syYiA8McYCqqiqcOnUKRUVFEAQBXl5eiIiIuCfh3L+rl4uOdcTiAwCrV682Pn7y5Ml7juUpLi7GqVOnUFpaCo1GA39/f4SFhdW4d5HZBhceO8nKysKSJUuwZ88eZGRkoLS09J7n1Wo1WrdujY4dO2LkyJE4cOCA8TkuOrZRXfHJyMhAQUEB1q5di/T0dBw/fvyBo8J9fHzQoUMHJCQkIDExkU86tQPexmNj69evx4wZM5CWloagoCD06dMHOp0O8fHxCAwMhFqtRnFxMbKysqDX67Fjxw5kZ2dDo9HAYDDg8ccfxy+//MJFx4aqqqqQkJCAAwcOQKvVoqqqCnFxcUhISIBOp0NMTAx8fX1hMBhw7do1/PXXX9Dr9fjjjz+Qn5+Pfv364e2330bfvn2d/VLkg5hNXLlyhYYPH04AqGfPnrRq1SoqLy+vs50gCLR7927q0qULAaB27dqRXq93wIyVY+fOnRQZGUkqlYp69+5N6enpJrUrLS2l//znP9S5c2cCQGPGjKGCggL7TlYhuPDYwLZt26hBgwYUGBhIP/zwAwmCYFE/Bw8epPbt25NGo6Evv/zSxrNUHkEQaMqUKaRSqahbt2507Ngxi/tJSUmhevXqUdOmTWn//v02nqnycOGx0oYNG8jDw4MeffRRysvLs7q/8vJyevvttwkAvf/++zaYoTIJgkATJ04kADR9+nSqqqqyus/c3Fzq2rUr+fr60o4dO2wwS+XiwmOF3bt3k6enJw0ePJjKysps2vcXX3xBADj5WOi9994jALRw4UKb9ltcXEyPPPII1atXjw4dOmTTvpWEC4+Fbt26RaGhoZSQkEClpaV2GePtt98mjUbD23zMtG3bNgJAn332mV36LyoqotjYWIqNjTVpOx57EO/VstArr7yCxYsX4/DhwwgPD7fLGBUVFejcuTOICAcOHIC7u7tdxpGT4uJixMbGIiQkBNu3b7fb3sGMjAx06tQJ7777LqZNm2aXMWTNyYXPJWVkZBAAmj17dq3LXbhwgb766ivq168fNWvWjNzc3CgoKIiGDRtGe/fuNWmsgwcPklarpZkzZ9pi6rL3wQcfkJeXF+Xk5NS6XEFBASUlJVHXrl0pKCiI3N3dqWnTptS7d29au3atSTsIpk6dShqNhk6fPm2r6SsGFx4LvPjiixQcHEyVlZW1LvfOO+8QAAoPD6fExESaPHkyPfnkk6TRaEitVtOqVatMGu/ZZ5+l8PBwMhgMtpi+bJWVlVGjRo0oKSmpzmVzcnLIx8eHHn30UZowYQK9++67NHbsWGrUqBEBoBdffLHOPkpKSuihhx6id955xxbTVxQuPGYqKCggb29vmjZtWp3L/vjjj5SWlvbA42lpaeTm5kb169c3aaP0rl27CABt3LjRojkrxXfffUcAKDs7u85lq6qqqv3gKCoqopiYGAJAWVlZdfYzadIkatCggd2288kVFx4zrVixggDQxYsXreqnf//+BIAOHDhQ57KCIFBMTAyNHj3aqjHl7oknnqDu3btb3c/rr79OAOjnn3+uc9kjR44QAEpNTbV6XCXh4/LNlJ6ejvDwcKsvGu7m5gYAJl3AXaVSoUePHkhPT7dqTLlLT09Hz549reqjrKwMW7duhUqlQkxMTJ3Lt27dGgEBAdDr9VaNqzR8kqiZ9Ho9dDqdVX3k5uZiy5YtaNy4sfGuEnXR6XRISUnB7du3q71uj9Ll5eXh0qVLZq+bwsJCzJo1C4Ig4OrVq/jtt99w/vx5TJ06FZGRkXW2V6lU0Ol0XHjMxIXHTMePH0e/fv0sbl9ZWYnnn38e5eXl+OKLL0y+/ELbtm0hCAJOnjyJ2NhYi8eXK/HqjW3btjWrXWFhIT7++GPjz25ubvj3v/+NN9980+Q+2rZtiw0bNpg1rtLxVy0z3b592+ILrguCgMTERKSlpeHFF1/E888/b3JbPz8/AHjg8hrsDvF98fX1Natdy5YtQUSoqqrCmTNnMG3aNLz//vt48skna7z+9f18fX1x+/Zts+esZFx4zKRWqy26qycR4cUXX8SKFSvw3HPPYf78+Wa1NxgMAMAXqKqBeKCgIAgWtddoNGjZsiUmT56M6dOnY926dVi0aJFJbQVB4PViJi48ZqpXrx7y8/PNaiMIAsaOHYvFixfj6aefxtKlS80+olYcU0w+7F716tUDALPXTXX69+8PANi+fbtJy+fn5xvHZ6bhwmOm2NhYHDx40OTlBUHAuHHjsGTJEjz11FNYvny5RZ+OBw8ehLe3NyIiIsxuqwRt27aFSqUya93U5NKlSwBM2+MI3Fk3vN3NPFx4zCTuwTDl65aYdJYsWYLhw4djxYoVFkdyvV6PuLg4jvQ18PX1RatWrUzeu5SRkYGbN28+8PiNGzfw3nvvAQAGDhxYZz+VlZXIzMy0ek+n0vBeLTN169YNn3zyCTIyMhAfH1/rstOmTcPSpUvh6+uLqKgoTJ8+/YFlhgwZgri4uFr7qaiowLZt2/Dss89aM3XZ69atGzZt2gRBEOr8Krt06VKkpKSgd+/eaNGiBXx8fHDu3DmkpqaiuLgYTz75JJ555pk6x0xLS0N5eTm6du1qq5ehDM49ftH1VFZWUnBwsEnn8owaNYoA1PpvyZIldfbzww8/mHwIv5Lt2LGDANCmTZtMWnb06NEUHR1N9erVI61WS40aNaIBAwbQd999Z/JVJJ988kmKiYmx+KqTSsWXxbDAJ598gs8//xwXLlxAQECAXcciIvTq1QtqtdrkjZ1KRURo3749QkND8csvv9h9vAsXLqBly5aYPXs2Xn75ZbuPJyvOrXuu6fLly+Tn50fjxo2z+1jff/89AaD169fbfSw5WLp0qUNOqBUEgYYOHUoNGzakmzdv2nUsOeLCY6EFCxbY/Rc8Ly+PAgMDacSIEXYbQ24EQaC+fftSSEgIFRYW2m0c8QNhzZo1dhtDzrjwWEgQBOrXrx81btzYLheCKisro0cffZQaNmxIV69etXn/cnb27Fny8/OjIUOG1HnNJEtkZWVRQEAAfyBYgQuPFS5fvkwREREUGhpq0+JTWlpKgwcPJg8PD9q2bZvN+lWS9evXk0ajoWeeeYYqKips1u+RI0eoSZMmFBsbSzdu3LBZv0rDhcdKZ8+epYiICGrcuLFNvnbl5ORQQkICeXl50YYNG2wwQ+VavXo1ubm5Ud++fSk3N9fq/tauXUv169en2NhYm9zKSMm48NjA5cuXqV+/fgSAxo4dS/n5+Wb3UVFRQbNmzSIvLy8KCwujPXv22GGmyrNlyxYKDg6mevXq0aJFiyy6v1ZeXh499dRTBICGDBnCSccGuPDYiCAINH/+fFKpVASAxo0bR3q9vs7jOy5evEgff/wxeXp6GtsVFxc7aNbKUFBQQGPGjCEA1LJlS/r888/pypUrtbYRBIH27NlDzz//PAEgtVpNK1eu5ON1bISP47ERQRAwatQorFixAgAQEhKCCxcuoEGDBtDpdIiPj0dgYCDUajWKi4uRlZUFvV6P06dPw8fHB1qtFjdv3kSTJk1w5MgRux8fpET79+/H119/jR9++AHl5eWIjIyETqdDmzZt4O3tDUEQcO3aNfz111/Q6/UoKChAaGgozpw5AwB4/fXXMWPGDKhUKie/EtfHhccGBEHAP/7xDyxcuBAA0LNnT2zduhWbN2/G3r17odfrcejQIRQVFcFgMMDb2xvR0dHQ6XTQ6XR4/PHHsWzZMrz22msA7pyIun37di4+dpKfn49ff/0Ver0eer0eOTk5KC0thUajgb+/P+Li4qDT6ZCQkIDevXsjJibGeKGxd955B5999hkXH2s5N3C5PoPBQOPHj7/nNIi33nrL7H42btxobK9Wq3mviYSMHTv2nvX7zjvv8FcuK/HZ6Va4P+mITLlW7/3ubiMIAo4cOYJHHnkEBQUFVs+TWScyMvKek06Tk5Px7rvvWnRBOHYHFx4L1VR0AFh0zZzmzZvfc8kLg8HAxUciIiIiHriyIRcf63DhsUBtRQewLPFotVo0b978nse4+EhDTeuTi4/luPCYqa6i4+HhYfE9t1q3bv3AY1x8nC88PLzG57j4WIYLj5kmTZpUY9EB7ty1wNzrKYsiIyONN/q7293Fh+8y4Xg+Pj5o2LBhjc8nJyffc4scVjcuPGY6fPhwjbtSVSpVtanFVJGRkbXeUuXYsWMmXweY2VarVq1qfT4rK8tBM5EHLjxm+vXXX5GcnAx/f/8HntNqtRZt3xFFRERUG9m1Wi3GjRuHnJycahMRs79WrVpVW/QbNWqEuXPnGg8cZabhj08z+fj44K233kL37t3RvXt3AHeSDhGhsrLSqsJzd1uNRmO8l1ZCQoLZ9+FithUZGWn8UBDXNwDs27cPLVu2dOLMXBMnHgv16NEDAPDFF18YE5BKpUKbNm0s7rN58+bw9fU1JpyjR48CuHNBcUtvVMdso127djAYDGjUqBHmzJmDCRMmADD/lsnsDj5lwgJ332FCfPtKSkpw4cKFOrcF1OX69eu4ffu2cdd68+bNcf78efztb39DamqqdRNnVsnOzkZYWBg8PT0BwLit79KlS2jSpIkzp+ZyuPBYQLyN8Zw5c5CUlGTXse6+V7vBYLB4jxmzvaSkJMybNw8+Pj4oLi529nRcChceM1WXduyNU490ceqxDH98mqlDhw4AgDlz5jhszGPHjgEAfvvtN97WIzGvvPIKAMuOVlcyTjxmcEbaEXHqkS5OPebjxGMGZ6QdEace6eLUYz5OPCZyZtoRceqRLk495uHEYyJnph0Rpx7p4tRjHk48JpBC2hFx6pEuTj2m48RjAimkHRGnHuni1GM6Tjx1kFLaEXHqkS5OPabhxFMHKaUdEace6eLUYxpOPLWQYtoRceqRLk49dePEUwspph0Rpx7p4tRTN048NZBy2hFx6pEuTj2148RTAymnHRGnHuni1FM7TjzVcIW0I+LUI12cemrGiacarpB2RJx6pItTT8048dzHldKOiFOPdHHqqR4nnvu4UtoRceqRLk491ePEcxdXTDsiTj3SxannQZx47uKKaUfEqUe6OPU8iBPP/3HltCPi1CNdnHruxYnn/7hy2hFx6pEuTj334sQDeaQdEace6eLU81+ceCCPtCPi1CNdnHr+S/GJR05pR8SpR7o49dyh+MQjp7Qj4tQjXZx67lB04pFj2hFx6pEuTj0KTzxyTDsiTj3SxalHwYlHzmlHxKlHupSeehSbeOScdkSceqRL6alHkYlHCWlHxKlHupScehSZeJSQdkSceqRLyalHcYlHSWlHxKlHupSaehSXeJSUdkSceqRLqalHUYlHiWlHxKlHupSYehSVeJSYdkSceqRLialHMYlHyWlHxKlHupSWehSTeJScdkSceqRLaalHEYmH085/ceqRLiWlHkUkHk47/8WpR7qUlHpkn3g47TyIU490KSX1yD7xcNp5EKce6VJK6pF14uG0UzNOPdKlhNQj68TDaadmnHqkSwmpR7aJh9NO3Tj1SJfcU49sEw+nnbpx6pEuuaceWSYeTjum49QjXXJOPbJMPJx2TMepR7rknHpcvvCcPHkSXbp0wXvvvYfr168jIyPDmHKSkpKcPDvp8/b2RrNmzQAAgwcPRkVFBRYtWoT4+HisX7/eybNTtrlz5wIASkpKcPnyZVy+fBmTJk1Cjx49cPHiRSfPzkrk4r755hsCQGq1mjw9PQkAAaA5c+Y4e2ouo6SkxPi+NW3a1Pj/YcOGOXtqivfKK68Y14e7uztpNBoCQKtWrXL21Kzi8oknJycHbm5uEAQBZWVlxscvX76M69evO3FmrqGiogIrV640/nzp0iXj/48ePeqMKbH/c/nyZWg0GuPPFRUVMBgM0Gq1yMnJceLMrOfyhefEiROoqqp64PHk5GQ0a9YMCxcudMKsXMP+/fsRFhaG8ePHV/v8mTNneOO8k3z55Zdo2bIl5s2bV+3zXHic7OjRo9X+cYgJ6JdffnHCrFzD3r17a91WUFZWhsuXLztwRky0du1aY8K5X1VVlXGngKty6cJjMBiQm5tb7XMajQaRkZH49ttvHTwr1zFx4kQ89dRTxt221Tl58qQDZ8REP/zwA4KDg6HVaqt9nhOPE124cAGVlZUPPK7RaBAWFoa0tDQ0btzYCTNzDVqtFitWrMCIESNqLD6u/gvuqlq2bImdO3ciKCio2uJz48YNFBUVOWFmtuHShae6PwouOuaprfhotVpOPE5UV/Fx5XUjq8LDRccyNRUfg8GAEydOOHFmrLbi48pp1KULz90VX61Wc9Gxwt3FR0REvEtdAu4uPmr1f/9kXTnxVL/lyonELfZ6vR4nTpxAaWkpNBoNAgIC0L59e+h0OmNhOXTokLFdeHg4Fx0ricUHAFatWgXgzqcqEUGlUqG4uBgHDx6EXq9HXl4eKioq4O7ujuDgYOh0OsTFxcHb29uZL0G2xOJz91HL2dnZAO58QFy6dAl6vR6ZmZkoKiqCIAjw9vZGq1atoNPpEBUVdc8xQU7n1MMX/48gCLRr1y569tlnydvb23ikZrNmzSg6OpqioqIoICDA+HhYWBh9+umnpFarCQCFhITQ5cuXnf0yZKOyspKGDx9ufL9nzZpF3bp1I5VKRQDI09OTwsPDqXXr1hQWFkbu7u7Go8d79epFq1atovLycme/DFk6c+aM8W/B29ubPvzwQ2rWrJlxXQUGBlJUVBS1atWKQkJCjI/7+flRYmIipaenO/slEBGR0wvPzp07KS4ujgBQeHg4/etf/6Lt27fTzZs371lOEAQ6c+YMrVmzhkaPHn3P6RHHjh1z0uzlq6ysjPz9/Y3vcb9+/SglJYUyMzOpsrLynmXLy8vpr7/+ovnz59PDDz9MACgoKIgWLFhAgiA46RXI14EDB4zrxdfXlyZMmEDr1q2j3NzcB97vGzdu0JYtW2jq1KnGAtW1a1fS6/VOmv0dTis8JSUl9Prrr5NKpaIuXbrQxo0byWAwmNw+Pz+fxo8fT76+vhQcHEypqal2nK2yHD9+nBISEggA9e3bl44ePWpW+8OHD9MLL7xgLFjnzp2z00yVZ/Xq1dSgQQPy9/enSZMmPfABXZvKykr6+eefqX379qTRaGjKlClOS6ZOKTxXrlyh+Ph48vDwoH//+99UVVVlcV+5ubn02GOPEQD65JNP+BPWSps2bSIfHx8KDw+ntLQ0q/rasGEDhYSEkL+/P+3evdtGM1QmQRDojTfeMJ68m5eXZ3Ff5eXlNHXqVNJqtdSjRw8qLCy04UxN4/DCc+3aNYqJiaGgoCDKyMiwSZ+CINC0adMIAH344Yc26VOJNm3aRO7u7jRw4EAqLi62SZ8FBQXUo0cP8vHx4eJjIUEQKCkpiQDQ7Nmzbfbhunv3bvL396dOnTpRUVGRTfo0lUMLT2VlJSUkJFDDhg3tsl0mOTmZANDixYtt3rfcZWdnk7e3Nw0cONDm8bukpIR69OhBAQEB/LXLAjNmzCAAtGDBApv3rdfrqV69ejRw4ECHfltwaOH5/PPPSa1W065du+w2RmJiIvn5+fEvuBkqKyupc+fO1KpVKyopKbHLGAUFBRQSEkL9+vXjr8NmyM7OJg8PD3rzzTftNsZvv/1GAGjhwoV2G+N+Dis82dnZ5O7uTm+99ZZdxyksLORfcDOJHwh79uyx6zgbNmxw+C+4KxM/EKKjo6m0tNSuY40dO9ahH9gOKzxPPfUUhYWF0e3bt81uK36FAmDSH8f/+3//jwDQ1q1bLZmqoty6dYv8/PzotddeM2n5Fi1aGNfF/f8mTJhQZ/vnn3+eGjduTBUVFVbOXP7Wrl1LAGjnzp11LrtkyZIa14v4r0+fPjW2LywspKCgIPrHP/5hy5dQI4fcZSIvLw/NmjXDl19+iddee82stkePHkV8fDy0Wi1KSkqwZ88edO3atdY2RIQ2bdqgTZs2WLNmjTVTl70FCxZg4sSJOHPmDJo3b17n8i1btkRhYSEmTZr0wHMdO3bE448/Xmv7w4cPIzY2FqtXr8bw4cMtnbYiPProoygvL8fOnTvrXDYjIwM///xztc+tXbsWR44cQXJyMt5+++0a+5g6dSpmzpyJixcvol69epZO2zSOqG6ffPIJeXl5UUFBgVntqqqqqFOnTtS5c2d67rnnTE48RERz584ljUZDFy9etGDGyhEbG0tDhgwxefkWLVpQixYtrBqzZ8+e9Mgjj1jVh9wdPXqUANDKlSut6qe8vJwCAwNJq9XWuQv+/PnzpNFo6H//93+tGtMUDjlJ9Pfff8egQYPg7+9vVrvk5GRkZmZi8eLFZp9n8vTTT8NgMGDbtm1mtVOSvLw8HDp0CM8884xDx33mmWeQlpaG27dvO3RcV7J582a4u7tj2LBhVvWzbt065Ofn4/HHH0dQUFCty4aEhKBXr174/fffrRrTFHYvPAaDAQcPHkSnTp3MapeVlYWPP/4YH3zwAdq0aWP2uIGBgQgLC4Nerze7rVKI742566a8vBzLli3Dp59+im+++QaZmZlmte/cuTMEQTC7nZLo9XrExsbC09PTqn7EK3COGzfOpOU7derkkL8Zu5+dfuLECZSUlECn05ncpqqqCqNHj0br1q0xefJki8fW6XRceGqh1+tRv359tGjRwqx2eXl5GD169D2PDRgwAMuXL0eDBg3qbN+2bVu4u7tDr9ejW7duZo2tFHq9Ht27d7eqj3PnzuGPP/5AcHAwBgwYYFIbnU6H5ORkXLlypc6EZA27Jx7xdimhoaEmt/n000+NX7Hc3NwsHjs0NNT1b3xmRxcvXkRoaGit11y+X2JiIrZv345r166hqKgIe/fuxcCBA7Fx40Y88cQTJt2VQryUBq+bmonrxhpLliyBIAgYM2aMyZsqwsLCANx7myN7sHviKS8vBwCTI2NmZiamT5+Of/7zn8ZbEVvKw8PDOD57UEVFBTw8PMxq8+GHH97zc5cuXfDrr7+iV69e2LlzJ3777TcMGjSozn543dTOknVzN0EQsGTJEqhUKiQmJprcThzT3uvG7onH3d0dgOkvZNSoUQgPD8dHH31k9djWrjy5c3d3R0VFhdX9qNVqjBkzBgCwa9cuk9rwuqmdtetm8+bNyM3NRZ8+fcxKTuLfqfh3ay92TzziFQFzc3NNegPEDY41JSRxm8C6deswZMiQWvvKzc216/dUV9e4cWPk5uYarzBoDXHbjil7qiorK3Hx4kW+WmQtxHVjKXM3KovEMe29buxeeKKjo+Hl5YX09HT06tWrzuXHjh1b7eNpaWnIycnBE088gYYNG6Jly5Z19pWenm7yRjUl0ul0uHr1Ki5cuIBmzZpZ1de+ffsAwKT1kp2djfLycrN2OChNhw4dkJ6eblHb/Px8/PLLL6hfvz6GDh1qVtv09HQ0btwYTZs2tWhsk9n9SCEi6tatG40cOdKqPkaNGmXWAYSFhYUEgJYuXWrVuHJ24cIFAkA//fSTScsfOXKk2oNAd+zYQZ6enuTh4WHSuT4pKSmkUqno1q1b5k5ZMWbOnEmenp4WnVry1VdfEQB69dVXzW7bv39/GjRokNntzOWQAwj79u2L1NRU3Lp1yxHDAQBWr14NlUqF3r17O2xMV9O0aVNER0cbL+xel9WrV6Np06YYPHgwkpKS8M9//hMDBgzAww8/jMrKSsybN8+k0y5++OEHdOvWDb6+vta+BNnq27cvysrKsH79erPbWvo168qVK9i2bRv69u1r9phms3tpoztXCVSr1fTNN99Y3Ic5iUcQBIqLi6PBgwdbPJ5SzJ49m7RaLV26dKnOZbdv304jRoygiIgI8vPzIzc3NwoJCaGRI0fSvn37TBrv2LFjBICWL19u7dRlr3v37rWe2Fmdffv2EQDq3Lmz2eP961//Ii8vL7px44bZbc3lsLPThwwZQtHR0Q45K/mPP/4gALRhwwa7j+XqCgoKyNvbmyZPnuyQ8SZMmECBgYF2v8yDHKxcuZIAOOTC7MXFxRQSEkKJiYl2H4vIgYXnr7/+Io1GQx999JFdxykuLqbw8HDq3r27WRePV7IpU6aQVqu12aVoa/Lnn38SAJo5c6Zdx5GL8vJyateuHcXFxdn9A/vVV18lLy8vOnHihF3HETn0CoTiL/jBgwftNoaj30A5uPsX3F53HSguLqawsDDq3r27VRf3Vxq9Xk8ajYamTp1qtzHED4SvvvrKbmPcz6GFp7y8nNq3b0/NmjWjs2fP2rz/+fPnGy+Izcyj1+vJ3d2dRowYYfPCUF5eTgMGDCAfHx/+QLDA1KlTSaVS0ffff2/zvo8ePUoNGjSgnj17OvQDweF3mbhw4QKFhoZSixYtKCcnx2b9zp0717gLkS95apkff/yR1Go1jRgxwmbJp6SkhAYOHEju7u60efNmm/SpNAaDgV544QXSaDT0n//8x2b9Hjp0iIKCgigmJoauX79us35N4ZT7auXm5lKrVq2oXr16lJKSYlWhuHbtGj311FMEgN544w0uOlb68ccfyd3dndq3b2/1V+Ldu3dTq1atyMfHh4uOlaqqqigxMZEA0NixY626F5bBYKBZs2aRl5cXxcfH05UrV2w4U9M47U6iBQUFNGbMGAJA/fv3p71795pVNEpKSmjRokXUsGFDql+/Pn333XdcdGxEr9dTu3btSK1W09NPP232VRzPnTtHr776KqnVaurSpQtlZ2fbaabKIggCLVy4kPz8/CgkJISWL19OZWVlZrX/888/qUePHgSAkpKSbHb/NHM5/d7pqampFBoaSgCoQ4cO9PXXX1NGRka1W/HF+0C/8cYbFBAQQCqViv7nf/6HLl++7ISZy1tpaSk1aNCAABi/fv3444/V3p9bEAQ6ffo0rVq1iv7+97+TWq0mPz8/Sk5OfuA+68x6586do0GDBhEAatiwIU2ePJm2bdtW7e2My8vLSa/X0+zZs6lNmzYEgKKjo2nbtm2On/hdnF54iO7EyNTUVBo0aBCp1WoCQJ6enhQbG0tdu3alzp07G4sTAAoMDKS3336bTp065eypy5LBYKDx48cb3++pU6dSdHS08eeGDRuSTqejbt26UYcOHah+/frG59q3b08LFizg0yEcIDs7m1599VV66KGHjO9/eHg4de7cmbp27Upt27Yld3d3AkAajYaGDRtGW7ZskcQ3A4fcZcIcxcXFyMjIgF6vx4kTJ1BaWgqNRgN/f3/ExcVBp9MhKioKarVDzvZQHEEQMHHiRCxYsAAAoNFoUFFRAbVajUuXLkGv1yM9PR1XrlxBeXk5PDw8EBwcDJ1OB51Ox1cDcAKDwYBjx45Br9cjMzMTRUVFMBgM8Pb2RnR0NHQ6Hdq3bw9vb29nT9VIcoWHOc/9RQcAoqKicPz4cSfOiskRxwYGoPqiAwAxMTFOmhGTMy48rMai4+bmhsjISCfNiskZFx6Fq6noAHeuFMiFh9kDFx4Fq63oiCIiIhw4I6YUXHgUbMGCBbUWHQCceJhdcOFRsLZt28Lf37/GC727u7vb/9q7TJG48ChYz549cf78eSQnJ1f7fGhoKB8vxeyCf6sUztfXF6+99prx57sTUHR0tLOmxWSOCw9DXFwcACAhIcGYgFq0aIGRI0c6d2JMtvjIZYW7+46elZWV0Grtfqs1xjjxKN3daYeLDnMUTjwKxmmHOQsnHgXjtMOchROPQnHaYc7EiUehOO0wZ+LEo0CcdpizceJRIE47zNk48SgMpx0mBZx4FIbTDpMCTjwKwmmHSQUnHgXhtMOkghOPQnDaYVLCiUchOO0wKeHEowCcdpjUcOJRAE47TGo48cgcpx0mRZx4ZI7TDpMiTjwyxmmHSRUnHhnjtMOkihOPTHHaYVLGiUemOO0wKePEI0OcdpjUceKRIU47TOo48cgMpx3mCjjxyAynHeYKOPHICKcd5io48cgIpx3mKjjxyASnHeZKOPHIBKcd5ko48cgApx3majjxyACnHeZqOPG4OE47zBVx4nFxnHaYK+LE48I47TBXxYnHhXHaYa6KE4+L4rTDXBknHhfFaYe5Mk48LojTDnN1nHhcEKcd5uo48bgYTjtMDjjxuBhOO0wOOPG4EE47TC448bgQTjtMLjjxuAhOO0xOOPG4CE47TE448bgATjtMbjjxuABOO0xuOPFIHKcdJkeceCSmuLgY+fn5xp857TA54sQjIQaDAUFBQbh9+zYmTZqEpKQkNG3aFACnHSYvXHgk5OzZswgNDQUAqNVqCIIAAOjYsSMOHDjgzKkxZlP8VUtCTp48afy/WHQAICsrC++99x6uX7/ujGkxZnNceCQkJycHKpXqgcfLysqQnJyMli1boqqqygkzY8y2uPBIyMmTJ2vcjqNSqdCkSRNUVFQ4eFaM2R4XHgk5ceJEtYlGo9EgNDQUO3bsgLe3txNmxphtceGRkKNHj+L+bf13F53GjRs7aWaM2Rbv1ZIIg8EAT0/PexIPFx0mV5x4JOL8+fP3FB21Ws1Fh8kWFx6JuHtXukqlQlhYGBcdJlt8KKydEBH27duHPXv2QK/X49ChQygqKoIgCPD29karVq2g0+nQsWNH9OnTB8ePHze25aLD5I638djYzZs3sXz5cnz99dc4evQoPD090b59e8THxyMwMBAqlQolJSXIysqCXq/HjRs30KBBA6hUKly7dg0BAQHIzs7mosNkjROPDa1ZswYTJ05EQUEBhg4dinnz5uHhhx+u8dgcIsLRo0eRkpKCuXPnAgBGjRqF+vXrO3LajDkeMavduHGDhg8fTgDoySefpPPnz5vdR1FREX300Uek1WqpXbt2dOjQITvMlDFp4K9aVrpy5Qr69++P8+fP45tvvsGIESOqPe3BVBkZGRg1ahTOnj2L1NRU9OjRw4azZUwauPBY4caNG3jkkUdw/fp1bNmyBTExMTbp99atW3jiiSeQnp6OrVu3olOnTjbplzGp4MJjISLC0KFDsWPHDuzYscNmRUdUUlKCvn374vz588jKyoK/v79N+2fMmfg4Hgt9//33+OWXX5CSkmLzogMAPj4+WL16NYqKivDGG2/YvH/GnIkLjwXy8/ORlJSEkSNHYujQoSa1WbduHfr164fAwEB4eXkhNDQUTz/9NM6fP19jm2bNmmHmzJlYsmQJtmzZYqvpM+Z0/FXLAl988QU+/PBD5ObmolGjRrUuS0R46aWXsHDhQoSHh+Oxxx6Dn58fLl26hD///BMrV66sdQMyEaFLly4ICAjA77//buuXwphzOGlvmsuqqqqi0NBQeuGFF0xafvbs2QSAXn75Zaqqqnrg+crKyjr7WLZsGQGgEydOmD1fxqSIE4+ZtmzZgn79+mHPnj3o2rVrrcuWlpYiJCQE/v7+OH78uMUXay8rK0NISAjGjRuHzz//3KI+GJMSPnLZTLt370b9+vXRpUuXOpfdvHkzbty4gdGjR8NgMGD9+vU4ceIE/P390bdvX0RERJg0pqenJ/r06YPdu3dbO33GJIELj5n0ej10Op1JBwmmp6cDALRaLdq3b3/PiaBqtRqvv/46vvzyS5PG1el0mD59OgRBgFrN+wSYa+PfYDNlZmaiQ4cOJi179epVAMCMGTNQr1497N+/H7du3UJaWhqioqIwY8YMfPPNNyb11aFDBxQXF+PUqVMWz50xqeDCY6aCggI0bNjQpGXFW9S4u7vj559/RqdOneDr64uePXti7dq1UKvVmDFjhkl9iWPevHnTsokzJiFceMxkMBhM/qrz0EMPAbhzQz7xjqCiNm3aICwsDKdOnUJhYWGdfWk0GuP4jLk6Ljxm8vLyQklJiUnLtmrVCgBqPN1BfLy0tLTOvsQxPT09TRqbMSnjwmOmyMhIZGdnm7Rs7969Ady5e8T9KisrcfLkSfj4+Jj01e3IkSNQqVQIDw83b8KMSRAXHjPpdDro9XqTlg0PD0f//v1x8uRJpKSk3PPc559/jsLCQgwdOtSk43v0ej2io6Ph6+tr0bwZkxI+gNBMy5Ytw+jRo3H16lWTksqpU6eQkJCAq1evYtCgQYiOjsbBgwexdetWtGjRAnv37jXpMqdxcXFo164dli9fbouXwZhTceIx06BBg+Dh4YElS5aYtHx4eDjS09MxevRo6PV6zJkzBzk5OXj55Zexf/9+k4pOeno6MjMzMXz4cGunz5gkcOKxwKhRo7Bjxw7k5OQY9zbZ09ixY7FlyxacPn3aIeMxZm+ceCzw8ssv48yZM1i6dKndxzp27BhWrlyJl156iYsOkw1OPBYaM2YMfvrpJ2RlZaFZs2Z2GcNgMKBHjx64ceMGMjIy4OXlZZdxGHM0TjwW+uqrr+Dn54fExERUVlbaZYzPPvsM+/btw+LFi7noMFnhwmMhf39/LFu2DH/++SfGjBlzz33PbWHRokWYMmUKpkyZgu7du9u0b8acznmXApKH1atXk0ajoSFDhlBhYaHV/RkMBvrss8+MFw8TBMEGs2RMWrjw2MD69evJz8+PQkJCaOPGjRb3k5OTQz169CAA9P7773PRYbLFX7VsYPDgwcjKykLr1q0xYMAA/P3vf8emTZuMZ6fXJTs7G0lJSYiNjcWlS5ewfft2TJ8+3aobAzImZbxXy4aICMuXL8eXX36Jw4cPIyIiAv369YNOp0N8fDwCAwOh0Whw69YtZGVlQa/XY+fOndi1axeCgoIwfvx4vPPOO/Dx8XH2S2HMrrjw2AERYffu3fj222+xd+9eHDt2DNW9zcHBwejYsSNGjhyJYcOGwd3d3QmzZczxuPA4QHFxMbKysnDr1i0YDAZ4eXkhOjoaQUFBzp4aY07BhYcx5nC8cZkx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZw/x8nEnGdEOQgngAAAABJRU5ErkJggg==", "text/plain": [ "Figure(PyObject
)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "v1 = Vertex([2,3], coordinates=[0,0])\n", "v2 = Vertex([1,4,5], coordinates=[-0.5,-1])\n", "v3 = Vertex([1,7], coordinates=[0.5,-1])\n", "v4 = Vertex([2], coordinates=[-1,-2])\n", "v5 = Vertex([2,6], coordinates=[0,-2])\n", "v6 = Vertex([5], coordinates=[-0.5,-3])\n", "v7 = Vertex([3], coordinates=[1,-2])\n", "g = Graph([v1,v2,v3,v4,v5,v6,v7])\n", "\n", "plot(g)" ] }, { "cell_type": "markdown", "id": "838953c8", "metadata": {}, "source": [ "Let's now run DFS:" ] }, { "cell_type": "code", "execution_count": 20, "id": "915dfb9a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Visiting vertex #1\n", "Visiting vertex #3\n", "Visiting vertex #7\n", "Visiting vertex #2\n", "Visiting vertex #5\n", "Visiting vertex #6\n", "Visiting vertex #4\n" ] } ], "source": [ "dfs(g, 1)" ] }, { "cell_type": "code", "execution_count": 21, "id": "34e13e99", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Neighbors = [2, 3]" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g.vertices[1]" ] }, { "cell_type": "markdown", "id": "a5b2752f", "metadata": {}, "source": [ "The second algorithm we will cover is breadth first search, or BFS. This instead of search all the way down the path of neighbours will search all neighbours of 1, then neighbours of those, and so on." ] }, { "cell_type": "code", "execution_count": 22, "id": "e865420f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "bfs (generic function with 1 method)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function bfs(g::Graph, start)\n", " visited = falses(length(g.vertices))\n", " tovisit = Queue( [start] )\n", " function visit(ivertex)\n", " visited[ivertex] = true\n", " println(\"Visiting vertex #$ivertex\")\n", " for nb in g.vertices[ivertex].neighbors\n", " if !visited[nb]\n", " visited[nb] = true\n", " push!( tovisit, nb )\n", " end\n", " end\n", " end\n", " \n", " while length(tovisit.data) > 0\n", " visit( pop!(tovisit) ) \n", " end\n", " return nothing\n", "end" ] }, { "cell_type": "code", "execution_count": 23, "id": "d4d61917", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAR4AAAGFCAYAAAAraJxWAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAA9hAAAPYQGoP6dpAAA3yUlEQVR4nO3deVxU9f4/8Ncs7GAgKiq4sIqoCI4raqap6TW7al/NVhVNuxZldStbzDJvRTfN7Vsu5HLVyqUsf5Gmpoa7MgmKuOCKGy4IIsg65/37w++Z68Iy+5w55/18PHw8ZOZ8lpkD73nNWVVERGCMMQdSO3sCjDHl4cLDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh+PCwxhzOC48jDGH48LDGHM4LjyMMYfjwsMYczguPIwxh9M6ewLMNZw7dw7btm2DXq/HX3/9hby8PFRUVMDd3R3BwcHQ6XTQ6XTo06cPmjZt6uzpMolT8Q39WE0EQcDvv/+Or7/+GqmpqSAiREVFoWPHjmjevDnc3d1RXl6OM2fOQK/X49SpU9BoNBgyZAgmTpyI3r17Q6VSOftlMCkixqpx/Phx6t69OwGguLg4WrRoERUWFtbaJj8/n+bNm0cxMTEEgPr160fnzp1z0IyZK+HCw+4hCALNmjWLPD09KSIigv744w8SBMHsPn799VcKCQkhPz8/Wrx4sZ1my1wVFx5mJAgCJSUlEQB69dVXqaSkxKr+CgsLKTExkQDQhx9+aHYBY/LFG5cZAICI8Oabb2Lu3LmYP38+JkyYYHWfDz30EL799ltERUVh8uTJcHNzwwcffGCD2TKX5+zKx6RhxYoVBIDmzZtnl/6nTZtGACg1NdUu/TPXwnu1GPLy8hATE4PHHnsM33//vV3GICIMGDAAR44cQVZWFvz9/e0yDnMNfAAhQ1JSEtzc3DB37txal1uxYgUmTJiAjh07wsPDAyqVCkuXLjVpDJVKhUWLFqGoqAhvv/22DWbNXBkXHoU7deoU1q5di08//RQNGjSoddkPPvgACxcuxLlz59CkSROzx2revDmmTJmCpUuX4urVq5ZOmckAFx6Fmz9/PgICAvDMM8/UuWxKSgrOnj2La9eu4aWXXrJovMTERGg0Gnz77bcWtWfywIVHwQwGA5YsWYIxY8bAy8urzuX79u2LFi1aWDVmYGAgRo4ciZSUFKv6Ya6NC4+CnThxAvn5+Rg0aJBDx/3b3/6G06dP48qVKw4dl0kHFx4F0+v1AIAOHTo4dNyOHTveMz5THi48CpaZmYmwsDCH79pu2bIlAgICkJGR4dBxmXRw4VGwgoICNGzY0OHjqlQqNGjQAIWFhQ4fm0kDFx4FMxgMUKud8yugVqthMBicMjZzPi48Cubl5YWSkhKnjH379m2T9qQxeeLCo2BRUVE4ceIEqqqqHDruzZs3cf78eURFRTl0XCYdXHgUTKfToaysDNnZ2Q4d9+DBg8bxmTLxZTEULD4+HiqVCrt370ZsbGydy6ekpGDnzp0AgMOHDxsf2759OwBgyJAhGDJkSJ397Nq1C97e3oiOjrZ47sy18dnpCjdo0CBcuXIFBw4cqPP6yKNHj8ayZctqfH7q1Kn46KOPau1DEARERkYiISEBy5cvt2TKTAa48ChcamoqHn/8cezbtw+dO3e2+3gbN27EwIEDsXv3bnTr1s3u4zFp4sKjcAaDAZGRkYiMjMTGjRvtelcIg8GA7t27o6KiAnq9nu9AoWC8cVnhNBoN5s2bh02bNmHJkiV2HWvmzJnYv38/5s6dy0VH4TjxMADAmDFj8NNPP0Gv1yMiIsLm/WdmZqJLly54+eWXMWPGDJv3z1wLFx4GACgsLETXrl1RVlaGtLQ0NG/e3GZ9Hz9+HL169UJwcDB27tzJBw4y/qrF7vD398fmzZuhVqvRo0cPm53AuXv3bvTs2ROBgYHYuHEjFx0GgAsPu0uzZs2wY8cO1K9fH506dcLHH3+MiooKi/oqLS3FW2+9hZ49eyIyMhJpaWlOOSGVSZRT7m3BJK28vJymTJlCKpWKfHx8aNasWVRUVGRS2xs3btC0adPI09OT3NzcKDk5mSorK+08Y+ZqeBsPq1ZeXh6Cg4MhCAIAwNfXF4MGDULHjh3RsWNHNG/eHB4eHigvL8fp06eh1+tx4MAB/PbbbygvL4cgCPD09MSlS5cQEBDg5FfDpIYLD3tAXl4eEhIScObMGQB3To9Ys2YNtmzZgoyMDNy+ffuBNr6+voiPj8djjz2Gvn37omvXrgCAdu3a4c8//+Tiw+7BhYfdIy8vDw8//DBycnIA3Ckot27dMj5fVVWFY8eO4cqVK6ioqICHhweaNm2KqKgo47V9qqqq4OHhYUxL7du3x7Zt27j4MCMuPMxILDqnT582XqSrY8eOOHDggNl9hYWFGROTRqNB27ZtufgwI96rxQBUX3TUajVat25tUX93tzMYDMjKykLv3r1RUFBgk/ky18aFh1VbdIA7hcfSo5gjIyPh5uZm/JmLD7sbFx6Fq6noAHe21URGRlrUb2Rk5ANXNuTiw0RceBSstqIjsjTxREREoLrNh1x8GMCFR9GWL1+OnJycWu/2YM1XrZoYDAZkZmZi3bp1FvXNXB8XHgV79tlnMWrUKKjVamg0mgeef+ihhyzeC9W8efNq+9RoNNBqtZgwYQKeeOIJi/pmro93pzOcPHnSmFA0Go3Vu9JFd+9SV6vVxuN6zp07Z9Oz35nr4cTDUFxcbPz/c889ZzwQ0NqLsYvttVotXnzxRePjWi3fY0DxnHSOGJMQlUpFAGjOnDlERJSTk0OTJ0+m48ePW9VvZmYmvffee3Tu3DkiInrllVcIAPn4+Fg9Z+ba+KuWwmVkZCA+Ph4Aqt0LZWviJU8vXryIpk2b2n08Jk38VUvhOnToAACYM2eOQ8Z75ZVXAIDvIqpwnHgUzNFpR8Sph3HiUTBHpx0Rpx7GiUehnJV2RJx6lI0Tj0I5K+2IOPUoGyceBXJ22hFx6lEuTjwK5Oy0I+LUo1yceBRGKmlHxKlHmTjxKIxU0o6IU48yceJREKmlHRGnHuXhxKMgUks7Ik49ysOJRyGkmnZEnHqUhROPQkg17Yg49SgLJx4FkHraEXHqUQ5OPAog9bQj4tSjHJx4ZM5V0o6IU48ycOKROVdJOyJOPcrAiUfGXC3tiDj1yB8nHhlztbQj4tQjf5x4ZMpV046IU4+8ceKRKVdNOyJOPfLGiUeGXD3tiDj1yBcnHhly9bQj4tQjX5x4ZEYuaUfEqUeeOPHIjFzSjohTjzxx4pERuaUdEace+eHEIyNySzsiTj3yw4lHJuSadkSceuSFE49MyDXtiDj1yAsnHhmQe9oRceqRD048MiD3tCPi1CMfnHhcnFLSjohTjzxw4nFxSkk7Ik498sCJx4UpLe2IOPW4Pk48LkxpaUfEqcf1ceJxUUpNOyJOPa6NE4+LUmraEXHqcW2ceFyQ0tOOiFOP6+LE44KUnnZEnHpcFyceF8Np516celwTJx4Xw2nnXpx6XBMnHhfCaad6nHpcDyceF8Jpp3qcelwPJx4XwWmndpx6XAsnHhfBaad2nHpcCyceF8BpxzScelwHJx4XwGnHNJx6XAcnHonjtGMeTj2ugROPxKSmpmLFihWoqqoCwGnHXPennoqKCnz77bfYunWrM6fF7sOJR0JKS0vh7e0NAAgLC0NiYiI++OADAJx2zCGmnhkzZmDmzJm4ePEiPD09cfv2beNzzLm48EhIVlYW2rVrB+DOH4+4aoYNG4ZVq1ZBq9U6c3ouoaKiAj179sT+/fsB3Ps+8tcv6eCvWhJy8uRJ4//v/jz46aef0KpVK6xcudIZ03IJRIRFixYhLCzMWHTEx0V3v7/MubjwSEhOTg40Gk21z50+fRrPPfccbt265eBZuYYLFy5g/PjxuHjxYo3L5OTkOHBGrDZceCQkJyen1m0QEyZMgI+PjwNn5DqaNGmCESNG1Pj+ubm5ceGREC48EnL8+HHj3qz7TZgwAV9//TXUal5l1dFqtVi5ciWGDx9ebfExGAxceCSEf4sl5Pjx49U+zkXHNLUVH0EQcPToUSfNjN2P92pJxN270u/GRcd8VVVVePbZZ7FmzZp7Ni7zLnXp4N9miTh16tQDj3HRsUxNyaesrAyXL1924syYiA8McYCqqiqcOnUKRUVFEAQBXl5eiIiIuCfh3L+rl4uOdcTiAwCrV682Pn7y5Ml7juUpLi7GqVOnUFpaCo1GA39/f4SFhdW4d5HZBhceO8nKysKSJUuwZ88eZGRkoLS09J7n1Wo1WrdujY4dO2LkyJE4cOCA8TkuOrZRXfHJyMhAQUEB1q5di/T0dBw/fvyBo8J9fHzQoUMHJCQkIDExkU86tQPexmNj69evx4wZM5CWloagoCD06dMHOp0O8fHxCAwMhFqtRnFxMbKysqDX67Fjxw5kZ2dDo9HAYDDg8ccfxy+//MJFx4aqqqqQkJCAAwcOQKvVoqqqCnFxcUhISIBOp0NMTAx8fX1hMBhw7do1/PXXX9Dr9fjjjz+Qn5+Pfv364e2330bfvn2d/VLkg5hNXLlyhYYPH04AqGfPnrRq1SoqLy+vs50gCLR7927q0qULAaB27dqRXq93wIyVY+fOnRQZGUkqlYp69+5N6enpJrUrLS2l//znP9S5c2cCQGPGjKGCggL7TlYhuPDYwLZt26hBgwYUGBhIP/zwAwmCYFE/Bw8epPbt25NGo6Evv/zSxrNUHkEQaMqUKaRSqahbt2507Ngxi/tJSUmhevXqUdOmTWn//v02nqnycOGx0oYNG8jDw4MeffRRysvLs7q/8vJyevvttwkAvf/++zaYoTIJgkATJ04kADR9+nSqqqqyus/c3Fzq2rUr+fr60o4dO2wwS+XiwmOF3bt3k6enJw0ePJjKysps2vcXX3xBADj5WOi9994jALRw4UKb9ltcXEyPPPII1atXjw4dOmTTvpWEC4+Fbt26RaGhoZSQkEClpaV2GePtt98mjUbD23zMtG3bNgJAn332mV36LyoqotjYWIqNjTVpOx57EO/VstArr7yCxYsX4/DhwwgPD7fLGBUVFejcuTOICAcOHIC7u7tdxpGT4uJixMbGIiQkBNu3b7fb3sGMjAx06tQJ7777LqZNm2aXMWTNyYXPJWVkZBAAmj17dq3LXbhwgb766ivq168fNWvWjNzc3CgoKIiGDRtGe/fuNWmsgwcPklarpZkzZ9pi6rL3wQcfkJeXF+Xk5NS6XEFBASUlJVHXrl0pKCiI3N3dqWnTptS7d29au3atSTsIpk6dShqNhk6fPm2r6SsGFx4LvPjiixQcHEyVlZW1LvfOO+8QAAoPD6fExESaPHkyPfnkk6TRaEitVtOqVatMGu/ZZ5+l8PBwMhgMtpi+bJWVlVGjRo0oKSmpzmVzcnLIx8eHHn30UZowYQK9++67NHbsWGrUqBEBoBdffLHOPkpKSuihhx6id955xxbTVxQuPGYqKCggb29vmjZtWp3L/vjjj5SWlvbA42lpaeTm5kb169c3aaP0rl27CABt3LjRojkrxXfffUcAKDs7u85lq6qqqv3gKCoqopiYGAJAWVlZdfYzadIkatCggd2288kVFx4zrVixggDQxYsXreqnf//+BIAOHDhQ57KCIFBMTAyNHj3aqjHl7oknnqDu3btb3c/rr79OAOjnn3+uc9kjR44QAEpNTbV6XCXh4/LNlJ6ejvDwcKsvGu7m5gYAJl3AXaVSoUePHkhPT7dqTLlLT09Hz549reqjrKwMW7duhUqlQkxMTJ3Lt27dGgEBAdDr9VaNqzR8kqiZ9Ho9dDqdVX3k5uZiy5YtaNy4sfGuEnXR6XRISUnB7du3q71uj9Ll5eXh0qVLZq+bwsJCzJo1C4Ig4OrVq/jtt99w/vx5TJ06FZGRkXW2V6lU0Ol0XHjMxIXHTMePH0e/fv0sbl9ZWYnnn38e5eXl+OKLL0y+/ELbtm0hCAJOnjyJ2NhYi8eXK/HqjW3btjWrXWFhIT7++GPjz25ubvj3v/+NN9980+Q+2rZtiw0bNpg1rtLxVy0z3b592+ILrguCgMTERKSlpeHFF1/E888/b3JbPz8/AHjg8hrsDvF98fX1Natdy5YtQUSoqqrCmTNnMG3aNLz//vt48skna7z+9f18fX1x+/Zts+esZFx4zKRWqy26qycR4cUXX8SKFSvw3HPPYf78+Wa1NxgMAMAXqKqBeKCgIAgWtddoNGjZsiUmT56M6dOnY926dVi0aJFJbQVB4PViJi48ZqpXrx7y8/PNaiMIAsaOHYvFixfj6aefxtKlS80+olYcU0w+7F716tUDALPXTXX69+8PANi+fbtJy+fn5xvHZ6bhwmOm2NhYHDx40OTlBUHAuHHjsGTJEjz11FNYvny5RZ+OBw8ehLe3NyIiIsxuqwRt27aFSqUya93U5NKlSwBM2+MI3Fk3vN3NPFx4zCTuwTDl65aYdJYsWYLhw4djxYoVFkdyvV6PuLg4jvQ18PX1RatWrUzeu5SRkYGbN28+8PiNGzfw3nvvAQAGDhxYZz+VlZXIzMy0ek+n0vBeLTN169YNn3zyCTIyMhAfH1/rstOmTcPSpUvh6+uLqKgoTJ8+/YFlhgwZgri4uFr7qaiowLZt2/Dss89aM3XZ69atGzZt2gRBEOr8Krt06VKkpKSgd+/eaNGiBXx8fHDu3DmkpqaiuLgYTz75JJ555pk6x0xLS0N5eTm6du1qq5ehDM49ftH1VFZWUnBwsEnn8owaNYoA1PpvyZIldfbzww8/mHwIv5Lt2LGDANCmTZtMWnb06NEUHR1N9erVI61WS40aNaIBAwbQd999Z/JVJJ988kmKiYmx+KqTSsWXxbDAJ598gs8//xwXLlxAQECAXcciIvTq1QtqtdrkjZ1KRURo3749QkND8csvv9h9vAsXLqBly5aYPXs2Xn75ZbuPJyvOrXuu6fLly+Tn50fjxo2z+1jff/89AaD169fbfSw5WLp0qUNOqBUEgYYOHUoNGzakmzdv2nUsOeLCY6EFCxbY/Rc8Ly+PAgMDacSIEXYbQ24EQaC+fftSSEgIFRYW2m0c8QNhzZo1dhtDzrjwWEgQBOrXrx81btzYLheCKisro0cffZQaNmxIV69etXn/cnb27Fny8/OjIUOG1HnNJEtkZWVRQEAAfyBYgQuPFS5fvkwREREUGhpq0+JTWlpKgwcPJg8PD9q2bZvN+lWS9evXk0ajoWeeeYYqKips1u+RI0eoSZMmFBsbSzdu3LBZv0rDhcdKZ8+epYiICGrcuLFNvnbl5ORQQkICeXl50YYNG2wwQ+VavXo1ubm5Ud++fSk3N9fq/tauXUv169en2NhYm9zKSMm48NjA5cuXqV+/fgSAxo4dS/n5+Wb3UVFRQbNmzSIvLy8KCwujPXv22GGmyrNlyxYKDg6mevXq0aJFiyy6v1ZeXh499dRTBICGDBnCSccGuPDYiCAINH/+fFKpVASAxo0bR3q9vs7jOy5evEgff/wxeXp6GtsVFxc7aNbKUFBQQGPGjCEA1LJlS/r888/pypUrtbYRBIH27NlDzz//PAEgtVpNK1eu5ON1bISP47ERQRAwatQorFixAgAQEhKCCxcuoEGDBtDpdIiPj0dgYCDUajWKi4uRlZUFvV6P06dPw8fHB1qtFjdv3kSTJk1w5MgRux8fpET79+/H119/jR9++AHl5eWIjIyETqdDmzZt4O3tDUEQcO3aNfz111/Q6/UoKChAaGgozpw5AwB4/fXXMWPGDKhUKie/EtfHhccGBEHAP/7xDyxcuBAA0LNnT2zduhWbN2/G3r17odfrcejQIRQVFcFgMMDb2xvR0dHQ6XTQ6XR4/PHHsWzZMrz22msA7pyIun37di4+dpKfn49ff/0Ver0eer0eOTk5KC0thUajgb+/P+Li4qDT6ZCQkIDevXsjJibGeKGxd955B5999hkXH2s5N3C5PoPBQOPHj7/nNIi33nrL7H42btxobK9Wq3mviYSMHTv2nvX7zjvv8FcuK/HZ6Va4P+mITLlW7/3ubiMIAo4cOYJHHnkEBQUFVs+TWScyMvKek06Tk5Px7rvvWnRBOHYHFx4L1VR0AFh0zZzmzZvfc8kLg8HAxUciIiIiHriyIRcf63DhsUBtRQewLPFotVo0b978nse4+EhDTeuTi4/luPCYqa6i4+HhYfE9t1q3bv3AY1x8nC88PLzG57j4WIYLj5kmTZpUY9EB7ty1wNzrKYsiIyONN/q7293Fh+8y4Xg+Pj5o2LBhjc8nJyffc4scVjcuPGY6fPhwjbtSVSpVtanFVJGRkbXeUuXYsWMmXweY2VarVq1qfT4rK8tBM5EHLjxm+vXXX5GcnAx/f/8HntNqtRZt3xFFRERUG9m1Wi3GjRuHnJycahMRs79WrVpVW/QbNWqEuXPnGg8cZabhj08z+fj44K233kL37t3RvXt3AHeSDhGhsrLSqsJzd1uNRmO8l1ZCQoLZ9+FithUZGWn8UBDXNwDs27cPLVu2dOLMXBMnHgv16NEDAPDFF18YE5BKpUKbNm0s7rN58+bw9fU1JpyjR48CuHNBcUtvVMdso127djAYDGjUqBHmzJmDCRMmADD/lsnsDj5lwgJ332FCfPtKSkpw4cKFOrcF1OX69eu4ffu2cdd68+bNcf78efztb39DamqqdRNnVsnOzkZYWBg8PT0BwLit79KlS2jSpIkzp+ZyuPBYQLyN8Zw5c5CUlGTXse6+V7vBYLB4jxmzvaSkJMybNw8+Pj4oLi529nRcChceM1WXduyNU490ceqxDH98mqlDhw4AgDlz5jhszGPHjgEAfvvtN97WIzGvvPIKAMuOVlcyTjxmcEbaEXHqkS5OPebjxGMGZ6QdEace6eLUYz5OPCZyZtoRceqRLk495uHEYyJnph0Rpx7p4tRjHk48JpBC2hFx6pEuTj2m48RjAimkHRGnHuni1GM6Tjx1kFLaEXHqkS5OPabhxFMHKaUdEace6eLUYxpOPLWQYtoRceqRLk49dePEUwspph0Rpx7p4tRTN048NZBy2hFx6pEuTj2148RTAymnHRGnHuni1FM7TjzVcIW0I+LUI12cemrGiacarpB2RJx6pItTT8048dzHldKOiFOPdHHqqR4nnvu4UtoRceqRLk491ePEcxdXTDsiTj3SxannQZx47uKKaUfEqUe6OPU8iBPP/3HltCPi1CNdnHruxYnn/7hy2hFx6pEuTj334sQDeaQdEace6eLU81+ceCCPtCPi1CNdnHr+S/GJR05pR8SpR7o49dyh+MQjp7Qj4tQjXZx67lB04pFj2hFx6pEuTj0KTzxyTDsiTj3SxalHwYlHzmlHxKlHupSeehSbeOScdkSceqRL6alHkYlHCWlHxKlHupScehSZeJSQdkSceqRLyalHcYlHSWlHxKlHupSaehSXeJSUdkSceqRLqalHUYlHiWlHxKlHupSYehSVeJSYdkSceqRLialHMYlHyWlHxKlHupSWehSTeJScdkSceqRLaalHEYmH085/ceqRLiWlHkUkHk47/8WpR7qUlHpkn3g47TyIU490KSX1yD7xcNp5EKce6VJK6pF14uG0UzNOPdKlhNQj68TDaadmnHqkSwmpR7aJh9NO3Tj1SJfcU49sEw+nnbpx6pEuuaceWSYeTjum49QjXXJOPbJMPJx2TMepR7rknHpcvvCcPHkSXbp0wXvvvYfr168jIyPDmHKSkpKcPDvp8/b2RrNmzQAAgwcPRkVFBRYtWoT4+HisX7/eybNTtrlz5wIASkpKcPnyZVy+fBmTJk1Cjx49cPHiRSfPzkrk4r755hsCQGq1mjw9PQkAAaA5c+Y4e2ouo6SkxPi+NW3a1Pj/YcOGOXtqivfKK68Y14e7uztpNBoCQKtWrXL21Kzi8oknJycHbm5uEAQBZWVlxscvX76M69evO3FmrqGiogIrV640/nzp0iXj/48ePeqMKbH/c/nyZWg0GuPPFRUVMBgM0Gq1yMnJceLMrOfyhefEiROoqqp64PHk5GQ0a9YMCxcudMKsXMP+/fsRFhaG8ePHV/v8mTNneOO8k3z55Zdo2bIl5s2bV+3zXHic7OjRo9X+cYgJ6JdffnHCrFzD3r17a91WUFZWhsuXLztwRky0du1aY8K5X1VVlXGngKty6cJjMBiQm5tb7XMajQaRkZH49ttvHTwr1zFx4kQ89dRTxt221Tl58qQDZ8REP/zwA4KDg6HVaqt9nhOPE124cAGVlZUPPK7RaBAWFoa0tDQ0btzYCTNzDVqtFitWrMCIESNqLD6u/gvuqlq2bImdO3ciKCio2uJz48YNFBUVOWFmtuHShae6PwouOuaprfhotVpOPE5UV/Fx5XUjq8LDRccyNRUfg8GAEydOOHFmrLbi48pp1KULz90VX61Wc9Gxwt3FR0REvEtdAu4uPmr1f/9kXTnxVL/lyonELfZ6vR4nTpxAaWkpNBoNAgIC0L59e+h0OmNhOXTokLFdeHg4Fx0ricUHAFatWgXgzqcqEUGlUqG4uBgHDx6EXq9HXl4eKioq4O7ujuDgYOh0OsTFxcHb29uZL0G2xOJz91HL2dnZAO58QFy6dAl6vR6ZmZkoKiqCIAjw9vZGq1atoNPpEBUVdc8xQU7n1MMX/48gCLRr1y569tlnydvb23ikZrNmzSg6OpqioqIoICDA+HhYWBh9+umnpFarCQCFhITQ5cuXnf0yZKOyspKGDx9ufL9nzZpF3bp1I5VKRQDI09OTwsPDqXXr1hQWFkbu7u7Go8d79epFq1atovLycme/DFk6c+aM8W/B29ubPvzwQ2rWrJlxXQUGBlJUVBS1atWKQkJCjI/7+flRYmIipaenO/slEBGR0wvPzp07KS4ujgBQeHg4/etf/6Lt27fTzZs371lOEAQ6c+YMrVmzhkaPHn3P6RHHjh1z0uzlq6ysjPz9/Y3vcb9+/SglJYUyMzOpsrLynmXLy8vpr7/+ovnz59PDDz9MACgoKIgWLFhAgiA46RXI14EDB4zrxdfXlyZMmEDr1q2j3NzcB97vGzdu0JYtW2jq1KnGAtW1a1fS6/VOmv0dTis8JSUl9Prrr5NKpaIuXbrQxo0byWAwmNw+Pz+fxo8fT76+vhQcHEypqal2nK2yHD9+nBISEggA9e3bl44ePWpW+8OHD9MLL7xgLFjnzp2z00yVZ/Xq1dSgQQPy9/enSZMmPfABXZvKykr6+eefqX379qTRaGjKlClOS6ZOKTxXrlyh+Ph48vDwoH//+99UVVVlcV+5ubn02GOPEQD65JNP+BPWSps2bSIfHx8KDw+ntLQ0q/rasGEDhYSEkL+/P+3evdtGM1QmQRDojTfeMJ68m5eXZ3Ff5eXlNHXqVNJqtdSjRw8qLCy04UxN4/DCc+3aNYqJiaGgoCDKyMiwSZ+CINC0adMIAH344Yc26VOJNm3aRO7u7jRw4EAqLi62SZ8FBQXUo0cP8vHx4eJjIUEQKCkpiQDQ7Nmzbfbhunv3bvL396dOnTpRUVGRTfo0lUMLT2VlJSUkJFDDhg3tsl0mOTmZANDixYtt3rfcZWdnk7e3Nw0cONDm8bukpIR69OhBAQEB/LXLAjNmzCAAtGDBApv3rdfrqV69ejRw4ECHfltwaOH5/PPPSa1W065du+w2RmJiIvn5+fEvuBkqKyupc+fO1KpVKyopKbHLGAUFBRQSEkL9+vXjr8NmyM7OJg8PD3rzzTftNsZvv/1GAGjhwoV2G+N+Dis82dnZ5O7uTm+99ZZdxyksLORfcDOJHwh79uyx6zgbNmxw+C+4KxM/EKKjo6m0tNSuY40dO9ahH9gOKzxPPfUUhYWF0e3bt81uK36FAmDSH8f/+3//jwDQ1q1bLZmqoty6dYv8/PzotddeM2n5Fi1aGNfF/f8mTJhQZ/vnn3+eGjduTBUVFVbOXP7Wrl1LAGjnzp11LrtkyZIa14v4r0+fPjW2LywspKCgIPrHP/5hy5dQI4fcZSIvLw/NmjXDl19+iddee82stkePHkV8fDy0Wi1KSkqwZ88edO3atdY2RIQ2bdqgTZs2WLNmjTVTl70FCxZg4sSJOHPmDJo3b17n8i1btkRhYSEmTZr0wHMdO3bE448/Xmv7w4cPIzY2FqtXr8bw4cMtnbYiPProoygvL8fOnTvrXDYjIwM///xztc+tXbsWR44cQXJyMt5+++0a+5g6dSpmzpyJixcvol69epZO2zSOqG6ffPIJeXl5UUFBgVntqqqqqFOnTtS5c2d67rnnTE48RERz584ljUZDFy9etGDGyhEbG0tDhgwxefkWLVpQixYtrBqzZ8+e9Mgjj1jVh9wdPXqUANDKlSut6qe8vJwCAwNJq9XWuQv+/PnzpNFo6H//93+tGtMUDjlJ9Pfff8egQYPg7+9vVrvk5GRkZmZi8eLFZp9n8vTTT8NgMGDbtm1mtVOSvLw8HDp0CM8884xDx33mmWeQlpaG27dvO3RcV7J582a4u7tj2LBhVvWzbt065Ofn4/HHH0dQUFCty4aEhKBXr174/fffrRrTFHYvPAaDAQcPHkSnTp3MapeVlYWPP/4YH3zwAdq0aWP2uIGBgQgLC4Nerze7rVKI742566a8vBzLli3Dp59+im+++QaZmZlmte/cuTMEQTC7nZLo9XrExsbC09PTqn7EK3COGzfOpOU7derkkL8Zu5+dfuLECZSUlECn05ncpqqqCqNHj0br1q0xefJki8fW6XRceGqh1+tRv359tGjRwqx2eXl5GD169D2PDRgwAMuXL0eDBg3qbN+2bVu4u7tDr9ejW7duZo2tFHq9Ht27d7eqj3PnzuGPP/5AcHAwBgwYYFIbnU6H5ORkXLlypc6EZA27Jx7xdimhoaEmt/n000+NX7Hc3NwsHjs0NNT1b3xmRxcvXkRoaGit11y+X2JiIrZv345r166hqKgIe/fuxcCBA7Fx40Y88cQTJt2VQryUBq+bmonrxhpLliyBIAgYM2aMyZsqwsLCANx7myN7sHviKS8vBwCTI2NmZiamT5+Of/7zn8ZbEVvKw8PDOD57UEVFBTw8PMxq8+GHH97zc5cuXfDrr7+iV69e2LlzJ3777TcMGjSozn543dTOknVzN0EQsGTJEqhUKiQmJprcThzT3uvG7onH3d0dgOkvZNSoUQgPD8dHH31k9djWrjy5c3d3R0VFhdX9qNVqjBkzBgCwa9cuk9rwuqmdtetm8+bNyM3NRZ8+fcxKTuLfqfh3ay92TzziFQFzc3NNegPEDY41JSRxm8C6deswZMiQWvvKzc216/dUV9e4cWPk5uYarzBoDXHbjil7qiorK3Hx4kW+WmQtxHVjKXM3KovEMe29buxeeKKjo+Hl5YX09HT06tWrzuXHjh1b7eNpaWnIycnBE088gYYNG6Jly5Z19pWenm7yRjUl0ul0uHr1Ki5cuIBmzZpZ1de+ffsAwKT1kp2djfLycrN2OChNhw4dkJ6eblHb/Px8/PLLL6hfvz6GDh1qVtv09HQ0btwYTZs2tWhsk9n9SCEi6tatG40cOdKqPkaNGmXWAYSFhYUEgJYuXWrVuHJ24cIFAkA//fSTScsfOXKk2oNAd+zYQZ6enuTh4WHSuT4pKSmkUqno1q1b5k5ZMWbOnEmenp4WnVry1VdfEQB69dVXzW7bv39/GjRokNntzOWQAwj79u2L1NRU3Lp1yxHDAQBWr14NlUqF3r17O2xMV9O0aVNER0cbL+xel9WrV6Np06YYPHgwkpKS8M9//hMDBgzAww8/jMrKSsybN8+k0y5++OEHdOvWDb6+vta+BNnq27cvysrKsH79erPbWvo168qVK9i2bRv69u1r9phms3tpoztXCVSr1fTNN99Y3Ic5iUcQBIqLi6PBgwdbPJ5SzJ49m7RaLV26dKnOZbdv304jRoygiIgI8vPzIzc3NwoJCaGRI0fSvn37TBrv2LFjBICWL19u7dRlr3v37rWe2Fmdffv2EQDq3Lmz2eP961//Ii8vL7px44bZbc3lsLPThwwZQtHR0Q45K/mPP/4gALRhwwa7j+XqCgoKyNvbmyZPnuyQ8SZMmECBgYF2v8yDHKxcuZIAOOTC7MXFxRQSEkKJiYl2H4vIgYXnr7/+Io1GQx999JFdxykuLqbw8HDq3r27WRePV7IpU6aQVqu12aVoa/Lnn38SAJo5c6Zdx5GL8vJyateuHcXFxdn9A/vVV18lLy8vOnHihF3HETn0CoTiL/jBgwftNoaj30A5uPsX3F53HSguLqawsDDq3r27VRf3Vxq9Xk8ajYamTp1qtzHED4SvvvrKbmPcz6GFp7y8nNq3b0/NmjWjs2fP2rz/+fPnGy+Izcyj1+vJ3d2dRowYYfPCUF5eTgMGDCAfHx/+QLDA1KlTSaVS0ffff2/zvo8ePUoNGjSgnj17OvQDweF3mbhw4QKFhoZSixYtKCcnx2b9zp0717gLkS95apkff/yR1Go1jRgxwmbJp6SkhAYOHEju7u60efNmm/SpNAaDgV544QXSaDT0n//8x2b9Hjp0iIKCgigmJoauX79us35N4ZT7auXm5lKrVq2oXr16lJKSYlWhuHbtGj311FMEgN544w0uOlb68ccfyd3dndq3b2/1V+Ldu3dTq1atyMfHh4uOlaqqqigxMZEA0NixY626F5bBYKBZs2aRl5cXxcfH05UrV2w4U9M47U6iBQUFNGbMGAJA/fv3p71795pVNEpKSmjRokXUsGFDql+/Pn333XdcdGxEr9dTu3btSK1W09NPP232VRzPnTtHr776KqnVaurSpQtlZ2fbaabKIggCLVy4kPz8/CgkJISWL19OZWVlZrX/888/qUePHgSAkpKSbHb/NHM5/d7pqampFBoaSgCoQ4cO9PXXX1NGRka1W/HF+0C/8cYbFBAQQCqViv7nf/6HLl++7ISZy1tpaSk1aNCAABi/fv3444/V3p9bEAQ6ffo0rVq1iv7+97+TWq0mPz8/Sk5OfuA+68x6586do0GDBhEAatiwIU2ePJm2bdtW7e2My8vLSa/X0+zZs6lNmzYEgKKjo2nbtm2On/hdnF54iO7EyNTUVBo0aBCp1WoCQJ6enhQbG0tdu3alzp07G4sTAAoMDKS3336bTp065eypy5LBYKDx48cb3++pU6dSdHS08eeGDRuSTqejbt26UYcOHah+/frG59q3b08LFizg0yEcIDs7m1599VV66KGHjO9/eHg4de7cmbp27Upt27Yld3d3AkAajYaGDRtGW7ZskcQ3A4fcZcIcxcXFyMjIgF6vx4kTJ1BaWgqNRgN/f3/ExcVBp9MhKioKarVDzvZQHEEQMHHiRCxYsAAAoNFoUFFRAbVajUuXLkGv1yM9PR1XrlxBeXk5PDw8EBwcDJ1OB51Ox1cDcAKDwYBjx45Br9cjMzMTRUVFMBgM8Pb2RnR0NHQ6Hdq3bw9vb29nT9VIcoWHOc/9RQcAoqKicPz4cSfOiskRxwYGoPqiAwAxMTFOmhGTMy48rMai4+bmhsjISCfNiskZFx6Fq6noAHeuFMiFh9kDFx4Fq63oiCIiIhw4I6YUXHgUbMGCBbUWHQCceJhdcOFRsLZt28Lf37/GC727u7vb/9q7TJG48ChYz549cf78eSQnJ1f7fGhoKB8vxeyCf6sUztfXF6+99prx57sTUHR0tLOmxWSOCw9DXFwcACAhIcGYgFq0aIGRI0c6d2JMtvjIZYW7+46elZWV0Grtfqs1xjjxKN3daYeLDnMUTjwKxmmHOQsnHgXjtMOchROPQnHaYc7EiUehOO0wZ+LEo0CcdpizceJRIE47zNk48SgMpx0mBZx4FIbTDpMCTjwKwmmHSQUnHgXhtMOkghOPQnDaYVLCiUchOO0wKeHEowCcdpjUcOJRAE47TGo48cgcpx0mRZx4ZI7TDpMiTjwyxmmHSRUnHhnjtMOkihOPTHHaYVLGiUemOO0wKePEI0OcdpjUceKRIU47TOo48cgMpx3mCjjxyAynHeYKOPHICKcd5io48cgIpx3mKjjxyASnHeZKOPHIBKcd5ko48cgApx3majjxyACnHeZqOPG4OE47zBVx4nFxnHaYK+LE48I47TBXxYnHhXHaYa6KE4+L4rTDXBknHhfFaYe5Mk48LojTDnN1nHhcEKcd5uo48bgYTjtMDjjxuBhOO0wOOPG4EE47TC448bgQTjtMLjjxuAhOO0xOOPG4CE47TE448bgATjtMbjjxuABOO0xuOPFIHKcdJkeceCSmuLgY+fn5xp857TA54sQjIQaDAUFBQbh9+zYmTZqEpKQkNG3aFACnHSYvXHgk5OzZswgNDQUAqNVqCIIAAOjYsSMOHDjgzKkxZlP8VUtCTp48afy/WHQAICsrC++99x6uX7/ujGkxZnNceCQkJycHKpXqgcfLysqQnJyMli1boqqqygkzY8y2uPBIyMmTJ2vcjqNSqdCkSRNUVFQ4eFaM2R4XHgk5ceJEtYlGo9EgNDQUO3bsgLe3txNmxphtceGRkKNHj+L+bf13F53GjRs7aWaM2Rbv1ZIIg8EAT0/PexIPFx0mV5x4JOL8+fP3FB21Ws1Fh8kWFx6JuHtXukqlQlhYGBcdJlt8KKydEBH27duHPXv2QK/X49ChQygqKoIgCPD29karVq2g0+nQsWNH9OnTB8ePHze25aLD5I638djYzZs3sXz5cnz99dc4evQoPD090b59e8THxyMwMBAqlQolJSXIysqCXq/HjRs30KBBA6hUKly7dg0BAQHIzs7mosNkjROPDa1ZswYTJ05EQUEBhg4dinnz5uHhhx+u8dgcIsLRo0eRkpKCuXPnAgBGjRqF+vXrO3LajDkeMavduHGDhg8fTgDoySefpPPnz5vdR1FREX300Uek1WqpXbt2dOjQITvMlDFp4K9aVrpy5Qr69++P8+fP45tvvsGIESOqPe3BVBkZGRg1ahTOnj2L1NRU9OjRw4azZUwauPBY4caNG3jkkUdw/fp1bNmyBTExMTbp99atW3jiiSeQnp6OrVu3olOnTjbplzGp4MJjISLC0KFDsWPHDuzYscNmRUdUUlKCvn374vz588jKyoK/v79N+2fMmfg4Hgt9//33+OWXX5CSkmLzogMAPj4+WL16NYqKivDGG2/YvH/GnIkLjwXy8/ORlJSEkSNHYujQoSa1WbduHfr164fAwEB4eXkhNDQUTz/9NM6fP19jm2bNmmHmzJlYsmQJtmzZYqvpM+Z0/FXLAl988QU+/PBD5ObmolGjRrUuS0R46aWXsHDhQoSHh+Oxxx6Dn58fLl26hD///BMrV66sdQMyEaFLly4ICAjA77//buuXwphzOGlvmsuqqqqi0NBQeuGFF0xafvbs2QSAXn75Zaqqqnrg+crKyjr7WLZsGQGgEydOmD1fxqSIE4+ZtmzZgn79+mHPnj3o2rVrrcuWlpYiJCQE/v7+OH78uMUXay8rK0NISAjGjRuHzz//3KI+GJMSPnLZTLt370b9+vXRpUuXOpfdvHkzbty4gdGjR8NgMGD9+vU4ceIE/P390bdvX0RERJg0pqenJ/r06YPdu3dbO33GJIELj5n0ej10Op1JBwmmp6cDALRaLdq3b3/PiaBqtRqvv/46vvzyS5PG1el0mD59OgRBgFrN+wSYa+PfYDNlZmaiQ4cOJi179epVAMCMGTNQr1497N+/H7du3UJaWhqioqIwY8YMfPPNNyb11aFDBxQXF+PUqVMWz50xqeDCY6aCggI0bNjQpGXFW9S4u7vj559/RqdOneDr64uePXti7dq1UKvVmDFjhkl9iWPevHnTsokzJiFceMxkMBhM/qrz0EMPAbhzQz7xjqCiNm3aICwsDKdOnUJhYWGdfWk0GuP4jLk6Ljxm8vLyQklJiUnLtmrVCgBqPN1BfLy0tLTOvsQxPT09TRqbMSnjwmOmyMhIZGdnm7Rs7969Ady5e8T9KisrcfLkSfj4+Jj01e3IkSNQqVQIDw83b8KMSRAXHjPpdDro9XqTlg0PD0f//v1x8uRJpKSk3PPc559/jsLCQgwdOtSk43v0ej2io6Ph6+tr0bwZkxI+gNBMy5Ytw+jRo3H16lWTksqpU6eQkJCAq1evYtCgQYiOjsbBgwexdetWtGjRAnv37jXpMqdxcXFo164dli9fbouXwZhTceIx06BBg+Dh4YElS5aYtHx4eDjS09MxevRo6PV6zJkzBzk5OXj55Zexf/9+k4pOeno6MjMzMXz4cGunz5gkcOKxwKhRo7Bjxw7k5OQY9zbZ09ixY7FlyxacPn3aIeMxZm+ceCzw8ssv48yZM1i6dKndxzp27BhWrlyJl156iYsOkw1OPBYaM2YMfvrpJ2RlZaFZs2Z2GcNgMKBHjx64ceMGMjIy4OXlZZdxGHM0TjwW+uqrr+Dn54fExERUVlbaZYzPPvsM+/btw+LFi7noMFnhwmMhf39/LFu2DH/++SfGjBlzz33PbWHRokWYMmUKpkyZgu7du9u0b8acznmXApKH1atXk0ajoSFDhlBhYaHV/RkMBvrss8+MFw8TBMEGs2RMWrjw2MD69evJz8+PQkJCaOPGjRb3k5OTQz169CAA9P7773PRYbLFX7VsYPDgwcjKykLr1q0xYMAA/P3vf8emTZuMZ6fXJTs7G0lJSYiNjcWlS5ewfft2TJ8+3aobAzImZbxXy4aICMuXL8eXX36Jw4cPIyIiAv369YNOp0N8fDwCAwOh0Whw69YtZGVlQa/XY+fOndi1axeCgoIwfvx4vPPOO/Dx8XH2S2HMrrjw2AERYffu3fj222+xd+9eHDt2DNW9zcHBwejYsSNGjhyJYcOGwd3d3QmzZczxuPA4QHFxMbKysnDr1i0YDAZ4eXkhOjoaQUFBzp4aY07BhYcx5nC8cZkx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZwXHgYYw7HhYcx5nBceBhjDseFhzHmcFx4GGMOx4WHMeZw/x8nEnGdEOQgngAAAABJRU5ErkJggg==", "text/plain": [ "Figure(PyObject
)" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Visiting vertex #1\n", "Visiting vertex #2\n", "Visiting vertex #3\n", "Visiting vertex #4\n", "Visiting vertex #5\n", "Visiting vertex #7\n", "Visiting vertex #6\n" ] } ], "source": [ "plot(g)\n", "bfs(g,1)" ] }, { "cell_type": "markdown", "id": "a5ccc078", "metadata": {}, "source": [ "Notice the only difference in the two algorithsm above is the choice of data structure, DFS uses a stack, BFS uses a queue. The moral of the story is that a good data structure choice can make your algorithm much more efficient and also easier to implement!" ] }, { "cell_type": "markdown", "id": "0b164201", "metadata": {}, "source": [ "## Sparse Matrices\n", "\n", "One of the very important applications of graphs and good data structure usage is for sparse matrices. A sparse matrix is one where most of the entries are zero - meaning that we should not be storing them as it would be a waste of space. For a lot of applications, matrices tend to be sparse (~5% non-zero values). Specialised data structures and algorithms have been designed specially for this.\n", "\n", "To show why this is a good idea:" ] }, { "cell_type": "code", "execution_count": 24, "id": "03d33817", "metadata": {}, "outputs": [], "source": [ "using SparseArrays" ] }, { "cell_type": "code", "execution_count": 25, "id": "76bb8e7e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1000×1000 SparseMatrixCSC{Float64, Int64} with 50523 stored entries:\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿\n", "⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mat1 = sprand( 1000,1000,0.05 )" ] }, { "cell_type": "markdown", "id": "578a85ea", "metadata": {}, "source": [ "So I have generate an one million entry matrix where only 5 percent of the entries are non-zero. Let's compare the speed of running this in sparse form compared to dense form:" ] }, { "cell_type": "code", "execution_count": 26, "id": "9f3025d4", "metadata": {}, "outputs": [], "source": [ "vec = rand( 1000 );" ] }, { "cell_type": "code", "execution_count": 27, "id": "790531f2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.078659 seconds (70.11 k allocations: 4.290 MiB, 98.44% compilation time)\n" ] } ], "source": [ "@time mat1 * vec;" ] }, { "cell_type": "code", "execution_count": 28, "id": "f04dfdff", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.185208 seconds (376.31 k allocations: 30.134 MiB, 12.26% gc time, 96.41% compilation time)\n" ] } ], "source": [ "@time Matrix( mat1 ) * vec;" ] }, { "cell_type": "markdown", "id": "a667508d", "metadata": {}, "source": [ "So you can see that it is magnitudes more expensive in memory and in time. Bad idea." ] }, { "cell_type": "markdown", "id": "739f7b97", "metadata": {}, "source": [ "The way sparse matrices are stored differs from language to language. Julia uses the Compressed Sparse Column format, for example:" ] }, { "cell_type": "code", "execution_count": 29, "id": "d23c7055", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5×5 SparseMatrixCSC{Int64, Int64} with 10 stored entries:\n", " 5 ⋅ -3 -2 7\n", " ⋅ 5 ⋅ ⋅ ⋅\n", " -2 ⋅ -1 ⋅ ⋅\n", " -4 ⋅ ⋅ -10 ⋅\n", " ⋅ ⋅ ⋅ ⋅ 9" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rows = [1,3,4,2,1,3,1,4,1,5]\n", "cols = [1,1,1,2,3,3,4,4,5,5]\n", "vals = [5,-2,-4,5,-3,-1,-2,-10,7,9]\n", "\n", "A = sparse(rows, cols, vals, 5, 5)" ] }, { "cell_type": "markdown", "id": "87b0372e", "metadata": {}, "source": [ "What Julia would store is that in column 1, there are 3 entries 5,-2,-4 in rows 1,3,4. And that in column 2 there is one entry in row 2. And so on. This way per the amount of storage instead of being $n^2$ is just 3 times the number of non-zero entries in the matrix." ] }, { "cell_type": "markdown", "id": "b1d3eb82", "metadata": {}, "source": [ "One big application of sparse matrices is to represent graphs. Each row/column represents a node, and a one in the ij position means there is a connection from node i to node j. This is how for example search engines store links between websites etc. \n", "\n", "It turns out that the eigenvector corresponding to the largest eigenvalue of this matrix will give you the node with the most neighbours linking to it. This is how the google pagerank algorithm works." ] }, { "cell_type": "code", "execution_count": null, "id": "545b7e48", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.5", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.5" } }, "nbformat": 4, "nbformat_minor": 5 }