{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" <p><div class=\"lev1 toc-item\"><a href=\"#Implementing-BFS\" data-toc-modified-id=\"Implementing-BFS-1\"><span class=\"toc-item-num\">1 </span>Implementing BFS</a></div><div class=\"lev1 toc-item\"><a href=\"#Intro-to-the-Maximum-Flow-Problem\" data-toc-modified-id=\"Intro-to-the-Maximum-Flow-Problem-2\"><span class=\"toc-item-num\">2 </span>Intro to the Maximum Flow Problem</a></div><div class=\"lev2 toc-item\"><a href=\"#A-Naive-Greedy-Algorithm\" data-toc-modified-id=\"A-Naive-Greedy-Algorithm-21\"><span class=\"toc-item-num\">2.1 </span>A Naive Greedy Algorithm</a></div><div class=\"lev2 toc-item\"><a href=\"#Residual-Graphs\" data-toc-modified-id=\"Residual-Graphs-22\"><span class=\"toc-item-num\">2.2 </span>Residual Graphs</a></div><div class=\"lev2 toc-item\"><a href=\"#Ford-Fulkerson-Algorithm\" data-toc-modified-id=\"Ford-Fulkerson-Algorithm-23\"><span class=\"toc-item-num\">2.3 </span>Ford-Fulkerson Algorithm</a></div><div class=\"lev2 toc-item\"><a href=\"#NetworkXを用いて最大流問題を解く\" data-toc-modified-id=\"NetworkXを用いて最大流問題を解く-24\"><span class=\"toc-item-num\">2.4 </span>NetworkXを用いて最大流問題を解く</a></div><div class=\"lev1 toc-item\"><a href=\"#Summary\" data-toc-modified-id=\"Summary-3\"><span class=\"toc-item-num\">3 </span>Summary</a></div>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Implementing BFS"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"まず準備として、始点と終点が指定されたときに始点から終点に至るパスのうちの一つを求めるアルゴリズムを実装したい。「Breadth First Search(BFS, 幅優先探索)やDFS(Depth First Search)を用いて実装できる」とレクチャーノートに書いてあるので、試しにBFSを用いて実装してみる。\n",
"\n",
"BFSの実装にはQueueというデータ構造を用いる。(cf: DFSではstackを用いる。)Pythonでは、dequeというデータ構造（stackとqueueを合わせたようなデータ構造）が提供されているので、それを用いる。\n",
"\n",
"[このページ](http://www.ocw.titech.ac.jp/index.php?module=General&action=DownLoad&file=201602093-9183-1-11.pdf&type=cal&JWC=201602093)も参考になりそう。\n",
"\n",
"実装に当たって、NetworkXというpythonのグラフライブラリを利用している。詳しい使い方は[公式サイトのチュートリアル](http://networkx.readthedocs.io/en/networkx-1.11/tutorial/)等が参考になる。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
">Given a graph $G$ and a starting vertex $s$, a breadth first search proceeds by exploring edges in the graph to find all the vertices in $G$ for which there is a path from $s$. The remarkable thing about a breadth first search is that it finds all the vertices that are a distance $k$ from ss before it finds any vertices that are a distance $k+1$. (http://interactivepython.org/runestone/static/pythonds/Graphs/ImplementingBreadthFirstSearch.html)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# dequeをimport\n",
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"code_folding": [
0
],
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"deque([1, 2, 3, 4, 5])\n",
"deque([1, 2, 3, 4, 5, 0])\n",
"0\n",
"deque([1, 2, 3, 4, 5])\n",
"1\n",
"deque([2, 3, 4, 5])\n"
]
}
],
"source": [
"# dequeのメソッドの確認\n",
"\n",
"d = deque([1,2,3,4,5])\n",
"print (d)\n",
"\n",
"# append: push/enqueueに対応\n",
"d.append(0)\n",
"print (d)\n",
"\n",
"# pop: 右の要素を削除し、返す\n",
"print (d.pop())\n",
"print (d)\n",
"\n",
"# popleft: 一番左の要素を削除し、返す\n",
"print (d.popleft())\n",
"print (d)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# NetworkXをインポート\n",
"import networkx as nx\n",
"\n",
"G = nx.DiGraph()\n",
"\n",
"G.add_edges_from([(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(4,5)])"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"code_folding": [
0
],
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAhcAAAFkCAYAAACThxm6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzs3Xd8jef/x/FXZIpRSqlRaiUVNUpL+1WztNTosEutJITk\n+Laoaql+1WpVjZyTgWPvoLYgNUs1tVcQITapHUlknOT+/RH6Kxkyzsl9xuf5eHjQ+z7jHZXkneu+\n7uuyUxRFQQghhBDCSAqpHUAIIYQQ1kXKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqF\nEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQ\nQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBC\nCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEII\nIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQggh\njErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGM\nSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYxK\nyoUQQgghjErKhRBCCCGMSsqFEEIIIYxKyoUQQgghjErKhRBCCCGMSsqFEEIIIYzKQe0AQhS0uLg4\noqKiSEpKwtnZmerVq1O0aFG1YwkhhNWQciFsQkREBMHBwYRt3szZCxdQFOWfc3Z2drhXrUrrDz/E\nx8cHDw8PFZMKIYTls1P+/VVWCCsTHR3N4IED2RIWRhkHBzoZDLwFeACuQAIQARwAVjs48LfBQJvW\nrQmcOZMqVaqoGV0IISyWlAthtfR6PV9oNJQ2GJhoMNAZcMrm8cnAKuAbBwfuODgwXavFy8urYMIK\nIYQVkQmdwipNmDABb29veiQmcsJg4DOyLxY8Pv8ZcNJgoEdiIt7e3kyYMMH0YYUQwsrIyIWwOnq9\nHm9vb8YBo/PxOuOAMY9fz9PT0zjhhBDCBki5EFYlOjqa2h4e9EhMZPYz5yKA/wGHgJukz7nwAL4C\n2mfyWgowAFjm4sKJiAiZgyGEEDkkl0WEVRk8cCClDQamZnLuEhAH9AX8SR+VsAM6AvpMHm8H/AKU\nMhgYPHCgaQILIYQVkpELYTUiIiKoVasWS0ifO5ETClAfSCJ9ZCMzS4Gej1+/Zs2a+Q8qhBBWTkYu\nhNUIDg6mjIMDnXPxHDvgFeB+No/pBJRxcCAoKChf+YSwVHFxcRw9epTw8HCOHj1KXFyc2pGEmZNF\ntITVCNu8mU4Gw3PvCkkAHgEPgHVAKNAjm8c7A50MBn4LDTVOUCEsgCw8J/JDLosIq/Dw4UNeeOEF\n5igK/Z7z2EHAzMd/LkT6yMQs4IVsnjMX8LKzIzY2VpYKF1ZNFp4TxiCXRYRVOH/+PIqikJOfn74E\nfgMWAh8CqaTPuchOLUBRFKKiovIXVAgzptfrqe3hwemdO1kCXDEYCAT6AY2A2o9/7wcEPj6/BIjY\nuZPaHh7o9ZlNjRa2SC6LCKuQlJReD1xz8Fi3x78AegEfkH7HyJ/ZPKfw49+HDh1KxYoVcXV1pUiR\nIri6uub6z05OTtjZ2eXxIxXCNCZMmMDo0aPxAqYCxXLwnCcLz3UwGBhqMODt7U1MTAyjRo0yaVZh\n/qRcCKvg7OwMpA/Z5lZnwAc4B9TI4jGPHv+emJjIxYsXSUhIID4+noSEhH/+/OjRoyye/TR7e/t/\nCkd+Skp2f3Z0dMzD34SwVXq9ntGjRz934bkJwHfA68Dxfx0vBswGKgGjR4/m5ZdfloXnbJzMuRBW\nIS4ujuLFi+dozsWz/Em/VBIOvJnFY3Iy5yItLY3ExMQMpcOYf34yQvM8jo6Ozy0g+S0w9vb2ufyb\nFuYou4Xn/u0a4E76tfRXebpcPCELz4knpFwIq1GzenVanD9PYBbnbwEvPXPMQPo15LPA32R9WWUw\nsKt6dSLOnTNK1rxKTU39p3A8W0CMVWBSUlJylMXZ2dmkoy+FCxemUCHLnhaWkpLCw4cPKVKkiNle\nDmv7/vuc3rmTEwZDtpdCugN3SP+cuUPm5QIgFqjt4IBHixaEbttm5LTCUshlEWE1Wn/4ISuCgpie\nxe2oA0n/wtcUqED6EuBLSC8WU8m6WCSRPiu+W9u2JkidO/b29hQrVoxixXJyRTxvUlJSjFJYbt68\nmenx+Ph40tLScpSlcOHCRi0sz/63i4uLSb/hHz16lIYNGwJQqFAhk34sRYoUyfXlsIiICLaEhbGE\n7OdY7AF+BY4Afs95zeLAJIOBnmFhnD59Whaes1EyciGsxvNW6AwB5gAnSP/JqxjQABgCtMvmdWWF\nTuNSFIXk5OQ8l5ecPi4nX9rs7OxMOvpy6NAhWrduXQB/q+kcHBxylXPXrl1cOHiQa2lpWa4Pk0b6\nKraNgQCgBdmPXEB6Ia/k4EC3QYPw9/c36scoLIOUC2FVcjrEm1MyxGuZFEUhMTHRZHNfEhIScjyB\n15w5Al6Q5aVESC8U3wFRwIvkrFyA+VxKFOqQciGsSk4np+WETE4T2UlLS+PRo0fZFpBdu3ah0+nU\njpqtuZDlJOi7pN+2PRr44vGxnJYLWXjOtsmcC2FVqlSpwnStFm9vbyqT/W112VGA8aTvlqrX6aRY\niAwKFSpEkSJFKFKkCC+99OxU4XTx8fEFnCr3slt4bhRQiufPs8jMvxeeq1evXp6yCcsl5UJYHS8v\nL+bOnct3+/dzEZhGzhYEeiIWGEZ6sZgwYYLcry/yrG7duowdO9Zkd+wYQ1YTmaNIX7tiBum3oUJ6\n6U4EUoBLpE/eLJnF858sPJfT26eFdZHLIsLqnDx5knr16pGamkoh4GXgZ9IXy8puU7MkYDXwjYMD\ndxwcmKHTSbEQqnj2jh1jzxv59x07f5J+O/azdgMtH/85s28SdsB/Sb/TKjPhwNvAkSNHZOTCBkm5\nEFZFURTee+89du7c+c+xQqTPeC9lZ0dXReFN0odsC5O+8uYp4CCyCZOwDRcvXiQgIIDZs2fz4MGD\nLOdc3AH2ZXJ8FBBH+uJzVUn/XMqMzLmwbXJZRFiVVatWPVUsIL1YODo68mH37uzav5/gx5ucPWFn\nZ8dr1arRrW1bBg0aJLebCqujKAo7d+5Eq9Wyfv36f0YtHEnf3TSzclGK9D13njWN9FGLDs95z4PA\na9WqSbGwUVIuhNWIj49n2LBhmZ4bNmwYkyZNAtKXCo+KiiIpKQlnZ2eqV68uXwCFVYqPj2fRokXo\ndDpOnTqV4XwKsAKYTvaXDJ/1vGXHzGnhOaEOuSwirMaYMWMYN25chuMVKlTgzJkzUiCEzbhw4QIB\nAQHMnTuX+/fvP/fxWS08l1ey8JyQciGswoULF/Dw8Mh0ZvrSpUvp0aOHCqmEKDiKohAWFoZWq2XT\npk05WqEU0ucklQciyN1dVVmRhecEpP+7EsLiDR06NNNi0aRJE7p3765CIiEKxsOHDwkICMDDw4MP\nPviAjRs35qhYODg40L17d1asXMk9FxeGGiGLQvpt3HccHAicOdMIrygslcy5EBZv69atrFu3LsPx\nQoUKodVqzXInSiHy69y5c+h0OubPn09sbGyOn1emTBkGDhyIj48P5cuXB+D+/fuy8JwwKikXwqIl\nJyfz3//+N9NzPj4+1K1bt4ATCWE6aWlpbN26Fa1WS2hoaK6e27BhQzQaDV26dMHZ2fmpc15eXsTE\nxDB69GhZeE4YhZQLYdH8/f05e/ZshuMvvvgiP/zwgwqJhDC+Bw8eMH/+fAICAjiXi43AHB0d6dq1\nKxqNhkaNMlsq6/+NGjWKpKQkJowbx9ZChfgpLS3HC899Bdx3dkYfECDFQgAyoVNYsBs3buDm5kZc\nXFyGc0FBQfj4+KiQSgjjOX36NDqdjoULF2b67zwr5cqVw8fHhwEDBvDyyy/n6DmKotC0aVNu3rxJ\ntVdfZetvv1HGwYFOBkOWC8+tIH1zs0JAfy8vZs/O73aBwlpIuRAWq0+fPixcuDDD8Xr16nHw4EHs\n7e1VSCVE/qSmprJ582a0Wi1hYWG5eu4777yDRqOhU6dOODnlZuUKWLJkCb169SIsLIxWrVoRERFB\ncHAwv4WGcuaZhecgfQGuf++A8tJLL3H16tVcv6+wTlIuhEX6448/aNy4cabnfv/9d959990CTiRE\n/ty/f5+5c+cSEBDAhQsXcvw8JycnevTogUajoUGDBnl674cPH+Lu7s4777zD6tWrM5x/duG5SZMm\nERISkuFxq1atolOnTnnKIKyLlAthcVJTU2nYsCGHDx/OcK5nz54sXrxYhVRC5M2pU6fQarUsWrSI\nhISEHD+vQoUKDBo0CG9vb8qUKZOvDCNHjmTGjBmcPn2aV1999bmP37VrFy1atMhw/IMPPmDLli35\nyiKsg5QLYXFmz57NgAEDMhwvUqQIkZGR/9xeJ4S5Sk1NZcOGDWi1Wnbs2JGr5zZp0gSNRsPHH3+M\no6NjvrOcO3eOWrVq8e233/K///0vR89RFAU3NzeioqKeOm5nZ0d0dDSVK1fOdy5h2WQRLWFR7t27\nx7fffpvpue+++06KhTBrd+/eZfLkyVSrVo1PPvkkx8XCxcUFT09Pjhw5wp49e+jSpYtRigXAF198\nQfny5fn6669z/Bw7Ozu8vLwyHFcUhblz5xoll7BsMnIhLIpGo0Gn02U4XqNGDU6cOJHh/n0hzMHx\n48fRarUsXryYxMTEHD+vUqVKDB48GC8vL0qVKmX0XJs2baJ9+/Z5mitx8+ZNKlasSGpq6lPHK1as\nyMWLF2VCtY2TciEsxokTJ6hXr94/20X/2+bNm2krOzAKM2IwGFi7di1arZY9e/bk6rnNmzdnyJAh\ndOjQAQcH0yxHlJSUxOuvv07lypUJCwvL00q2n3zyCWvXrs1wXD4fhVwWERZBURQ0Gk2mxaJ9+/by\nhUyYjdu3bzNp0iSqVq1Kly5dclwsChcuzIABAzh+/Dg7d+7kk08+MVmxAJg2bRrR0dHMmDEjz0vk\ne3t7Z3pc1rsQMnIhLMKKFSsy3YDMycmJU6dOUb16dRVSCfH/Dh8+jFarZdmyZZluopeVV199FV9f\nX/r378+LL75owoT/79q1a7i7u+Pt7c20adPy/DqpqalUrlyZa9euPXXcwcGBK1eu5HgBL2F9ZORC\nmL34+HiGDx+e6bnhw4dLsRCqSUlJYcWKFbz77rs0aNCA+fPn57hYtGrVinXr1hEVFcXw4cMLrFgA\njBgxAldXV77//vt8vY69vT39+/fPcNxgMGS6wJ2wHTJyIcxecnIyWq2W77//nvj4+H+OV6hQgbNn\nz1KkSBEV0wlbFBMTw6xZswgODub69es5fl6RIkXo06cPfn5+1KxZ04QJs/b777/TtGlT5syZk2kx\nyK2LFy9StWrVDCt41qhRg7Nnz8quxDZKyoWwGB988AF79+79Z6GhZcuWZXqpRAhTOXDgAFqtlhUr\nVpCcnJzj51WrVg0/Pz/69evHCy+8YMKE2UtNTaVBgwY4OTnx559/UqiQcQavP/jgA7Zt25bh+K5d\nu2jWrJlR3kNYFtkVVViELVu2sG3bNpYvX84rr7zCkiVL6Natm9qxhA1ITk5m1apV+Pv7Ex4enqvn\ntmnTBo1GQ5s2bYz2jTw/Zs2axbFjx4xaLCB9Ymdm5UKv10u5sFEyciHMXnJyMrVr16Z8+fLs2LFD\nhllFgbhx4wYzZ85k5syZ3Lx5M8fPK1asGH379sXX1xd3d3cTJsydO3fu4ObmxkcffWT0ha6Sk5Op\nUKECt2/ffuq4i4sL169fp2TJkkZ9P2H+1K/SQjzHjBkzOH/+PP7+/lIshEkpisL+/fv57LPPqFSp\nEmPHjs1xsXB3d0er1XL16lX8/f3NqlhA+gq2BoOBSZMmGf21nZyc6NOnT4bjiYmJLFmyxOjvJ8yf\njFwIs3bjxg3c3Nzo168f/v7+ascRVi42Npby5cs/NXE4O3Z2dnz44YdoNBpat25tFpc+MnP06FEa\nNGjAlClT+PLLL03yHmfOnMl0kmqdOnU4evSo/GBgY6RcCLPWu3dvQkNDiYyMlKFVUSC8vb3R6/XZ\nPuaFF16gf//+DB482OxvhVYUhWbNmnH79m2OHTtmtD1JMtOkSRP27t2b4fhff/3FW2+9ZbL3FeZH\nJnQKs/XHH3+waNEiZs2aJcVCmNzly5cJDAxk5cqVWT7Gw8MDjUZDr169KFq0aAGmy7tly5bx+++/\ns23bNpMWCwAvL69My4Ver5dyYWNk5EKYpdTUVBo2bIidnR3h4eGyCZIwCUVR2L17N1qtlrVr11K0\naFE8PT0JDw/njz/+ANIvfXTs2BGNRkPLli0tang/Li4Od3d3GjVqxK+//mry90tISKBcuXLExsY+\ndbxo0aLcuHHDYgqZyD/zvEAobN6cOXP+WU5ZioUwtoSEBGbNmkXdunVp0aIFp0+fRqfTce3aNaZO\nncqIESMoWbIkw4cP5/z586xdu5b33nvPoooFwIQJE7h79y5Tp04tkPdzdXWlZ8+eGY7HxcWxYcOG\nAskgzIOMXAizc/fuXdzc3GjXrh0LFixQO46wItHR0QQGBjJnzhzu37+f5YhEamoqSUlJuLq6qpg2\nf86dO8frr7/OyJEjGTt2bIG97+HDh2nQoME//+3h4UFgYCBNmza1uHIm8k7KhTA7fn5+LFy4kLNn\nz1KuXDm14wgLpygK27dvR6vVsmHDBkqUKIGnpyeDBw+mSpUqasczmfbt23PixAlOnz5d4CWpV69e\nvP3225w8eZI1a9Zw5coVnJycCjSDUJeUC2FWjh8/zhtvvMFPP/2U5WZlQuREXFwcixYtQqvVcvr0\naWrXro1Go6Fnz54WPSKRE5s2baJ9+/asXLmSzp07q5bj5MmT1K5dm9WrV/Ppp5+qlkMUPCkXwmwo\nikLz5s2JiYnh+PHj8pOOyJOoqCgCAgKYN28eDx8+5OOPP2bIkCE2MyyflJTE66+/TqVKlfjtt99U\n/5jfeecdSpQoQWhoqKo5RMGSW1GF2VixYgV79uxh69atUixErqSlpREWFoa/vz+hoaG8+OKLDBo0\niEGDBlGpUiW14xWo6dOnEx0dzdq1a1UvFpB+e6q3tzeXL1+2uf8XtkxGLoRZiI+Px93dnbfeeos1\na9aoHUdYiNjYWBYsWIBOpyMyMpJ69eqh0Wjo0aMHhQsXVjtegbt27Rru7u54eXkxffp0teMA6Zen\nypUrx/Dhw/n+++/VjiMKiJQLYRZGjRrFL7/8QkREBFWrVlU7jjBzkZGR6HQ65s+fT0JCAp06dUKj\n0dC4cWOz+GldLb169WLbtm1ERkZSokQJteP8Y8CAAWzZsoXo6Gi5tdxGyDoXQnVRUVFMmTKFESNG\nSLEQWUpLS2PTpk20adMGd3d3li9fzpAhQ7h48SIrVqzg3XfftelisXfvXpYsWcKkSZPMqlhA+qWR\nK1euEBYWpnYUUUBk5EKormPHjhw9epQzZ85Y/Sx+kXsPHjxg3rx5BAQEEBUVxZtvvolGo6Fr1664\nuLioHc8spKam8uabb+Lg4EB4eLjZbaCmKAp169bFzc2NVatWqR1HFACZ0ClUFRoayoYNGwgJCZFi\nIZ4SERGBTqdj4cKFJCUl0bVrVxYtWkSjRo1seoQiM7Nnz+bo0aP8+eefZlcsIH0JdW9vb4YOHUpM\nTAxly5ZVO5IwMRm5EKpJSkqidu3aVKxYke3bt8s3DEFqaiobN25Eq9Wyfft2ypYti4+PDwMHDpQF\n1bJw9+5datSoQceOHZk3b57acbJ09+5dypcvz7hx4/jqq6/UjiNMzPwqrrAZM2bM4MKFC2i1WikW\nNu7evXtMmTKF6tWr8/HHHxMXF8eSJUu4fPky//vf/6RYZOO7774jJSWFSZMmqR0lWy+++CKdOnVC\nr9cjP9NaPxm5EKq4fv067u7ueHp6ms0tc6LgnThxAq1Wy+LFi0lNTaVbt25oNBrZnjuHjh07Rv36\n9fn5558ZOnSo2nGea9euXbRo0YLdu3fTtGlTteMIE5JyIVRhrrfMCdMzGAysX78erVbLrl27KF++\nPIMGDcLb21uuxeeCoig0a9aMW7ducezYMYtYeE5RFNzc3HjnnXdYuHCh2nGECcllEVHgzPmWOWE6\nd+7c4aeffqJatWp06tSJlJQUli9fzsWLFxk9erQUi1xavnw5v//+O/7+/hZRLCB9YqenpycrV67k\n/v37ascRJiQjF6JAmfstc8L4jh49ilarZenSpSiKQo8ePdBoNNSvX1/taBYrLi6O1157zSJXtL15\n8yYVK1ZkxowZ+Pr6qh1HmIh8ZRcF6sktczqdToqFFUtJSSEkJIQmTZrwxhtvsG3bNsaMGcOVK1eY\nN2+eFIt8mjhxIrdv32bq1KlqR8m1l19+mQ4dOjB79myZ2GnF5Ku7KDB37txh1KhR9O3bl0aNGqkd\nR5jA33//zYQJE6hSpQrdunXD3t6eVatWER0dzTfffMNLL72kdkSLFxUVxS+//MKIESOoUqWK2nHy\nxMvLi2PHjnHo0CG1owgTkcsiosD4+vqyePFiIiMj5fq6lTl48CBarZbly5djb29Pz5490Wg01KlT\nR+1oVqdDhw4cO3bMole0TU1NpXLlyrRv357g4GC14wgTkJELUSCOHTtGcHAw33//vRQLK5GcnMyy\nZcv4z3/+w1tvvcXu3bsZP348V69eZfbs2VIsTGDz5s1s3LiRX375xWKLBYC9vT39+/dn6dKlxMfH\nqx1HmICMXAiTe3LL3O3btzl27BiOjo5qRxL5cPPmTWbOnElwcDA3b96kZcuWaDQaOnToIDtempC1\nrWh78eJFqlatypw5c+jXr5/acYSRyd4iwuSe3DIXFhYmxcKChYeHo9VqCQkJwdHRkd69e+Pn50et\nWrXUjmYTnqxo++uvv1p8sQB49dVXad26NXq9XsqFFZKRC2FScXFxuLu78/bbb7N69Wq144hcSkpK\nIiQkBK1Wy4EDB6hatSq+vr7069ePkiVLqh3PZjxZ0bZ///7MmDFD7ThGs3LlSrp27cqpU6fw8PBQ\nO44wIplzIUxqwoQJ3L17l19++UXtKCIXrl+/zpgxY6hUqRK9e/emZMmSbNiwgcjISIYOHSrFooB9\n/fXXuLi4MHbsWLWjGNVHH31E6dKl0ev1akcRRiblQpjMuXPnmDp1Kl9//TWvvvqq2nHEcyiKwr59\n++jevTuVK1dm2rRpdOnShdOnT7N161bat28vcypUsG/fPhYvXmyVK9o6OTnRp08fFi5cSFJSktpx\nhBHJZRFhMu3bt+fkyZOcPn2awoULqx1HZCExMZHly5fj7+/PkSNHqFGjBn5+fvTt25fixYurHc+m\npaam8tZbb2Fvb2+1K9qePn0aDw8PVqxYQdeuXdWOI4xEJnQKk9i0aRObNm1i1apVUizM1JUrVwgK\nCmL27Nncvn2btm3bEhoayvvvv2+V38QskV6v58iRI+zfv99q/5/UrFmTd999l9mzZ0u5sCIyciGM\nLikpiddff53KlSsTFhZmFTPbrYWiKP9sdrV27VqKFClCv3798PX1pUaNGmrHE/9y9+5d3NzcaN++\nPfPnz1c7jkktWLCAvn37cuHCBYtddVQ8zTqrsFDVtGnTuHjxIv7+/lIszERCQgJ6vZ569erRrFkz\nTp06xYwZM7h69SrTp0+XYmGGxowZQ3JyMj/++KPaUUyuc+fOFC9enLlz56odRRiJjFwIo7p27Rru\n7u4MGDDAIjdVsjaXLl0iMDAQvV7PvXv3aN++PRqNhlatWknxM2PHjh2jfv36TJ48mWHDhqkdp0AM\nHjyYdevWcenSJRwc5Iq9pZNyIYzqs88+Y/v27URGRvLCCy+oHccmKYrCzp070Wq1rF+/nmLFiuHp\n6Ymvry9Vq1ZVO554DkVRaN68OTExMRw/fhwnJye1IxWIw4cP06BBAzZs2ED79u3VjiPySeqhMJrf\nf/+dZcuWMXfuXCkWKoiPj2fRokXodDpOnTpFrVq1CAwMpFevXhQpUkTteCKHVqxYwZ49e9i6davN\nFAuA+vXr88Ybb6DX66VcWAEZuRBGkZqaSoMGDXB2drbqme3m6MKFCwQEBDB37lxiY2Pp2LEjGo2G\nFi1ayKUPCxMfH4+7uztvvvkma9euVTtOgQsKCkKj0XDlyhXKlSundhyRD/IdQBjFzJkzOXbsGFqt\nVopFAVAUhW3bttGhQweqV6/O/PnzGTBgABcuXGDNmjW0bNlSioUFmjhxIrdv37bZ+Uo9evTAycnJ\n6u+OsQUyciHy7c6dO9SoUYNPPvmEOXPmqB3Hqj18+JCFCxei0+k4c+YMderUYciQIfTo0cOit+AW\ncP78eTw8PBgxYgTjxo1TO45q+vTpw759+4iMjJQfVCyYlAuRb4MGDWLZsmVERkZSpkwZteNYpXPn\nzqHT6Zg/fz7x8fF88sknaDQamjRpIiMUVqJjx44cPXqUM2fO2HRR3Lt3L02aNGH79u20bNlS7Tgi\nj2RCp8iXI0eOMHPmTKZNmybFwsjS0tLYunUrWq2W0NBQSpcujZ+fHz4+PrzyyitqxxNGFBoayoYN\nG1ixYoVNFwuAxo0b4+7ujl6vl3JhwWTkQuSZoig0adKEe/fucfToURwdHdWOZBUePHjA/PnzCQgI\n4Ny5c9SvXx+NRkP37t1xcXFRO54wsuTkZGrXrk2FChXYvn27jEQBU6ZMYdSoUVy/fp1SpUqpHUfk\ngVzQEnm2dOlS9u3bh1arlWJhBGfOnMHPz4+KFSsyfPhw6tevz759+zh48CB9+/aVYmGlZsyYwfnz\n55kxY4YUi8d69+6NoigsXrxY7Sgij2TkQuTJw4cPcXd3p3HjxqxcuVLtOBYrNTWVzZs3o9VqCQsL\no0yZMgxLOoBJAAAgAElEQVQcOBAfHx/Kly+vdjxhYtevX8fd3Z1+/frh7++vdhyz0qVLF86cOcPx\n48eldFkgGbkQeTJ+/Hju37/PlClT1I5ike7fv8/UqVNxc3OjY8eOPHjwgEWLFnH58mV++OEHKRY2\nYuTIkbi4uDB27Fi1o5gdLy8vTp48SXh4uNpRRB7IhE6Ra5GRkUybNo3Ro0dTuXJlteNYlFOnTqHV\nalm0aBEpKSl07dqVpUuX0qhRI7WjiQL2xx9/sGjRImbNmkXJkiXVjmN2WrduTeXKldHr9bz99ttq\nxxG5JJdFRK4oikK7du04ffo0ERERFC5cWO1IZi81NZUNGzag1WrZsWMH5cqVw8fHhwEDBvDyyy+r\nHU+oIDU1lYYNG2JnZ0d4eDj29vZqRzJLP/zwA5MnT+bGjRsUK1ZM7TgiF+SyiMiVjRs3EhoaytSp\nU6VYPMfdu3eZPHky1apV45NPPuHRo0csXbqUixcvMmbMGCkWNmzOnDkcPnwYrVYrxSIb/fr149Gj\nRyxfvlztKCKXZORC5FhiYiK1atWiWrVqbN26VSZZZeH48eNotVoWL15MWloaPXr0QKPR0KBBA7Wj\nCTNw7949atSoQbt27ViwYIHaccxeu3btuH37tsy9sDAy50Lk2NSpU7l8+TKbNm2SYvEMg8HA2rVr\n0Wq17NmzhwoVKjB69Gi8vb1lcTHxlDFjxpCcnMyPP/6odhSL4OXlxaeffsrx48epU6eO2nFEDsll\nEZEjV65cYcKECfz3v//ltddeUzuO2bh16xYTJ06kSpUqdOnSBUVRCAkJITo6mlGjRkmxEE85fvw4\ngYGBjBkzRnb9zKH27dtTtmxZ9Hq92lFELshlEZEjPXr0YOfOnURGRlK8eHG146juyfXyZcuWYWdn\nx2effYZGo6FevXpqRxNmSlEUWrRowc2bNzl+/DhOTk5qR7IYI0eOZObMmVy/fl3melkIGbkQz7V7\n926WL1/OTz/9ZNPFIiUlhRUrVtC4cWMaNGjAjh07GDt2LFevXmXOnDlSLES2QkJC2L17N9OnT5di\nkUuenp7cv3+fNWvWqB1F5JCMXIhsGQwG6tevT5EiRdi3b59NboEcExPDrFmzCA4O5vr16zRv3pwh\nQ4bQoUMHHBxk2pJ4vvj4eF577TXq16/PunXr1I5jkVq0aAHAzp07VU4ickK+MopsBQcHc/LkSf76\n6y+bKxYHDhzA39+fkJAQ7O3t+fzzz/Hz86N27dpqRxMWZtKkSdy6dYtp06apHcVieXl50atXL86d\nO0eNGjXUjiOeQ0YuRJZu375NjRo16Ny5M7Nnz1Y7ToFITk5m5cqVaLVawsPDefXVV/H19aV///68\n+OKLascTFuj8+fN4eHjw1VdfMX78eLXjWKxHjx5Rvnx5fHx8mDRpktpxxHNIuRBZGjhwICEhIURG\nRvLSSy+pHcekbty4wcyZMwkODiYmJoZWrVqh0Who166dLHIk8uWjjz7iyJEjnD59miJFiqgdx6IN\nGTKEkJAQrly5IjsxmznbGucWOXbo0CFmz57NDz/8YLXFQlEU9u/fz2effUalSpWYMmUKn376KadO\nnSIsLIyOHTtKsRD5smXLFtavX8+UKVOkWBiBl5cXMTExbNq0Se0o4jlk5EJkoCgKjRs35uHDhxw5\ncsTqJi0mJiayYsUKtFothw4dolq1avj5+dG3b19KlCihdjxhJZKTk6lduzbly5dnx44dsvCckTRs\n2JAyZcqwceNGtaOIbFjXdw1hFIsXL2b//v3s3LnTqorF1atXCQ4OZtasWdy6dYsPPviAjRs30rZt\nW5ubrCpMz9/fn6ioKFatWiXFwoi8vb3x8fHh6tWrVKxYUe04IgsyciGeEhsbi7u7O02bNmXFihVq\nx8k3RVHYu3cvWq2WX3/9FVdXV/r27Yuvry/u7u5qxxNW6saNG7i5udG3b1+0Wq3acazKw4cPKVeu\nHF9//TXfffed2nFEFqRciKeMGDECnU7HmTNnqFSpktpx8uzRo0csW7YMrVbL0aNHcXd3x8/Pj969\ne9v0QmCiYPTp04dNmzZx7tw5SpYsqXYcq+Pp6cn27du5cOGCjDqaKfm/Iv5x9uxZpk+fzrfffmux\nxeLy5cuMHDmSV155BS8vLypUqMCWLVuIiIjAz89PioUwuT/++IOFCxcyceJEKRYm4u3tzaVLl/jt\nt9/UjiKyICMXAki/fNC2bVsiIyOJiIjAxcVF7Ug5pigKu3fvRqvVsnbtWooWLYqnpyeDBw+mevXq\nascTNiQ1NZVGjRqhKAp//fWX3G1kIoqiULt2bTw8PAgJCVE7jsiE9czWE/myYcMGtm7dytq1ay2m\nWCQkJLB48WJ0Oh0nTpygZs2a6HQ6Pv/8c4oWLap2PGGD5s6dy6FDh9i3b58UCxOys7PDy8uLESNG\ncOvWLau9Xd6SyciFIDExkVq1alGjRg1CQ0PNfmZ7dHQ0gYGBzJkzh/v379OhQweGDBlCy5YtzT67\nsF737t3Dzc2Ntm3bsnDhQrXjWL07d+5Qvnx5Jk6cyLBhw9SOI54hcy4EU6ZM4cqVK8yYMcNsvzkr\nisJvv/3GRx99RLVq1dDr9Xh6enL+/HnWrVvHe++9Z7bZhW34/vvvSUxM5KefflI7ik0oVaoUn376\nKXq9HvkZ2fxIubBxly9fZuLEiXzxxRdmeWtmXFwcQUFB1KpVi9atW3PhwgVmzpzJtWvX+Pnnn6lS\npYraEYXgxIkTBAYGMmbMGMqVK6d2HJvh5eXFmTNn2Ldvn9pRxDPksoiN69atG3v27OHs2bNmdSdF\nVFQUAQEBzJs3j4cPH/Lxxx+j0Who1qyZjFAIs6IoCi1btuT69eucOHECJycntSPZjLS0NGrUqEGT\nJk2YP3++2nHEv8jIhQ3buXMnISEhTJ482SyKRVpaGlu3bqVdu3a4ubmxaNEiBg0aRHR0NKtXr6Z5\n8+ZSLITZWblyJbt27WLGjBlSLApYoUKF8PT0JCQkhAcPHqgdR/yLjFzYKIPBwBtvvEGxYsXYt2+f\nqt+0Y2NjWbBgATqdjsjISOrVq4dGo6FHjx4ULlxYtVxCPE98fDw1a9akXr16rF+/Xu04Nun69etU\nqlQJrVbLoEGD1I4jHpNbUW1UUFAQp06d4uDBg6oVi8jISHQ6HfPnzychIYFOnToxZ84cGjduLCMU\nwiL8+OOP/P3330ybNk3tKDarfPnytGvXDr1eL+XCjMjIhQ26desWbm5udO3alZkzZxboe6elpREa\nGopWq2Xr1q289NJLDBgwAB8fH9mESFiUCxcu4OHhwfDhwxk/frzacWzahg0b6NixI4cOHaJ+/fpq\nxxFIubBJ3t7erF69msjISEqXLl0g73n//n3mzZtHQEAA58+fp0GDBgwZMoSuXbtazKJdQvzbxx9/\nzKFDhzhz5gxFihRRO45NMxgMVK5cmY8++ojAwEC14whkQqfNOXjwIHPmzGHcuHEFUiwiIiIYPHgw\nFStWZMSIETRs2JA//viDAwcO0Lt3bykWwiJt3bqVdevWMWXKFCkWZsDBwYF+/fqxZMkSEhIS1I4j\nkJELm5KWlkbjxo2Jj4/n8OHDODiYZspNamoqGzduRKvVsn37dsqWLYuPjw8DBw6UNQCExUtOTqZO\nnTq8/PLL7Ny5U+YHmYkLFy5QrVo1FixYQO/evdWOY/NkQqcNWbRoEX/++Se7du0ySbG4d+8ec+bM\nISAggIsXL9KoUSMWL15Mly5d5BY9YTW0Wi3nzp0jJCREioUZqVq1Kq1atWL27NlSLsyAjFzYiNjY\nWNzc3GjRogXLli0z6mufOHECrVbL4sWLSU1NpVu3bmg0Gt566y2jvo8Qartx4wbu7u707t0bnU6n\ndhzxjBUrVtC9e3dOnz7Na6+9pnYcmyblwkrExcURFRVFUlISzs7OVK9e/amdQYcPH05QUBBnz541\nyl0ZBoOB9evXo9Vq2bVrF+XLl2fQoEF4e3tTtmzZfL++EOaob9++bNy4kcjISF588UW144hnJCUl\nUaFCBfr168fPP/+sdhybJpdFLFhERATBwcGEbd7M2QsXntq8x87ODveqVWn94Ye0bt2aGTNmMHbs\n2HwXizt37qDX6wkMDOTy5cs0btyY5cuX8+mnn+Lo6JjfD0kIs7V//34WLFhAcHCwFAsz5ezsTO/e\nvVmwYAETJkyQy7EqkpELCxQdHc3ggQPZEhZGGQcHOhkMvAV4AK5AAhABHABWOzjwt8FA0cKFOXD4\ncJ6HCo8ePYpWq2Xp0qUoikKPHj3QaDRyT7mwCWlpaTRs2JC0tDQOHDiAvb292pFEFk6dOsXrr7/O\nypUr6dy5s9pxbJaUCwuj1+v5QqOhtMHARIOBzkB23TwZWAWMLFSIu05OTNdq8fLyytF7paSksGbN\nGrRaLXv37qVixYoMHjwYLy8vXnrpJSN8NEJYBr1ej7e3N3v37qVx48ZqxxHP8Z///IdixYqxdetW\ntaPYLkVYjPHjxyuA4gVKLChKLn7FPn4eoIwfPz7b94mJiVHGjx+vVKhQQQGUpk2bKitXrlRSUlIK\n6CMVwnzcu3dPKV26tNKrVy+1o4gcmjt3rmJnZ6dER0erHcVmSbmwELNnz1YAZVwuS8Wzv354XDD0\nen2G9zhw4IDSu3dvxcnJSXFxcVG8vLyUo0ePqvDRCmE+hgwZohQtWlS5du2a2lFEDj18+FApVqyY\nMmbMGLWj2Cy5LGIBoqOjqe3hQY/ERGY/cy4emAz89fjXPWA+kNVd3gowAFjm4sKJiAgqVKjA6tWr\n0Wq17N+/n8qVKzN48GA8PT0pVaqUiT4iISzDyZMnqVevHhMnTmTEiBFqxxG5MHDgQDZv3szFixdl\njowKpFxYgLbvv8/pnTs5YTBQ7Jlzl4AqQGWgKrALmEfW5QIgFqhtb49z5co8TEjg5s2btGzZEo1G\nQ4cOHeQTUQhAURTee+89rl69yokTJ3B2dlY7ksiFgwcP8tZbb7Fp0yY+/PBDtePYHNlbxMxFRESw\nJSyMiZkUC4DywE0gmvQRjJw0xeLApNRUzl24QLNmzTh58iTbt2/n448/lmIhxGOrVq1i586dzJgx\nQ4qFBWrQoAF169ZFr9erHcUmSbkwc8HBwZRxcCCrG6ocgTJ5eN1OQBl7e8qUKUOtWrXyHlAIK5SQ\nkMCwYcPo0KEDbdu2VTuOyAM7Ozu8vLzYsGEDN2/eVDuOzZFyYebCNm+mk8GQ7e2meeEMdEpN5bfQ\nUCO/shCW78cffyQmJoapU6eqHUXkQ8+ePXFwcGDBggVqR7E5Ui7M2MOHDzl74QKm2qHjTeDM+fPE\nxcWZ6B2EsDzR0dFMnjyZ4cOHU716dbXjiHwoWbIknTt3Rq/XI9MLC5aUCzN2/vx5FEXBw0SvX4v0\nSWtRUVEmegchLM/QoUMpXbo033zzjdpRhBF4eXkRFRXF7t271Y5iU2RvETOWlJQEpC/pbQqFH//e\npk0bSpYsiaurq9F+FS5cGFdXVxwdHWVbamExtm3bxtq1a1m2bNlTG/8Jy9W0aVNq1KiBXq+nefPm\nwPM3ehT5J+XCjD2ZoZ5gotd/9Pj39u3bU7x4cRISEp76de/evQzHHj16RHx8PKmpqTl6D3t7e6OW\nlmfLy5NfcpeLyK/k5GT++9//0rRpU7p166Z2HGEkTyZ2jh49miJFirBn+/ZsN3r08fHBw8NU48W2\nQ9a5MGNxcXEUL16cOYpCvxw8/hDwFtkvovVvcwEvOztiY2Nz3dpTUlIyFA9j/Xr06NE/f87pP08n\nJyeTFxgXFxcKFZIridZq6tSpfPXVVxw+fJi6deuqHUcYSXR0NJ79+rFz925eKlSIzmlpz93osU3r\n1gTOnEmVKlXUjG7RpFyYuZrVq9Pi/HkCc/DY3JaLwcCu6tWJOHcuHwlNR1EUkpKSTFpeEhISSExM\nzHGmZwuHsQuMq6srTk5OcimpgN28eRM3Nzc+//xzAgIC1I4jjCSvGz1+4+DAHQeHXG30KJ4ml0XM\nXOsPP2RFUBDTs7kdNQC4D1x7/N/rgSuP/zwEMl18K4n0lt7NjO/ht7Ozw8XFBRcXF1588UWTvU9q\naiqJiYlGKS43btzItMAkJCSQkpKSozyFChUyeYFxdXXFwUE+/Z/45ptvcHR0ZNy4cWpHEUYyYcIE\nRo8ejRcwlcy/Dj7LCfgM6GAwMNRgwNvbm5iYGEaNGmXSrNZIRi7MXEREBLVq1WIJ6f/oM1MFuJzF\nuWigUibHlwI9H79+zZo18x9UPFdKSkqmpcNYIzAJCQnEx8fn+FKSo6OjyQtM4cKFzf5S0p9//sk7\n77xDUFAQPj4+ascRRqDX6/H29mYcMDofrzMOGPP49Tw9PY0TzkZIubAA2e0tkhexQG0HBzxatCB0\n2zYjvKIwF4qikJycbNIC8+R4Trm4uJisvDz55ezsnKdLSWlpaTRq1AiDwcDBgwdlYrAVyG6jx4Ok\nXzbeBVwESgFvA+OBGpm81rMbPcocjJyTcmEBsvtkyS35ZBHGkJaWZpRLSc8byUlOTs5RHjs7uzyV\nlhMnThASEsKoUaOoW7fucx/v6Oho4r/Z7MXGxvL+++8btZhZwuhSbmT3w1gX4I/Hv9chfV8mLRAH\nhEOmawrJD2N5I+XCQhhjmE8hvaHLMJ+wFAaDIV+XkrJ7blxcHLdv387Vyo0ODg4mHYF58pisRlCu\nX79OhQoVjPXX+4/8ji7l5OPK6+hSbjzvMvKfpK9M/O/ZRlFAbdILx8IsXlcuI+eezOiyEF5eXsTE\nxDB69GgukfMJSk/EAsMAPekTnaRYCEvg4OBAsWLFKFbMGBcEn/bFF1+g1+s5c+YMZcqUMUqBiY2N\n5ebNm1k+NqecnZ0z/QZtKomJiSQmJnL37l2TvUdeR5dyU2ACAwPTN3o0GDLN8HYmx6qTvlrx6Wyy\ndwK+dHAgKCgIf3///P9l2AApFxZk1KhRlC1bli80GrYZDEzKwa1VScBq/v/WKr1OJ8VC2LyTJ0+i\n0+mYMGECFStWBNLXSilRooTJ3lNRlDxfSnpSYK5fv26yfKamKArx8fHEx8eb7D0cAS+y/5qYmRjg\n9WzOOwOdDAbZ6DEX5LKIBYqOjmbwwIFsCQujjIMDnQwG3iS9fRcmfeXNU6RPXpJFYYR4mqIotGrV\niitXrnDixIl/VsK1BE/ubBFZmws5WnTwicWkrws0D+jznNfN66KDtkhGLixQlSpVCN22jYiICIKD\ng/ktNJTgx5ucPWFnZ8dr1arRrW1bBg0aJNcJhXhs9erV7Nixg02bNllUsYD0yyWNGjXKdHQjp+uo\nWLvcLNx9BvADGvP8hQf/vdFjvXr18hrPZsjIhZWQjXiEeL6EhARq1qxJnTp12LBhg9pxjCo366jk\nZ5JsWlqa2h9qto6TPkHzeWKA/wBpwH7g5Ry8bl3SR48aNWqUr4y2QEYurETRokWlTQvxHD/99BM3\nb95k+/btakcxOkdHRxwdHSlevLjJ3iM366jk9y6fvMrJtNlYoM3j3/fy/GIB/7/Ro6WNdqlFyoUQ\nwiZER0fz008/MWzYMKpXr652HItkZ2eHs7Mzzs7OlCxZ0mTvk5N1VJ4tL/fv3+enH38kAshuXCEJ\naE/6LajbAfccZjpF+scv/3ZyRi6LCCFswqeffspff/3FmTNn5JKhlXreRo9pwCfAFtL3YPogF69t\n7hs9mhsZuRBCWL2wsDDWrFnD0qVLpVhYIYPBwLp163iYmMgKYDqZ3446FNgAdARuA0ueOd8zi9e3\nhI0ezY2MXAghrFpKSgp169aldOnS7N69W7aztyJ///03s2fPJjg4mKtXr/LGG29w5MiRLFfobAHs\nyeb1UrM4Lit05p71LCgvhBCZ0Ol0nD17Fn9/fykWVuKvv/6id+/evPLKK4wfP54PPviAw4cPc/jw\nYdq0bs23Dg48zOR5O0kvEFn9ykws6YsQtmndWopFLsjIhRDCasXExODm5kbPnj0JDMzqSrywBImJ\niYSEhKDT6Thw4ACvvvoqgwcPpn///pQqVeqfx8lGj+ZBRi6EEFbrm2++wcHBgXHjxqkdReTRlStX\n+Pbbb3nllVfo06cPJUuWZP369URFRfHVV189VSwgfZHB6VotetI3asyrJxs96oEZOp0Ui1ySCZ1C\nCKsUHh7OvHnzCAwMzPANSJg3RVHYtWsXOp2OtWvXUqRIEfr168fgwYNxd3/+zaOy0aP65LKIEMLq\npKWl8fbbb5OcnMyhQ4ey3MJcmJe4uDgWLVqETqcjIiICDw8P/Pz86NWrV552xtXr9Xyh0VAqjxs9\nzpCNHvNMyoUQwurMnTsXT09P9uzZQ5MmTdSOI54jMjKSgIAA5s+fT1xcHB999BEajYbmzZvnexKu\nbPSoDikXQgircv/+fdzc3GjdujVLljy7koEwF6mpqYSGhqLT6di6dSulS5fG29sbHx8fKlWqZPT3\n+/dGj2ey2OixlWz0aDRSLoQQVuXLL79k9uzZnD17lgoVKqgdRzzj7t27zJ07l8DAQKKjo3nzzTfR\naDR07doVFxeXAskgGz2anpQLIYTVOHXqFHXr1mX8+PGMHDlS7TjiX44ePYpOp2PJkiWkpaXRtWtX\nNBoNDRs2VDuaMAEpF0IIq6AoCq1bt+bSpUucPHlSdq80AykpKfz666/odDr27t1LhQoVGDRoEF5e\nXpQtW1bteMKE5FZUIYRV+PXXX9m+fTsbN26UYqGyGzduMGvWLGbOnMmNGzdo3rw5q1at4qOPPsLB\nQb7t2AIZuRBCWLyEhARq1qxJ7dq12bhxo9pxbJKiKOzfvx+tVsuqVatwcnLi888/x9fXl9q1a6sd\nTxQwqZBCCIs3efJkbt68yW+//aZ2FJvz6NEjli1bhk6n48iRI1SvXp2ff/6Zvn37UqJECbXjCZXI\nyIUQwqJdvHiRmjVr8sUXXzBp0iS149iM6OhogoKCmDNnDvfu3ePDDz/Ez8+P999/n0KFZGcJWyfl\nQghhcS5evMipU6do164dnTp14s8//+Ts2bNyO6GJpaWlsX37drRaLRs3buSFF17A09OTQYMGUa1a\nNbXjCTMil0WEEBZn6NChrFmzhkaNGhEeHs6SJUukWJhQbGwsCxYsICAggLNnz1KnTh1mzpxJz549\ncXV1VTueMEMydiWEsChhYWGsWbMGSN+czM7OjmPHjhEXF6dyMusTERGBr68vFSpU4Msvv6Ru3brs\n2bOHo0eP4u3tLcVCZEkuiwghLEZKSgp169bl9OnTGc4NHz6cn3/+WYVU1sVgMLBx40a0Wi07duyg\nbNmyDBw4kAEDBsiKpyLH5LKIEMJi6HS6TItFyZIl+frrr1VIZD1u376NXq8nKCiIy5cv884777Bk\nyRI6d+6Mk1N2e4kKkZGMXAghLEJMTAxubm7ExsZmOKfT6fD19VUhleU7ePAgOp2O5cuXA/DZZ5/h\n6+tLgwYNVE4mLJmUCyGERejfvz/z5s3LcLxOnTocOnRIVn7MhaSkJFauXIlOpyM8PJzKlSszePBg\n+vfvT+nSpdWOJ6yAfDYKIcxeeHh4psUCwN/fX4pFDl29epXg4GBmzZrFrVu3aNWqFWvXrqV9+/bY\n29urHU9YEfmMFEKYtbS0NDQaTabnunfvTrNmzQo4kWVRFIU9e/ag0+lYs2YNhQsXpm/fvgwePJia\nNWuqHU9YKbksIoQwa3PnzsXT0zPDcVdXV86ePUvFihVVSGX+4uPjWbx4MTqdjpMnT/Laa6/h5+fH\n559/TvHixdWOJ6ycjFwIIczW/fv3GTlyZKbnRo0aJcUiE1FRUQQEBDBv3jwePnxIx44dmT59Oi1b\ntsTOzk7teMJGSLkQQpitsWPHcuvWrQzHq1WrxtChQ1VIZJ7S0tLYsmULOp2O0NBQSpUqhY+PD4MG\nDaJy5cpqxxM2SC6LCCHM0qlTp6hbty6pqakZzq1fv54OHTqokMq83Lt3j3nz5hEYGMj58+epX78+\nGo2Gbt26UbhwYbXjCRsmIxdCCLOjKAr//e9/My0Wbdu2pX379iqkMh/Hjx8nICCAxYsXk5KSQteu\nXVm8eDGNGjWSSx/CLMjIhRDC7KxevZrOnTtnOO7o6MjJkydxc3NTIZW6UlJSWLt2LTqdjj179lC+\nfHl8fHwYMGAAZcuWVTueEE+RkQshhFlJSEjIcj7Fl19+aXPF4ubNm8yePZvg4GCuX79O06ZNCQkJ\n4eOPP8bR0VHteEJkSsqFEMKsTJ48mcuXL2c4Xq5cOUaPHq1CooKnKArh4eHodDpCQkJwcHDg888/\nx9fXlzp16qgdT4jnkssiQgizcfHiRWrWrEliYmKGc4sWLaJXr14qpCo4jx49YsWKFeh0Og4dOkTV\nqlXx9fWlX79+lCxZUu14QuSYjFwIIczGsGHDMi0W//nPf+jZs6cKiQrGpUuXCAoKQq/Xc+fOHdq2\nbcumTZto06YNhQoVUjueELkmIxdCCLPw22+/0bp16wzH7ezsOHjwIPXr11chlekoisKOHTvQ6XSs\nX7+eYsWK0b9/fwYNGkSNGjXUjidEvsjIhRBCdSkpKQwZMiTTcwMGDLCqYvHw4UMWLlyITqfjzJkz\nvP766wQFBdGzZ0+KFCmidjwhjELKhRBCdTqdjtOnT2c4XrJkScaPH69CIuM7c+YMAQEBLFiwgISE\nBD755BOCg4Np2rSprE0hrI5cFhFCqComJgY3NzdiY2MznNPpdPj6+qqQyjhSU1PZtGkTOp2OsLAw\nypQpw4ABAxg4cKDsiyKsmoxcCCFU9c0332RaLGrXrs3AgQNVSJR/d+7cYc6cOQQGBnLp0iXefvtt\nFi9eTOfOnXF2dlY7nhAmJyMXQgjV/PXXXzRq1CjTc7t27aJZs2YFnCh/Dh8+jE6nY9myZSiKQvfu\n3fHz8+PNN99UO5oQBUpGLoQQqkhLS8PPzy/Tc926dbOYYpGcnMzq1avR6XT88ccfvPLKK3z//fd4\nes453fYAAApPSURBVHry0ksvqR1PCFVIuRBCqGLBggUcOHAgw3FXV1d+/vlnFRLlzvXr15k5cyYz\nZ84kJiaG9957jzVr1tC+fXscHORLq7Bt8hkghChwDx48YOTIkZme+/bbb3nllVcKOFHOKIrC3r17\n0el0/Prrrzg7O9OnTx98fX3x8PBQO54QZkPKhRCiwI0dO5a///47w/GqVasybNgwFRJlLz4+nqVL\nl6LT6Th+/Dhubm5MnTqV3r1788ILL6gdTwizIxM6hRAFKiIigrp162IwGDKcW7duHR07dlQhVebO\nnz9PUFAQc+bM4cGDB3To0AE/Pz/ee+89WZZbiGzIyIUQosAoisKQIUMyLRZt2rShQ4cOKqR6Wlpa\nGtu2bUOn07F582ZKlCiBt7c3gwYNokqVKmrHE8IiyMiFEKLA/Prrr3Tq1CnDcUdHR06cOIG7u7sK\nqdLdv3+f+fPnExAQQFRUFPXq1UOj0dC9e3dcXV1VyyWEJZKRCyFEgUhISGDo0KGZnvviiy9MXiwM\nBgMbNmygVKlSNG3a9J/jJ0+eJCAggEWLFpGUlESXLl1YsGAB77zzjizLLUQeSbkQQhSIn3/+mUuX\nLmU4/vLLL/Pdd9+Z7H1v3bqFXq8nKCiIK1eu0KJFC7Zt28a6devQ6XTs2rWLcuXKMWLECLy9vSlX\nrpzJsghhK+SyiBDC5C5evEjNmjVJTEzMcG7hwoV8/vnnRn/PgwcPotPpWL58OUlJSU+dK1u2LDEx\nMbz77rv4+fnx6aef4ujoaPQMQtgqGbkQQpjc8OHDMy0W77zzDr169TLa+yQlJbFy5Up0Oh3h4eFZ\nPq5kyZJs2bKFevXqGe29hRD/T0YuhBAmtX37dlq1apXhuJ2dHQcPHqR+/fr5fo+rV68SHBzMrFmz\nuHXr1nMf7+rqyrVr1yhRokS+31sIkZGMXAghTCYlJYUhQ4Zkes7b2ztfxUJRFHbv3o1Op2Pt2rWk\npqbm+Lkvv/wyFy5cMEqxEUJkJOVCCGEyAQEBREREZDheokQJxo8fn6fXjIuLY8mSJeh0Ok6ePJmr\n57Zp0wY/Pz/atGmDvb19nt5fCPF8cllECGESMTExuLm5ERsbm+GcVqvNckfUrJw7d47AwEDmzZvH\ngwcPcvy84sWL079/fwYPHkyNGjVy9Z5CiLyRkQshRL7ExcURFRVFUlISzs7OVK9enaJFi/Ltt99m\nWixq166Nj49Pjl47LS2NLVu2oNVq2bJlS65y1apVC41GQ8+ePSlatGiuniuEyB8pF0KIXIuIiCA4\nOJiwzZs5e+EC/x4AtbOz49Xy5Ym+di3T52q12uduSX7v3j3m/V979xMadXYAcPw78Uei1TaHGm+C\nMSNdE5ZetpXSgigxbUSp1D9htxIrJg7RCVhqCwHpJc3uoWXbJbFk6bSCaGtrBbGwyqYgReiKu3uo\nstM9TBy8aWl7iO5qkh9NDz9tIZmZTDZPdjb5fo4z7/fL8xD8Zub93jtzhtOnT3P37t2q57VixQr2\n7NlDNptl69atboIlfUr8WkRS1YrFIscyGa6NjbEuitgbx3wFaAU+B3wM5IF3gd8D/wbqgP88vb6r\nq4sLFy6Uvf/t27cZGRnh3LlzPH78uOp5NTU1cfToUTKZTM0e1y4tJ8aFpKrkcjlO9PezNo55NY7Z\nB9RXGD8F/BH4IXAfiOrrKRQKc/7zn56e5vLlywwPD3Pjxo0FzWnLli1ks1n2799PQ0PDwv5Bkp4b\nzwyWNK+hoSF6e3t5+ckT7sQxr1A5LHj6/ivAh8BhYGpqirNnz/7v/fv37zM4OMiGDRs4cOBA1WFR\nX19Pd3c3t27d4ubNmxw8eNCwkGqMn1xIqiiXy9Hb28sgcGoR9xkEfgwMDAxw7949Ll68yPT0dNXX\nr1+/nr6+Pnp6emhqalrETCQ9b8aFpLKKxSIvtrby8pMn/GrWe38BtpW4JgW8A3x11uszQC9whv+v\nwajG9u3byWaz7N69e96FoJJqg7+pkso6lsmwNo55vcKYE8BLs15LlxiXAl4HrpKswagUGKtXr6a7\nu5vjx4/T1ta2oDlL+vQZF5JKyufzXBsb4zzw+QrjvgF8p8p7fgH4KfDdMu9v2rSJbDbLoUOHaGxs\nXMBsJdUS40JSSaOjo6yLIvbF8bxjHwGrgGo21N4L9JM8pgrJvhi7du0im83S3t5OXZ3rzKXPOn+L\nJZU09tZb7I3jeZ8KOUzyicRKYDvw/jzjG4AuoKGujpMnTzI+Ps6VK1fo6OgwLKQlwgWdkuZ4+PAh\njY2N/HpmhsNlxrwD/BzYCawl2TzrZ8BHwF+BL1e4/2+AnlSKiYkJt+aWliD/TJA0x/j4ODMzM7RW\nGPM14A/A94BdwI9IggNgYJ77t5EcmV4oFBY7VUk1yLiQNMfk5CSQbOm9EC3At4HrJI+elrNq1s+R\ntLQYF5LmeLbj5cef4Nr1JFt/f1RhzLNTQ9xZU1qajAtJc6TTaVKpFPlPcO04yeLOSispPiB5SiSd\nLrUjhqTPOuNC0hxr1qzhSxs38m6FMf8s8drfgD8B35zn/u8BL7S0uJhTWqKMC0kl7di5k0tRxFSZ\n97tIFnK+CuSA7wNfJ/nE4rUK950ELkUR7Z2dIacrqYb4KKqkkvL5PG1tbZwnOd10thHgPFAAJoAm\noJ3kcLKNFe77W5IdOvP5PJs3bw47aUk1wbiQVFZnRwd/v36dO3FccQvwak0AL0YRrdu2cfXttwPc\nUVItMi4klVXpVNSFmgGOAr9buZI7+TzNzc0BZiipFrnmQlJZzc3N/GJ4mBzwk0XcZ+bp9TngjZER\nw0Ja4jy4TFJFPT09PHjwgFOnTnGP5Nj0hXxFMgH8gCQshoaGOHLkyPOYpqQa4tcikqqSy+U40d/P\nF+OY1+KYfVDxULNJ4BIwEEX8K4p4Y2TEsJCWCeNCUtWKxSLHMhmujY2xLorYG8e8RHJWyCqSnTc/\nINnH4lIU8Y845ls7dvDLN9/0qxBpGTEuJC1YPp9ndHSUP1+9yodPDzl7JpVK8UJLC+2dnfT19fm4\nqbQMGReSFuXRo0cUCgUmJydpaGggnU6786a0zBkXkiQpKB9FlSRJQRkXkiQpKONCkiQFZVxIkqSg\njAtJkhSUcSFJkoIyLiRJUlDGhSRJCsq4kCRJQRkXkiQpKONCkiQFZVxIkqSgjAtJkhSUcSFJkoIy\nLiRJUlDGhSRJCsq4kCRJQRkXkiQpKONCkiQFZVxIkqSgjAtJkhSUcSFJkoIyLiRJUlDGhSRJCsq4\nkCRJQRkXkiQpKONCkiQFZVxIkqSgjAtJkhSUcSFJkoIyLiRJUlDGhSRJCsq4kCRJQRkXkiQpKONC\nkiQFZVxIkqSgjAtJkhSUcSFJkoIyLiRJUlDGhSRJCsq4kCRJQRkXkiQpKONCkiQFZVxIkqSgjAtJ\nkhSUcSFJkoIyLiRJUlDGhSRJCsq4kCRJQRkXkiQpKONCkiQFZVxIkqSgjAtJkhSUcSFJkoIyLiRJ\nUlDGhSRJCsq4kCRJQRkXkiQpKONCkiQF9V8j2OgXyMGWfwAAAABJRU5ErkJggg==\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x10c41e1d0>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"#試しに描画してみる\n",
"# Position nodes using Fruchterman-Reingold force-directed algorithm.\n",
"pos = nx.spring_layout(G, k=5.)\n",
"\n",
"# Draw labels for nodes and edges.\n",
"nx.draw_networkx_labels(G, pos)\n",
"\n",
"# Finish drawing.\n",
"nx.draw(G, pos)\n",
"\n",
"# Display with Matplotlib.\n",
"plt.axis('off')\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[2, 3, 4]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G.successors(1)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"code_folding": [
0
],
"collapsed": false
},
"outputs": [],
"source": [
"# もう少し賢く書くべきか\n",
"# 書き直したので、以後ここはみなくてよい\n",
"def bfsPath(G, s, e):\n",
" '''\n",
" BFSを用いて、sからeへのpathを一つ求める。\n",
" Inputs:\n",
" G: a graph\n",
" s: a start point\n",
" e: an end point\n",
" Output:\n",
" path: a list of edges which represents a path from s to e.\n",
" the number of nodes the path contains is smallest.\n",
" '''\n",
"\n",
" past = [] # 過去に訪れた点を記録\n",
" path = []\n",
"\n",
" # 全ての点のsからの距離の初期値を無限大に\n",
" for p in G.nodes():\n",
" G.node[p]['dist'] = float('inf')\n",
" \n",
" # node s の距離を0に\n",
" G.node[s]['dist'] = 0\n",
" \n",
" # sに隣接する点をqueueに\n",
" queue = deque(G.successors(s))\n",
" \n",
" # sに隣接する点の距離を1に\n",
" for p in G.successors(s):\n",
" G.node[p]['dist'] = 1\n",
" \n",
" # この部分がBFS\n",
" while len(queue)>0:\n",
" v = queue.popleft()\n",
" if v == e: break\n",
" else:\n",
" past.append(v)\n",
" for p in G.successors(v):\n",
" if (not p in past):\n",
" queue.append(p)\n",
" if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
" G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
" \n",
" # pathが存在しない場合はNoneを返す\n",
" if len(G.successors(s)) == 0:\n",
" v = s\n",
" if v != e or v == s:\n",
" print ('There is no path.')\n",
" return None\n",
" \n",
" # 終点から遡ってpathを形成する\n",
" pp = e\n",
" while (1):\n",
" if pp == s:\n",
" break\n",
" pred = G.predecessors(pp)\n",
" for p in pred:\n",
" if G.node[p]['dist'] == G.node[pp]['dist']-1:\n",
" path.insert(0, (p,pp))\n",
" pp = p\n",
" break\n",
" \n",
" return path"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"code_folding": [],
"collapsed": true
},
"outputs": [],
"source": [
"# dequeをimport\n",
"from collections import deque\n",
"\n",
"\n",
"def BFS(G, s):\n",
" '''\n",
" Implementing BFS\n",
"\n",
" Parameters\n",
" ----------\n",
" G=(V, E): a graph\n",
" V's attribute\n",
" v.color, v.parent, v.distance\n",
" s: a starting point\n",
"\n",
" Return\n",
" ------\n",
" None\n",
" '''\n",
"\n",
" # 全ての頂点を初期化\n",
" for v in G.nodes():\n",
" G.node[v]['color'] = 'white'\n",
" for v in G.nodes():\n",
" G.node[v]['distance'] = float('inf')\n",
" for v in G.nodes():\n",
" G.node[v]['parent'] = None\n",
"\n",
" # sについて初期化\n",
" G.node[s]['color'] = 'gray'\n",
" G.node[s]['distance'] = 0\n",
"\n",
" queue = deque()\n",
" queue.append(s)\n",
"\n",
" while len(queue) > 0:\n",
" u = queue.popleft()\n",
" for v in G.successors(u):\n",
" if (G.node[v]['color'] == 'white'):\n",
" G.node[v]['color'] = 'gray'\n",
" G.node[v]['distance'] = G.node[u]['distance'] + 1\n",
" G.node[v]['parent'] = u\n",
" queue.append(v)\n",
" G.node[v]['color'] = 'black'\n",
"\n",
"def BFS_path(G, s, t):\n",
" '''\n",
" Implementing BFS\n",
"\n",
" Parameters\n",
" ----------\n",
" G=(V, E): a graph\n",
" V's attribute\n",
" v.color, v.parent, v.distance\n",
" s: a starting point\n",
" t: an end point\n",
"\n",
" Return\n",
" ------\n",
" a shortest path from s to t\n",
" '''\n",
"\n",
" BFS(G, s)\n",
" path = []\n",
" v = t\n",
" if (G.node[v]['distance'] == float('inf')):\n",
" print('there is no path')\n",
" return []\n",
"\n",
" while (v != s):\n",
" path.insert(0, v)\n",
" v = G.node[v]['parent']\n",
" path.insert(0, v)\n",
" return path"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"BFS(G,1)"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"collapsed": false,
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n",
"1\n",
"1\n",
"1\n",
"2\n"
]
}
],
"source": [
"for v in G.nodes():\n",
" print ( G.node[v]['parent'] )"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"1\n",
"1\n",
"2\n"
]
}
],
"source": [
"for v in G.nodes():\n",
" print ( G.node[v]['distance'] )"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 5]"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"BFS_path(G,1,5)"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[3, 4, 5]"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"BFS_path(G,3,5)"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"there is no path\n"
]
},
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"BFS_path(G,5,1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"# Intro to the Maximum Flow Problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"前節で作ったbfsPathを元に、naive greedy algorithmを実装することがこの節の目標。\n",
"\n",
"とりあえず、例のグラフを作ってみる。"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"G = nx.DiGraph()\n",
"G.add_edges_from([('s','v',{'cap': 3}),('s','w',{'cap': 2}),('v','w',{'cap': 5}),('v','t',{'cap': 2}),('w','t',{'cap': 3})])\n",
"\n",
"#flowを初期化\n",
"for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"code_folding": [
0
],
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAhcAAAFkCAYAAACThxm6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzt3XlcVOXiBvBnYNgUBQVxQTEEHcQsKzUXSFxQcEkRl6F+\nl1vuWnqzrq3Ypmb31rVSS00yzbxgwg1zJdQyFTOrq6mgJCKbCi4osnOY8/sD4YrMDCBn5szyfD+f\nPl7PnDnz8PGiD+c97/sqRFEUQURERCQRG7kDEBERkWVhuSAiIiJJsVwQERGRpFguiIiISFIsF0RE\nRCQplgsiIiKSFMsFERERSYrlgoiIiCTFckFERESSYrkgIiIiSbFcEBERkaRYLoiIiEhSLBdEREQk\nKZYLIiIikhTLBREREUmK5YKIiIgkxXJBREREkmK5ICIiIkmxXBAREZGkWC6IiIhIUiwXREREJCmW\nCyIiIpIUywURERFJiuWCiIiIJMVyQURERJJiuSAiIiJJsVwQERGRpFguiIiISFIsF0RERCQplgsi\nIiKSFMsFERERSYrlgoiIiCTFckFERESSYrkgIiIiSbFcEBERkaRYLoiIiEhSLBdEREQkKZYLIiIi\nkhTLBREREUmK5YKIiIgkxXJBREREkmK5ICIiIkmxXBAREZGkWC6IiIhIUiwXREREJCmWCyIiIpIU\nywURERFJiuWCiIiIJMVyQURERJJiuSAiIiJJsVwQERGRpFguiIiISFJKuQMQEZF1Kyoqwvnz51Fe\nXg4HBwf4+vrC2dlZ7ljUDCwXRERkdCkpKVi7di2Sdu/GuQsXIIpi7WsKhQKqbt0QPHo05syZA39/\nfxmT0v1QiHf/iRIRERlQRkYG5s2ejb1JSfBQKhEuCOgHwB9ACwAlAFIAHAcQr1QiXxAQEhyMz9at\ng7e3t5zRqQlYLoiIyCiio6Pxwvz5cBcEvCcImATAXs/5FQDiALymVOK6UomPV63CjBkzjBOWmoUP\ndBIRkcEtW7YMM2fORERZGU4JAp6C/mKBO68/BeC0ICCirAwzZ87EsmXLDB+Wmo13LoiIyKCio6Mx\nc+ZMLAEQ1YzrLAHw5p3rTZ8+XZpwZBAsF0REZDAZGRno7e+PiLIyrG/mtUQAswDEODriVEoKn8Ew\nYSwXRERkMKEjRyL1hx9wShDQSoLrFQLorVTCf+hQ7Pn+ewmuSIbAZy6IiMggUlJSsDcpCe/dUyxO\nofofn513Hfv9zrG+91wjFMDAu37fGsByQcDepCSkpqYaIjZJgOWCiIgMYu3atfBQKjHpnuMPAnAF\n8NNdxw6h+h+kkwCK7hwTARwFMOSe94cD8FAqsWbNGulDkyRYLoiIyCCSdu9GuCDUmxWiADAY1YWi\nxiEAYXdeS75z7ASqh0EC7nm/A4BwQcC+PXukD02S4AqdRER03wRBwKVLl5CZmYmsrCxkZmYiMzMT\n6enpOJuejpd1vC8QwGIApQCcABwGsBzARVQXjZH4392Me8sFUD18sjY9HUVFRVwq3ASxXBARkU4l\nJSXIysqqUxxq/svKykJOTg6qqqp0vl/Xwt2BACpRPezRGcDVO8dO4393NA7feb+rlvf3AiCKIs6f\nP48+ffrc3xdHBsNyQURkpURRxI0bN+rddbj791evXm3WZ7TQcbwvAEdUP3fRBYAHAF9UF4w1qF6d\n8xCAiTre73Tn1/Ly8mblI8NguSAislBVVVVahyzu/n1xcbFBM5ToOG4HoD+qy4UXqksF7vxaDmAL\ngDwAT+h4f+mdXx0cHKQJSpJiuSAiMlOlpaVahyxqfp+TkwNBEGTNmALgcR2vBQJYAeACgJfuHHMD\n4AfgH6h+uDNQ+1txBtW7p/r6+koXliTDckFEZIJEUURBQYHeuw75+flyx9TKxsYGnp6euHn1Ko6X\nleFZHecFAlgGIBt1S8QTANYB8AbQScd7fwXg5+PDhzlNFMsFEZEMqqqqcPnyZZ0PSmZmZqKoqKjh\nC8nAyckJXl5e6Nq1a+1/d//e09MTSqUSCxYswNbPPsPHVVVaNykbBMAWgDOAh+86Hgjgc+geEilH\n9XbsU0NDJf26SDpc/puIyADKysr0DllkZ2fLPmShS9u2besUh3vLg7u7OxQKRYPX2bZtG6ZMmYIt\nqN7dVCr/BvA0qlcA7dmzp4RXJqmwXBARGUBkZCQ2b94sd4x6bGxs0KlTJ53FwcvLS5KhhsTERISH\nh6O0uBgdAaQC3FvEinBYhIjIALy8vGT5XEdHxwaHLOzs7AyaYfPmzZg2bVrtnZnLABYCiG7mdUVU\nP/h5XanEZ+vWNfNqZEgsF0RE90EURVy9elXnA5fnzp0zyOe2adNGZ3Ho2rUr2rVr16ghC0MQRREf\nfPABXnnllTrHNQC+APAAgKj7vTaApaguKNGrV3O7dRPHYREiIi0EQUBOTo7OZyaysrJQWlpae36L\nFi3q/CNfXl6OjRs3NukzFQpFg0MWrVpJMbggPY1Gg4ULF2LlypV6z5sO4CM0bYikENV3LKIBLFu2\nDK+//vp95yTjYLkgIqtUXFysd5pnbm4uNBpN7fnu7u467xZ07doVbdu2rXPH4Ny5c/Dz86vzmQ4O\nDnqHLDp37mzwIQtDKCsrQ2RkJLZt26bznGeeeQYDBgzASy+8ADdBwHJBwCRA6yySGuUA4gG8plTi\nulKJT1avxvTp0yVOT4bAckFEFkcURVy7dk3vNM/r16/Xnm9rawtPT0+d5aFLly5o2bJlkzKUlZVh\n9erV9YYsbGwsazPqmzdvYsKECTh48KDOc15//XUsXboUCoUCGRkZmDd7NvYmJcFDqUS4IKAvqvcK\ncUL1yptnUL2ORbxSiXxBQEhwMD5bt45DIWaE5YKIdBJFEbm5uTh37hzy8/PRvXt39O3bV+5YEAQB\nubm5eocsSkr+t/C0k5OT3ucUOnXqBKWSj6A1VW5uLkJDQ3Hq1CmtrysUCqxatQrPPfdcvddSUlKw\ndu1a7NuzB2fT03H3P0UKAH6+vhgRGoq5c+dyuqkZYrkgIq0qKyvxt7/9Dfv370dlZSU8PDxQWVmJ\nSZMm4bXXXoMoigZ7cLCkpKTBIYu7d+J0c3PTWRy8vLwavS4DNV5qaipGjRqF7Oxsra87ODhgy5Yt\nCA8Pb/BaRUVFOH/+PEpKShAUFISlS5fi5Zd1bdZO5oBVnYi0srGxwfnz57F+/XoMGjQIZWVl+OST\nT/D2229j6tSp6Nat231dVxRFXL9+XWdxyMzMxLVr1+rkuHvIIiAgoN6QBZeANq7k5GSMHTsWBQUF\nWl93dXXFd999h8BAXTuD1OXs7Fy7bbpKpcLFixelikoy4Z0LImoSGxsbHDp0CIMHD9b6uiAIuHTp\nkt4hi7t34nR0dNT7oGSnTp3M8iFHS7V9+3ao1WqUlZVpfd3T0xN79+7Fgw8+eF/XnzRpEgoKCrB/\n//7mxCSZ8c4FETVIo9HAxsYGO3fuROvWrdGhQwet512+fBldunSpM2Rx91LSwcHB9YYs5FyXgZpm\n3bp1mDdvXp1ZNHfz9/fH3r170aVLl/v+DJVKhU2bNt33+8k0sFwQUYNsbGxQXFyMxYsXY8aMGTqf\n2m/fvj0+/fTT2jsQUi0lTfISRRFvvfUWlixZovOcwMBAbN++HW3atGnWZ6lUKuTm5uL27dsmu6YH\nNYzlgsiKVFVVaR2yCA8Px9ChQ/XOmPj73/+OVq1aYeHChTqnU9rY2GD27NmGik8yEAQBc+bMwRdf\nfKHznIkTJ2LLli1wdHRs9uepVCoAQFpaGh577LFmX4/kwXJBZEFKS0uRnZ2t80HJnJycOjtx1iwl\nHRQUpHVoomZGyGeffYakpCRs2LABnp6eqKqqgq2trTG/NJJBSUkJpk6dip07d+o8Z968eVi5cqVk\n/3+oKRfnzp1juTBjLBdEZkIURRQUFOidZZGfn197/t1LSXt5eWHAgAH1Hpxs6LazQqHA4cOH8dln\nn+HNN9/EE088AQAsFlbg2rVrGDduHH7++Wed5yxduhSvv/66pM/MuLq6on379gbbm4WMg+WCyERU\nVVXhypUrOleUzMzMRFFRUe35dy8l3bt3b4wdO7ZOeejcuTPs7fUtrtyw0tJSzJo1C4IgQBAEPPfc\nczh79iwUCgXee+899O/fv7lfNpmgixcvYtSoUUhLS9P6uq2tLdavX49nn33WIJ+vUqlYLswcp6IS\nGUlZWVmDQxaVlZW157u6uupcFKpr167w8PAw+FLS5eXlcHJyQq9evaBUKtGjRw/4+PigT58+GDVq\nFFxcXAz6+WR8J06cQGhoKK5cuaL19RYtWmDbtm0YPXq0wTLMmjULx48fx3//+1+DfQYZFu9cWIia\nFe7Ky8vh4OAAX19fPqVvRKIo4tatW3rvOuTl5dWer1Ao0LFjx9qy0L9//3rloXXr1jJ+RdUcHBx0\nTjsky7N//36EhYXh9u3bWl93d3fHrl27DH7HSqVSYcuWLbVToMn8sFyYsZq1+ZN278a5Cxfqrs2v\nUEDVrRuCR4/GnDlz4O/vL2NS86fRaOoNWdz77MPdfyHb29vXloRevXph9OjR9YYsHBwcZPyKiOqK\njY1FZGRknbtnd/P29kZiYiK6d+9u8CwqlQolJSXIzc1t1poZJB8Oi5ghbbsK9gPgD6AFgBIAKQCO\ng7sKNlZ5ebneIYvs7Ow6f+m6uLjoHbJo3749f+Iis7FixQq89NJLOl9/5JFHsHv3bp2Lp0ntzz//\nRI8ePZCUlIQRI0YY5TNJWiwXZiY6OhovzJ8Pd0HAe4KASQD0PbJXASAOwGtKJa4rlfh41SrMmDHD\nOGFNyL1DFvfedbh3fLljx45al6KuOcZnDcgSaDQaLFq0CCtWrNB5TnBwMOLj4426oJUgCGjRogVW\nrFiB559/3mifS9LhsIgZWbZsGaKiojADwAoAjflWtwfwFIBxgoAXBQEzZ85EXl4e3njjDYNmNSaN\nRoO8vDy95aGwsLD2fDs7O3h5ecHLyws9e/ZESEhIneLQpUsXDlmQxauoqMAzzzyDmJgYnec8/fTT\n2LBhQ7NnHTWVUqmEr68vZ4yYMd65MBPR0dGYOXMmlgCIasZ1lgB48871pk+fLk04A6uoqKgzZHFv\nccjOzkZFRUXt+a1bt9Y7ZNGhQwcOWZBVKywsxMSJE/VuDrZo0SK8//77sn2vhIWFobi4GN9//70s\nn0/Nw3JhBjIyMtDb3x8RZWVY38xriQBmAYhxdMSplBSTeAajsLCwwSGLu/9v2qFDB53FoWvXrnB1\ndZXxqyEybVeuXEFoaChOnDih85yPPvoIL7zwghFT1ffqq68iJiYGmZmZsuag+8NyYQZCR45E6g8/\n4JQgNGoopCGFAHorlfAfOhR7DPxTgUajQX5+vt7ycOvWrdrz7ezs0KVLF53loUuXLpLsX0BkjdLS\n0jBq1ChcvHhR6+v29vb46quvMHXqVOMG0+LLL7/EtGnTUFxcjBYtWsgdh5qI5cLEpaSkoFevXtiC\n6mcnpPJvAE/fuX7Pnj3v+zoVFRXIycnRO2RRXl5ee76zs3O9hyTvHbLg0tJE0jt27BjGjBmD69ev\na329devWSEhIwNChQ42cTLvk5GQMHjwYJ06cwMMPPyx3HGoiPtBp4tauXQsPpRKT7tps6l5FqH4O\nYzuAywBcADwM4J8A+uh4TziAhUol1qxZg5UrV+q89u3bt/Xedbh8+XKdIYv27dvXFoU+ffpoHbKQ\nch8CImrYzp07MWXKFJSWlmp9vWPHjtizZ49J/SN+9wZmppSLGoflwsQl7d6NcEHQO910NoD/AJgP\noCeA6wAOA0iF7nLhACBcEJC4cyd++b//01ocsrKyUFBQUPsepVJZO2TRvXt3jBgxot6QhZOTkyRf\nNxFJY8OGDZg1axaqqqq0vq5SqZCYmIiuXbsaOZl+bm5ucHd354wRM8VhERN2+/ZtuLi44AtRhL7t\ngdoA+AsA3fcftNsA4O75Ii1bttQ5XNG1a1d07NiRQxZEZkIURSxbtgyLFy/Wec6AAQOwc+dOuLm5\nGTFZ4wUEBKBr167YsmWL3FGoiXjnwoSlp6dDFEU0tHC3K4BjqB4S6diE6/e682tMTAxGjhyJNm3a\ncMiCyAJUVVXh+eefx9q1a3WeM27cOMTGxpr0w5IqlQonT56UOwbdB072N2E1D0I29K3/TwCnAXQB\n8DiAdwBkNOL6NQMY3t7eaNu2LYsFkQUoLS3FpEmT9BaLmTNn4j//+Y9JFwvgf1uv8wa7+WG5MGE1\nq0SWNHDeZAAXAKwG4AngQ1TflUhs4H01j3ZxNUoiy3Djxg0EBwcjISFB5zlvv/021q1bB6XS9G9c\nq1QqFBUV4fLly3JHoSZiuTBhvr6+UCgUSGnEue0BzEH1g50ZANwALGvgPWdQvXuqr69v84ISkeyy\nsrIQEBCAI0eOaH3dxsYG69atw1tvvWU2dynvnjFC5oXlwoQ5OztD1a0bjus5R4PqRbHu5g6gE4Dy\n+qfX8SsAPx8fODs7NyMlEcnt1KlTGDRoEFJTU7W+7ujoiG+//RazZs0ycrLm6datG2xtbVkuzBDL\nhYkLHj0a8UolKnS8fhvVQyHPAvgYQDSAqaguDvoW3SpH9XbsI0JDpYxLREZ28OBBBAYGIjc3V+vr\nbdu2xf79+/Hkk08aOVnz2dvbo1u3biwXZojlwsTNmTMH+YKAOB2vtwDwHICTAN4G8CKAPwGsAfA3\nPdeNB5AvCJg7d66EaYnImLZt24aRI0fWWUL/bl5eXjhy5AgGDRpk5GTS8fPzw9mzZ+WOQU3EcmHi\n/P39ERIcjNeVStzW8rodgPcB/A7gJqqHSH5H9eZkuhQCeE2pREhwcLOW/iYi+axatQpTp06tsyPw\n3R566CEcPXoUfn5+Rk4mrZoZI2ReWC7MwGfr1uGaUokXJbiWCOAlANeVSny2bp0EVyQiYxJFEa+9\n9hoWLFigc4pmUFAQfvrpJ3Tq1MnI6aSnUqlw8eJFlJWVyR2FmoDlwgx4e3vj41WrEA1gaTOuI955\nfzSAT1avNont1omo8SorK/HMM8/g/fff13nOlClTsHfvXri4uBgxmeGoVCqIoojz58/LHYWagOXC\nTMyYMQNLly7FYgAzAa1DJPoUonqo5E0Ay5Ytw/Tp0xt4BxGZkqKiIowbNw5fffWVznNeeOEFxMTE\nWNTaNZyOap5YLszIG2+8gfXr1yPG0REPKpX4N6BzFkmNclRvr95bqUSMoyOio6Px+uuvGz4sEUkm\nLy8PQUFBSEzUvTTeBx98gBUrVsDGxrL+Wm/Xrh1cXV1ZLswMNy4zQxkZGZg3ezb2JiXBQ6lEuCCg\nL6pX5XRC9cqbZ1A9HTXOxgZXNRqEBAfjs3XrOBRCZGbS09MxatQopKena31dqVTiyy+/xP/93/8Z\nOZnxDBgwACqVCps2bZI7CjUSy4UZS0lJwdq1a7Fvzx6cvbPJWQ2FQoFWjo5o7eaG77//nrNCiMzQ\nr7/+itGjR+Pq1ataX3d2dkZ8fDxGjhxp5GTG9cwzz+Ds2bP4+eef5Y5CjWT6i8uTTv7+/li5snqj\n9aKiIpw/fx7l5eVwcHCAr68vYmNjMXv2bLRp00bmpETUVImJiQgPD0dxcbHW1z08PLBnzx48+uij\nRk5mfCqVCgkJCRBF0WyWLrd2ljU4Z8WcnZ3Rp08fPP744+jTpw+cnZ0xceJE2NjYIC5O1xJcRGSK\nvvrqK4wdO1ZnsfD19cXRo0etolgA1eXi1q1byM/PlzsKNRLLhQVr27YtRo0ahZiYGLmjEFEjbdq0\nCX/9618hCILW1/v164fk5GR069bNyMnkwxkj5oflwsJFREQgOTkZmZmZckchokYICQnRWRxCQ0Nx\n4MABtGvXzsip5OXr6wsbGxuWCzPCcmHhnnzySTg6OmLr1q1yRyGiRmjXrh0CAgLqHX/mmWewfft2\nq9zF2MHBAQ888ADLhRlhubBwrVq1wrhx4xAbGyt3FCJqQHl5OSIiIrB582a8/PLLaNGiBYDqNW42\nbNgAOzs7mRPKh3uMmBfOFrECarUa4eHhOHfuXO3YJRGZllu3bmHChAk4evQo4uPjERYWhqFDh+LC\nhQuYN2+e3PFk5+fnh507d8odgxqJdy6sQGhoKFq1asW7F0Qm6tKlS3jiiSdw4sQJ7Nu3D2FhYQCq\nn79gsaimUqlw4cIFnbvAkmlhubACTk5OCAsLQ2xsrM5dFIlIHqmpqRg4cCBu3LiBw4cPa33egqrL\nRVVVlc6VSsm0sFxYCbVajbNnz+LkyZNyRyGiO5KTkxEQEIDWrVvj6NGj6NWrl9yRTBano5oXlgsr\nMWLECLi5uXFohMhEfPfddxg+fDgefPBBHDp0CJ07d5Y7kknr0KEDWrVqxXJhJlgurISdnR0mTZrE\noREiE/D5558jLCwMY8aMQWJiIlxdXeWOZPIUCgVnjJgRlgsrolarkZmZyc1/iGQiiiLefvttzJ49\nG3PnzsXWrVvh6OgodyyzwXJhPlgurEhgYCA6derEoREiGQiCgNmzZ+Odd97Be++9h1WrVsHW1lbu\nWGaF5cJ8sFxYEVtbW0yZMgXffPMNqqqq5I5DZDVKSkowceJEbNiwARs3bsRrr73G3T3vg5+fH65f\nv45r167JHYUawHJhZSIiInDlyhUcPHhQ7ihEVuHatWsYPnw4Dhw4gJ07d+Kvf/2r3JHMFmeMmA+W\nCyvTr18/eHt7c2iEyAguXryIgIAApKen44cffkBISIjckcxa9+7doVAoWC7MAMuFlVEoFFCr1YiL\ni+NKd0QGdPLkSQwaNAiVlZVITk5Gv3795I5k9pycnODl5cVyYQZYLqxQREQECgoKkJSUJHcUIot0\n4MABPPHEE+jYsSOSk5Ph6+srdySLwYc6zQPLhRV68MEH4e/vj5iYGLmjEFmc2NhYhISEYMCAAfjx\nxx/Rvn17uSNZFJYL88ByYYUUCgUiIiKwfft2lJSUyB2HyGJ8/PHHiIiIgFqtxo4dO9CqVSu5I1kc\nlUqF9PR0CIIgdxTSg+XCSk2dOhVFRUXYvXu33FGIzJ5Go8GiRYuwcOFCvPLKK9i0aRPs7e3ljmWR\n/Pz8UFlZiYyMDLmjkB4sF1aqe/fueOyxxzg0QtRMFRUViIyMxL/+9S988skneP/997mGhQFxOqp5\nYLmwYhEREdi1axcKCwvljkJklm7fvo0xY8Zg27ZtiI2NxYIFC+SOZPE8PT3RsmVLnD17Vu4opAfL\nhRWbMmUKysvLkZCQIHcUIrNz5coVDBkyBL/88gsSExMxZcoUuSNZBYVCgR49evDOhYljubBiXbp0\nQWBgIBfUImqitLQ0DBo0CHl5eTh06BCCgoLkjmRVOGPE9LFcWDm1Wo2kpCSu1U/USL/88gsGDx4M\nBwcHHD16FA899JDckawOy4XpY7mwcpMmTYIoioiPj5c7CpHJ2717N4YOHYoePXrg8OHD8PLykjuS\nVVKpVMjPz8fNmzfljkI6sFxYOQ8PDwwfPpxDI0QN+PLLL/Hkk08iODgY+/btg5ubm9yRrJafnx8A\nzhgxZSwXBLVajYMHDyI3N1fuKEQmRxRFLFu2DNOmTcOMGTMQFxcHJycnuWNZtR49egBguTBlLBeE\nsLAw2NnZYdu2bXJHITIpVVVVeP755xEVFYV3330Xa9asgVKplDuW1WvZsiU6d+7McmHCWC4Irq6u\nCA0N5dAI0V1KS0sxZcoUrF27FuvXr8fixYu5OJYJUalUXOvChLFcEIDqoZFjx47hwoULckchkl1B\nQQFGjhyJPXv2ICEhATNmzJA7Et2DM0ZMG8sFAQDGjRuHFi1aYOvWrXJHIZJVdnY2AgICkJqaigMH\nDmDcuHFyRyIt/Pz8UFVVhaqqKrmjkBYKURRFuUOQaYiIiMCZM2fwxx9/yB2FSBanT59GSEgIlEol\nEhMTa/exINOj0WhgY8Ofj00V/2SoVkREBE6dOoUzZ87IHYXI6H766ScEBgbC3d0dR48eZbEwcSwW\npo1/OlRr1KhRcHFx4dAIWZ34+HiMHDkSjz76KA4ePIiOHTvKHYnIrLFcUC0HBwdMnDgRMTEx4GgZ\nWYvVq1dj8uTJCAsLw+7du+Hi4iJ3JCKzx3JBdUREROD8+fP4/fff5Y5CZFCiKOKNN97A/PnzsXDh\nQmzZsgUODg5yxyKyCCwXVMfQoUPh4eGBmJgYuaMQGUxlZSWmTZuG9957Dx9++CH+9a9/cQzfwhQU\nFCAzM1PuGFaL301Uh1KpxOTJk7F161ZoNBq54xBJrqioCOPHj8eWLVvw9ddf46WXXpI7Et2H8vJy\nvbs5//jjj/jb3/6G8vJyI6aiGiwXVI9arUZOTg6Sk5PljkIkqfz8fAwdOhSHDh3C7t278fTTT8sd\nie5TZGQkli9fjoqKitpj586dQ3FxMQDgsccew++//47U1FS5Ilo1lguqZ9CgQejcuTOHRsiipKen\nY/DgwcjOzsZPP/2EESNGyB2JmiE7Oxt+fn6wt7evPTZlyhTs2rULAODl5QVPT08+PyYTlguqx8bG\nBmq1Gtu2bYMgCHLHIWq23377DYMGDYJCocDRo0fxyCOPyB2Jmql9+/b4888/AaD27yk3Nzf8+uuv\ntee4uLjgypUrsuSzdiwXpJVarcbVq1dx4MABuaMQNcv333+PoKAgPPDAAzhy5Ai8vb3ljkQSCAwM\nxMmTJ1FQUAClUokbN26goqIChw4dwldffYV33nkHmZmZCAwMlDuqVWK5IK0effRRdO/enTulkln7\n+uuvMWbMGDzxxBM4cOAA2rVrJ3ckksioUaMAAGFhYfj888/xl7/8BRUVFXjllVfw/PPP4+uvv8ZT\nTz2FwYMHy5zUOnFvEdLpzTffxMqVK5GXl8f5/2RWRFHEBx98gFdeeQXTpk3DunXroFQq5Y5FEjt6\n9ChefvlllJWVoXPnznj33XfRu3dvFBYWIjs7G7169ZI7otViuSCdUlJS0KtXLyQkJGD8+PFyxyFq\nFI1GgxdffBGffPIJoqKi8O6770KhUMgdiwzk9u3bSEtLQ4cOHeDp6Sl3HLqD5YL0evjhh+Hv78+Z\nI2QWysvguE1xAAAgAElEQVTLERkZiW3btuHTTz/F3Llz5Y5EZJX4zAXppVar8d1339XOHScyVbdu\n3UJISAi2b9+O+Ph4FgsiGbFckF5qtRolJSXYsWOH3FGIdMrNzUVgYCBOnDiBffv2ISwsTO5IRFaN\nwyLUoAEDBqBDhw5ISEiQOwpRPampqQgJCYEoiti7dy/8/f3ljkRk9XjnghqkVquxZ88e3Lx5U+4o\nZIUa+vln586daN26NZKTk1ksrFRcXBzvVpkYlgtq0JQpU1BZWYlvv/1W7ihkhRqa6bFo0SIcO3YM\nnTt3NlIiMjXFxcVISEjgs2EmhOWCGtSpUycMGTKEM0bIqMaOHYuoqKhGnduiRQsDpyFTplKpAABp\naWkyJ6EaLBfUKBEREdi/fz/y8/PljkIWThRF9O/fH1lZWVi4cKHcccgM1JSLc+fOyZyEarBcUKNM\nnDgRNjY2iIuLkzsKWbCbN2/Cx8cH7dq1w6+//go3NzeUlJSgpKRE7mhkwtq0aYN27dqxXJgQlgtq\nFHd3dwQHB3NohAxGEAQsWrQIFy9exKZNm2Bvb49//OMfmDRpEnr37o1nn30WBw8elDsmmSiVSsVy\nYUK42D41WkREBCIjI5GdnY0uXbrIHYcsjFKpxLRp05CVlYVnn30WLi4uOHnyJCZOnIhhw4Zh06ZN\nyM7ORnl5OUaOHCl3XDIxfn5++P333+WOQXfwzgU12vjx4+Ho6IitW7fKHYUs1MCBA7Fo0SLk5OTg\njz/+wJYtW/DOO+/g73//O7799lvk5uZi165dcsckE6RSqZCWltbg1GUyDi6iRU0yadIkXLx4Eb/+\n+qvcUciC7dq1C5WVlRgzZgzs7Oyg0WhgY2ODhQsXYteuXTh58iScnJzkjkkmZMeOHXjyySeRk5PD\nDcxMAO9cUJOo1Wr89ttv+PPPP+WOQhZs9OjRGD16NOzs7AD8b62LW7duYdSoUSwWVE/NjJGzZ8/K\nnIQAlgtqojFjxsDZ2RmxsbFyRyELplAoYG9vX+f333zzDb7//nsEBQXJF4xMlre3N5RKJR/qNBEs\nF9QkTk5OmDBhAmJiYji2SUYRHx+PBQsWYPr06ViyZAnCw8PljkQmyM7ODj4+PiwXJoLlgppMrVYj\nNTUVp06dkjsKWQiNRoOUlBQIglDvtYCAAGRmZmLnzp149tlnZUhH5oLTUU0HywU1WXBwMNq2bcuh\nEZJERUUF/vKXv6Bfv364fv16vdfbt2+PuLg4DBkyRIZ0ZE78/PxYLkwEywU1mb29PcLDwxEbG8uh\nEWqWwsJCjBkzBnFxcdi4cSPat2+v9byaBzuJ9FGpVMjMzERpaancUaweywXdF7VajYyMDPzyyy9y\nRyEzdeXKFQQFBeGXX35BYmIiJk+eLHckMnMqlQqiKOL8+fNyR7F6LBd0X4YMGYJPP/0Ufn5+ckch\nM5SWloZBgwYhLy8Phw4d4gwQkgQ3MDMdLBd0X2xtbTF79my4uLjIHYXMzLFjxzB48GA4Ojri6NGj\neOihh+SORBbC3d0dbdu25VoXJoDlgu6bra2t3BHIzOzatQvDhg1Djx49cPjwYXh5eckdiSwMZ4yY\nBpYLIjKKL7/8EuPHj0dwcDD27duHtm3byh2JLBDLhWlguSCDKi8vx61bt+SOQTISRRFLly7FtGnT\nMGPGDMTFxXH5bjKYmumonMkmL5YLMpgbN27g008/xTvvvCN3FJJJVVUVnnvuOSxevBjvvvsu1qxZ\nA6VSKXcssmAqlQqFhYXIy8uTO4pVY7kgg2nbti369++PLVu2IDMzU+44ZGSlpaWYPHkyPv/8c6xf\nvx6LFy+u3YCMyFA4Y8Q0sFxQs6SmpmLdunV1bkHu378faWlpAKqXbn7kkUcQHR0tV0SSwY0bNxAc\nHIy9e/ciISEBM2bMkDsSWQkfHx/Y2tqyXMiM9yepWZYvX4527drV+Yn0iy++QHFxMbZv3w6gek2M\npKQkuSKSkWVnZyMkJAR5eXk4cOAABgwYIHcksiL29vbw9vbmdFSZ8c4FNUufPn2QnJwMALWbTk2Y\nMAHff/89Lly4AI1Gg/3792PAgAHQaDRyRiUjOH36NAYOHIji4mIcOXKExYJkwRkj8mO5oGaJjIxE\namoq/vjjj9oH9QoKCvDQQw/h6aefRsuWLXHmzBmEhobCxob/d7NkBw8eREBAANzd3XH06NHasW8i\nY2O5kB+HRahZ3N3dERISgrfeegtjx46Fo6Mjli5dihdeeAEjR45EamoqHnjgAfTv31/uqGRA8fHx\nePrppxEQEID//Oc/aN26tdyRyIqpVCpkZGSgvLwcDg4OcsexSgqRk4GpmTIyMvCvf/0LX331FXx8\nfNC3b1+sXr2a39RWYvXq1ViwYAHUajU2btwIe3t7uSORlfvpp58wZMgQnDlzBv7+/nLHsUosFyQJ\nQRBw4cIFZGdn4+GHH4a7u7vckcjARFHEG2+8geXLl+PFF1/EBx98wKEvMgl5eXno0KED/vOf/yAs\nLEzuOFaJwyIkCaVSiR49eqBHjx5yRyEjqKysxMyZM7Fp0yZ8+OGHeOmll+SORFTLw8MDLi4ufO5C\nRiwXRNQkRUVFmDx5Mvbv348tW7bgqaeekjsSUR0KhYIPdcqM5YIMQhRFrsZogfLz8zFmzBicPXsW\nu3fvxogRI+SORKSVSqXiWhcy4gApSUoURVRVVSErK0vuKCSx9PR0DB48GNnZ2fjpp59YLMik1dy5\n4GOF8mC5IEkpFAr89a9/RUREhNxRSEK//fYbBg0aBIVCgaNHj+KRRx6ROxKRXiqVCgUFBbh27Zrc\nUawSywVJbvTo0Th69CguXrwodxSSQGJiIoYMGQJvb28kJyfD29tb7khEDfLz8wPADczkwnJBknvy\nySfh5OSErVu3yh2Fmmnz5s0YO3YsgoKCsH//fk4xJrPh6+sLhUJROzRSWloqdySrwnJBknN2dsa4\nceMQExMjdxS6T6Io4p///CciIyMRGRmJhIQEtGzZUu5YRI2yfft2fPjhh2jRogWioqLg6urKnXmN\njItokUEkJCQgLCwMKSkp6Nmzp9xxqAk0Gg0WLlyIlStXIioqCu+++y5n/pBZ6d27N06fPl3n2KOP\nPorffvtNpkTWh3cuyCBCQkLQunVrDo2YmbKyMqjVaqxevRpr1qzBkiVLWCzI7GjbNC8tLY0zR4yI\n5YIMwtHREWFhYYiJieE3tJm4efMmQkJCsGPHDsTHx2POnDlyRyK6L9rKRVFRES5duiRDGuvEckEG\nExERgbS0NJw4cULuKNSA3NxcPPHEEzh58iSSkpIwYcIEuSMR3Tdt5QLgzBFjYrkggxk2bBjc3d35\nYKeJS01NxaBBg3Dz5k0cOXIEAQEBckciapaaaaj3YrkwHpYLMhg7OztMnjwZW7duhUajkTsOaZGc\nnIzBgwejdevWSE5O5vbUZBF450J+LBdkUGq1GllZWfj555/ljkL32L59O4YPH47evXvj0KFD6Ny5\ns9yRiCTh4uKC9u3b1zvOcmE8LBdkUAEBAfD09OTQiIlZt24dJk6ciLFjxyIxMRGurq5yRyKSlLa7\nF9zIzHhYLsigbGxsMHXqVHzzzTcQBEHuOFZPFEW89dZbmDNnDubNm4fY2Fg4OjrKHYtIctrKRWZm\nJlfqNBKWCzI4tVqN/Px8/Pjjj3JHsWqCIGDWrFl49913sXz5cqxcuRK2trZyxyIyCG3lQhRFnD9/\nXoY01oflggyub9++8PHxQWxsrNxRrFZJSQnCwsKwceNGbNq0Ca+++ioXxyKLxoc65cVyQQanUCig\nVqsRHx+PiooKueNYnWvXrmH48OH44YcfsGPHDkRGRsodicjgOB1VXiwXZBRqtRo3b95EYmKi3FGs\nysWLFzF48GCkp6fjxx9/REhIiNyRiIzigQcegJ2dXb3jLBfGwXJBRvHggw/iwQcf5NCIEZ04cQID\nBw5EVVUVkpOT0bdvX7kjERmNUqmEr69vveMsF8bBckFGo1arsX37dpSUlMgdxeIdOHAATzzxBDw9\nPXHkyBGtf8kSWTptz12cO3eO+x0ZAcsFGY1arUZxcTF27twpdxSLFhsbi5CQEAwaNAg//vij1sWE\niKyBtnJx69Yt5OXlyZDGurBckNH4+PigX79+HBoxoI8++ggRERGIiIjAjh074OzsLHckItlwxoh8\nWC7IqNRqNXbv3o1bt27JHcWiaDQa/P3vf8eLL76IV199FRs3btT6MBuRNWG5kA/LBRnV1KlTUVFR\ngYSEBLmjWIyKigr85S9/wYoVK7By5UosX76ca1gQgeVCTiwXZFSenp4IDAzkXiMSKSwsxJgxYxAX\nF4etW7di/vz5ckciMhlubm5wd3evd5zlwvBYLsjoIiIisG/fPly9elXuKGbtypUrGDJkCI4fP47E\nxERMnjxZ7khEJkfXjBEyLJYLMrrw8HAAQHx8vMxJzFdaWhoGDhyI/Px8HDp0CEFBQXJHIjJJ2spF\nRkYGVws2MJYLMrp27dphxIgRHBq5T8eOHcPgwYPh5OSEo0ePonfv3nJHIjJZ2spFVVUV0tPTZUhj\nPVguSBYRERE4dOgQcnJy5I5iVnbt2oVhw4ahR48eOHz4MLy8vOSORGTSdD3UefbsWSMnsS4sFySL\nCRMmwN7eHt98843cUczGhg0bMH78eIwcORL79u1D27Zt5Y5EZPK4gZk8WC5IFi4uLhg9ejQX1GoE\nURSxdOlSTJ8+HTNnzkRcXBycnJzkjkVkFrp16walUlnvOMuFYbFckGzUajWOHz/OsU89qqqq8Nxz\nz2Hx4sVYsmQJPvvsM9ja2sodi8hs2NnZoVu3bvWOs1wYFssFyWbs2LFo2bIl717oUFpaismTJ+Pz\nzz/H+vXrERUVxcWxiO4Dp6MaH8sFyaZFixYYP348y4UWN27cQHBwMPbu3YuEhATMmDFD7khEZktb\nubhx4wauXbsmQxrrwHJBslKr1Th9+jROnz4tdxSTkZWVhYCAAJw9exYHDhzA2LFj5Y5EZNa4DLjx\nsVyQrEaNGgVXV1fevbjj9OnTGDRoEEpLS3HkyBEMGDBA7khEZo/TUY2P5YJkZW9vj/DwcMTExODg\nwYOYN28e8vPz5Y4li4MHDyIgIADt2rVDcnKyzr8QiahpOB3V+FguSDaiKOL48eO4efMmLly4gKCg\nIKxZs8YqlwWPi4vDyJEj0bdvXxw8eBAdO3aUOxKRxXB3d0ebNm3qHWe5MByWC5JNdnY2+vfvX69M\nWNuy4KtXr8aUKVMQHh6O3bt3o3Xr1nJHIrIoCoVC653AEydO4MSJEygqKpIhlWVjuSDZeHl5aX2m\nwFqWBRdFEa+//jrmz5+PF198EV9//TXs7e3ljkVkkdq3bw8AsLvrWFZWFh555BG0bt0aPX19sWDB\nAqSkpMgT0MKwXJCsIiIitB639GXBKysr8eyzz2L58uX48MMP8eGHH8LGht+ORFLLyMhA6MiR2L59\nO9oCmAFgA4CfAfxx59cvRBFD09Oxdc0a9OrVC6EjRyIjI0PO2GZPIYqiKHcIsl6XL19G586dodFo\n6hzv27cvjh8/LlMqwyoqKsLkyZOxf/9+bNy4EU899ZTckYgsUnR0NF6YPx/ugoD3BAGTAOi7N1gB\nIA7Aa0olriuV+HjVKq4xc5/4oxLJqmPHjggKCqp3/Ndff8X58+eNH8jA8vPzMXToUBw5cgR79uxh\nsSAykGXLlmHmzJmIKCvDKUHAU9BfLHDn9acAnBYERJSVYebMmVi2bJnhw1oglguSnVqt1nrc0ta+\nSE9Px6BBg5CTk4OffvoJw4cPlzsSkUWKjo5GVFQUlgBYD6DVPa8fBfAOgEId7291533vAoiKisIX\nX3xhsKyWisMiJLvr16+jQ4cOEAShzvFevXpZzMqdv/32G0aPHg1XV1fs3bsX3t7eckciskgZGRno\n7e+PiLIyrNdxzr8AvAwgA4CXnmuJAGYBiHF0xKmUFH7fNgHvXJDs3NzcMGrUqHrHz5w5g1OnTsmQ\nSFqJiYkYMmQIvL29ceTIEf4FRWRA82bPhrsgYIWecxr7E7UC1UXETRAwb/bs5oezIiwXZBIsdWhk\n8+bNGDt2LIKCgrB//364u7vLHYnIYqWkpGBvUhLeE4R6QyE13kH1XQsAeADV/wjaAsjScX5rAMsF\nAXuTkpCamippXkvGckEmYfz48XB0dKx3PDY2FuY4cieKIv7xj38gMjISkZGRSEhIQMuWLeWORWTR\n1q5dCw+lEpP0nBMOoGYC/CcAvgawGUC7Bt7joVRizZo10gS1AiwXZBJatWqldffPCxcumN2UVI1G\ngxdeeAGvvvoqFi9ejOjoaCiVSrljEVm8pN27ES4IemeFPAjg0Tv/ezyqZ4c8BcBJz3scAIQLAvbt\n2SNNUCvAv/HIZKjVasTFxdU7Hhsbi/79+8uQqOnKysoQGRmJ+Ph4rFmzBnPmzJE7EpHF0Gg0yMvL\nQ1ZWVr3/MjIycDY9vXbIQ2p9AaxNT0dRURGcnZ0N9CmWg7NFyGSUlpaiffv2uH37dp3jnTp1QlZW\nFmxtbWVK1jg3b97EhAkTcOzYMcTExGDChAlyRyIyK0VFRVqLQ1ZWFrKzs5GdnY3Kykq91/gZwOMN\nfE5jZ4vc7RiAAQD++9//ok+fPo18l/XinQsyGU5OTpgwYQI2b95c5/ilS5dw+PBhDBkyRKZkDcvN\nzUVoaChycnKwb98+DB48WO5IRCalqqoKly9f1lkesrKyUFBQ0OzPaSFBVm1qhk3Ky8sN9AmWheWC\nTIpara5XLoDqoRFTLRepqam1U2kPHz4Mf39/mRMRGV9hYaHe4pCTk4OqqiqD5yhpxDmK+7hu6Z1f\nHRwc7uPd1ofDImRSKisr0aFDB9y4caPOcTc3N1y+fBl2dnY63imPI0eOYNy4cejcuTP27NkDT09P\nuSMRSU4QBFy6dElvebh165bcMQFUb0r2bAPnrAMwD8B/ATzUhOvOUChQWFjIZy4agXcuyKTY2dlh\n0qRJ+Pzzz+scv379Ovbv34+QkBCZktW3fft2qNVqPP7440hISICrq6vckYiaTBRF3Lx5U+dzDllZ\nWcjNza23uaApad++Pby8vPBnSgqOFxc3WC4eQ/VCWq8DUKN6G/YnoX/GyK8A/Hx8WCwaieWCTE5E\nRES9cgEAMTExJlMu1q1bh3nz5mHixInYvHmz1jU6iEzN1q1bcf78+XoloqioSO5oOjk5OcHLy0vn\nf507d679/luwYAG2rlmDjxuYjtoXwFIAawEkAtBA/8Od5QDilUpMDQ2V7guzcBwWIZNTVVWFLl26\n4PLly3WOt2rVCvn5+bL+Qy6KIt566y0sWbIE8+fPx0cffWTys1iIaqhUKqSlpckdo46OHTvqLQ9u\nbm5QKBr3lERKSgp69eqFLaheu0Iq/wbw9J3r9+zZU8IrWy7euSCTY2triylTpuCTTz6pc/z27dvY\nvXs3Jk6cKEsuQRAwZ84cfPHFF3j//ffx8ssvN/ovPSI5lZaWIjs72+i39Fu0aIGuXbvqLA6enp6S\nPiDp7++PkOBgvP7DDxinZwnwpigE8JpSiZChQ1ksmoB3LsgkHTt2DAMGDKh3fPLkyfjmm2+Mnqek\npARTp07F3r178cUXXyAyMtLoGYi00Wg0yM/P1/uw5dWrVyX/XIVCgU6dOum969CmTRujF/DG7Ira\nWNwV9f6xXJBJEkURPj4+yMjIqHPcyckJeXl5aNVKip9JGufatWsYN24cTp06hbi4OJN57oOsQ3Fx\nce2DlboeuqyoqKg9X9/dgm+//RYrV65s1Oc6Ozs3eNfB1GZv1YiOjsbMmTOxBEDUfV5DRPVzGW/e\nud706dMly2cNOCxCJkmhUECtVmP58uV1jpeWluK7777D008/bZQcFy9exKhRo1BQUIAff/wRffv2\nNcrn0v0TRRGXLl1CWloarl69im7dupnsn5tGo8GVK1f03nW4fv167fn33i3o27dvk+4WXLhwAQBg\nY2MDT09PvXcdXFxczHbYb8aMGcjLy0NUVBQyAawAmjREUgjgJQDRAJYtW8ZicR9454JM1h9//IGH\nH3643vGxY8dix44dBv/8EydOIDQ0FC1btsTevXvh6+tr8M+k5hEEAQsXLkRSUhLKy8vh4eGByspK\nhIeH44033oAoikb9B/P27dt67zrk5OTUWc7a0HcLbt68icLCQnTq1MkqNtOLjo7GC/Pnw00QsFwQ\nMAnQO4ukHEA8qp+xuK5U4pPVq1ks7hPLBZksURTRq1cvpKam1jluZ2eHK1euoG3btgb77P379yMs\nLAwqlQq7du2Ch4eHwT6LpKPRaBASEoLXXnsNAQEBqKiowKpVq7B48WKkpKSge/fukn2WIAh6l7PO\nzs6us5y1ra1t7d2CLl26WNzdAlOVkZGBebNnY29SEjyUSoQLAvoC6IXqdS1KAZxB9ToW8Uol8gUB\nIcHB+GzdOj5j0QwsF2TSlixZgjfffLPe8fXr12PGjBkG+czY2FhERkZi2LBhiIuL46I5FsDW1hb7\n9u3D0KFDG/2eW7du6R2uyM3NrbOctaurq95hho4dO1rF3QJTlZKSgrVr12Lfnj04m56Ou//pUygU\n8PPxwYjQUMydO5ezQiTAckEm7c8//0SPHj3qHR8+fDj27dsn+eetWLECL730EiIjIxEdHW2yD6xR\nwzQaDWxsbJCYmIipU6fi559/hp+fn9ZzP/jgA1y4cKFOeSgsLKx9XalUonPnzjqLQ5cuXdC6dWtj\nfWnUTEVFRTh//jzKy8vh4OAAX19f/hAhMZYLMnl9+/bFb7/9VueYjY0NcnNz0aFDB0k+Q6PRYNGi\nRVixYgVeffVVvPfee7w9bQHKysoQGBiIgQMH6l3wrF+/fhAEQWd56NChAxdLI2oC3qMjk6dWq+uV\nC41Gg23btmH+/PnNvn5FRQWeeeYZxMbGYtWqVXj++eebfU0ynIqKCuTk5EAURXh7e8PGxkbnuYsW\nLYK9vT0WLVqktxwcP37cEFGJrBbvXJDJy8rKQteuXesdHzhwIJKTk5t17cLCQkycOBGHDh3Cli1b\nMGnSpGZdj5pHFEVcv35d77MOV65cgSiKmDp1KmJjY7VeQ6FQ4PPPP8c//vEPrF+/HsOGDUNVVRXv\nPhAZCcsFmYXAwEAcPny43vGMjAw88MAD93XNK1euIDQ0FBkZGUhISEBQUFDzQlKDysrKkJOTo7c8\nlJaW1p7v4OCgc6iiR48e8PLSvtVUcnIyZs2ahRdffBHTpk0z1pdHRHdwWITMglqt1louNm/ejHHj\nxjX5way0tDSMGjUKFRUVOHToEHr37m2I2FZFFEVcvXpVb3HIy8ur856arbK9vLwwevToegWiXbt2\nTX72paysDDNnzkRlZSVsbGywYMECnDt3DqIoYsmSJXj88cel/LKJSAveuSCzkJ+fj44dO0Kj0dQe\nswNQec95CoUCqm7dEDx6NObMmQN/f/961zp27BjGjBkDDw8P7N27V+dPv1RXSUlJvQWh7v19eXl5\n7flN2SpbSuXl5XByckLPnj2hVCrh6+sLHx8fPPzwwxg9ejTatGkj+WcSUV0sF2Q2AgMDkXz4MDQA\n2gKYCqAfAH8ALQCUAEgBcBy6F8PZtWsXJk+ejEcffRTfffedQRfiMicajQZ5eXl67zpcu3at9nyF\nQqF3q+wuXbo0aatsIrIsLBdkFqKjozF/3jy4VVbin0CDy/hWAIjD/5bx/XjVKtjY2GDWrFkYN24c\n/v3vf8PJycko2U1BUVFRg5tf3b0MdcuWLRtchtreXt+fABFZM5YLMnnLli1DVFQUpgP4CE3bgOg2\ngIUAvrjz+zlz5mD16tUWNWugqqqqwc2vbty4UXu+jY1Ng1tlu7q68q4DEd03PtBJJi06OhpRUVH3\nvXVyK1TvbNgV1VsnP/bYY2ZXLAoLCxvc/EoQhNrzW7VqVXvXYcCAAZgyZUqd4tCpUyeuPEpEBsU7\nF2SyMjIy0NvfHxFlZVjfzGuJAGYBiHF0xKmUFJPZkEgQBFy6dEnvXYdbt27Vnm9ra1tvGep7N8Fy\ncXGR8SsiImK5IBMWOnIkUn/4AacEoUlDIboUAuitVMJ/6FDs+f57Ca6onyiKjdr86u4ZMG3atGlw\n8ytzu/NCRNaH5YJMUkpKCnr16oUtAJ6S8Lr/BvD0nes3d+fDyspK5Obm6i0Pt2/frj1fqVTq3Gq7\n5g5Eq1ZS1CgiInmxXJBJWrBgAbauWYNsQag3KyQewGQABwEE3vPaOgBzAZxG9RTVe5UD8FIqMXXu\nXKxcuVLn54uiiIKCAr3F4dKlS3W2bXZzc9N716F9+/a860BEVoHlgkxST19fDE1Px2daXisD4AHg\nrwBW3fPacABXAfyh59rzAPzg44OdiYk6p2VmZWWhuLi49j329vY6n3GoOdayZcvmfdFERBaC5YJM\nzu3bt+Hi4oIvRBHP6jjnaQAHAFwCUDNhMg+AJ4B3Abyu5/obAEy/55iHh4feuw7t2rXTu/smERH9\nD6eikslJT0+HKIpahzVqTAUQC+BHAEPvHNuG6lkhUxq4fq87v65duxbDhg1D586drWpBLSIiQ+OP\nYmRyavanaKHnnBAArQFsvevYNwD6APBt4Po1NaJPnz7o3r07iwURkcRYLsjkODg4AKjeK0QXewAT\nAHwLQAMgF8ARAOpGXL9mQ++azyEiImmxXJDJ8fX1hUKhQEoD500FcA3AflQPiQAND4kAwBlUb7zl\n69vQPQ4iIrofLBdkcpydnaHq1g3HGzhvBIA2qH724hsA/VG9zHdDfgXg5+MDZ2fn5gUlIiKtWC7I\nJAWPHo14pRIVes5RApiI6rsWv6BxQyLlqN6OfURoqAQpiYhIG5YLMklz5sxBviAgroHzpgIoRvV0\n1MmNuG48gHxBwNy5c5sbkYiIdOA6F2SyzH1vESIia8VyQSbLGnZFJSKyRBwWIZPl7e2Nj1etQjSA\npYByI7MAAAKHSURBVM24jnjn/dEAPlm9msWCiMjAuEInmbQZM2YgLy8PUVFRyASwAmjSEEkhgJdQ\nXSyWLVuG6dPvXfibiIikxmERMgvR0dF4Yf58uAkClgsCJgH1dku9WzmqH958TanEdaUSn6xezWJB\nRGQkLBdkNjIyMjBv9mzsTUqCh1KJcEFAX1TvFeKE6pU3z6B6HYt4pRL5goCQ4GB8tm4dh0KIiIyI\n5YLMTkpKCtauXYt9e/bg7J1NzmooFAr4+fhgRGgo5s6di549e8qYlIjIOrFckFkrKirC+fPnUV5e\nDgcHB/j6+nLlTSIimbFcEBERkaQ4FZWIiIgkxXJBREREkmK5ICIiIkmxXBAREZGkWC6IiIhIUiwX\nREREJCmWCyIiIpIUywURERFJiuWCiIiIJMVyQURERJJiuSAiIiJJsVwQERGRpFguiIiISFIsF0RE\nRCQplgsiIiKSFMsFERERSYrlgoiIiCTFckFERESSYrkgIiIiSbFcEBERkaRYLoiIiEhSLBdEREQk\nKZYLIiIikhTLBREREUmK5YKIiIgkxXJBREREkmK5ICIiIkmxXBAREZGkWC6IiIhIUiwXREREJCmW\nCyIiIpIUywURERFJiuWCiIiIJMVyQURERJJiuSAiIiJJsVwQERGRpFguiIiISFIsF0RERCQplgsi\nIiKSFMsFERERSYrlgoiIiCTFckFERESSYrkgIiIiSbFcEBERkaRYLoiIiEhSLBdEREQkKZYLIiIi\nkhTLBREREUmK5YKIiIgkxXJBREREkmK5ICIiIkmxXBAREZGkWC6IiIhIUiwXREREJCmWCyIiIpIU\nywURERFJiuWCiIiIJMVyQURERJJiuSAiIiJJ/T8X/Li/WXmbWQAAAABJRU5ErkJggg==\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x10edcc160>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# 描画(edgeについている数字はcapacity)\n",
"\n",
"# Position nodes using Fruchterman-Reingold force-directed algorithm.\n",
" # 点の位置はランダムに決まるので、出来上がったグラフの形が微妙だったら、何回かやり直せばよい。\n",
" # 座標を指定することもできるので、点の数が少ない場合は手動で形を決めた方が良いかも（後述）\n",
"pos = nx.spring_layout(G, k=5.)\n",
"\n",
"# Draw only weight attribute as edge label.\n",
"edge_labels = {(i, j): w['cap'] for i, j, w in G.edges(data=True)}\n",
"nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)\n",
"\n",
"# Draw labels for nodes and edges.\n",
"nx.draw_networkx_labels(G, pos)\n",
"\n",
"# Finish drawing.\n",
"nx.draw(G, pos)\n",
"\n",
"# Display with Matplotlib.\n",
"plt.axis('off')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## A Naive Greedy Algorithm"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# もろもろをインポート\n",
"import networkx as nx\n",
"import matplotlib.pyplot as plt\n",
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# 例のグラフGを生成\n",
"G = nx.DiGraph()\n",
"G.add_edges_from([('s','v',{'capacity': 3}),('s','w',{'capacity': 2}),('v','w',{'capacity': 5}),('v','t',{'capacity': 2}),('w','t',{'capacity': 3})])\n",
"for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"まず、前節で作ったbfsPath（flowやcapacityについては考慮してなかった）を、naive greedy algorithmの中で使えるもの(bfsFlowPath)に改変する。"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"code_folding": [
0
],
"collapsed": true
},
"outputs": [],
"source": [
"def bfsFlowPath_(G, s, e):\n",
" '''\n",
" Search a path from s to t all of whose points have strictly positive capacity.\n",
" \n",
" Inputs:\n",
" G: a graph\n",
" s: a start point\n",
" e: an end point\n",
" each edge has two attributes:\n",
" capacity: capacity\n",
" flow: its current flow which should be no more than its capacity\n",
" Output:\n",
" path: a list of edges which represents a path from s to e.\n",
" At each edge of the path, its current flow is strictly less than its capacity.\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
"\n",
" past = [] # 過去に訪れた点を記録\n",
" path = []\n",
"\n",
" # 全ての点のsからの距離の初期値を無限大に\n",
" for p in G.nodes():\n",
" G.node[p]['dist'] = float('inf')\n",
" \n",
" # node s の距離を0に\n",
" G.node[s]['dist'] = 0\n",
" \n",
" # sに隣接する点をqueueに\n",
" # queueには、今後訪れるべき点が格納される\n",
" queue = deque()\n",
" for p in G.successors(s):\n",
" # current flow < capacity となるedgeだけをpathの候補に\n",
" # flow < capacity となるedge以外は存在しないものとして扱うのと同じ\n",
" if G[s][p]['flow'] < G[s][p]['capacity']:\n",
" queue.append(p)\n",
" \n",
" # あとで条件分岐に用いる\n",
" numberOfSuccessorsOfSource = len(queue)\n",
" \n",
" # sに隣接する点の距離を1に\n",
" for p in queue:\n",
" G.node[p]['dist'] = 1\n",
"\n",
" # BFSを用いてflow < capacityを満たすsからeへのpathがあるのか調べる\n",
" # pastに過去に訪れた点を格納\n",
" while len(queue)>0:\n",
" v = queue.popleft()\n",
" if v == e: break\n",
" else:\n",
" past.append(v)\n",
" for p in G.successors(v):\n",
" # (過去に訪れていない and flow < capacity)を満たすedge\n",
" if ( (not p in past) and ( G[v][p]['flow'] < G[v][p]['capacity']) ):\n",
" if ( not p in queue):\n",
" queue.append(p)\n",
" if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
" G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
"\n",
" # sからeへのpathが存在しない場合はNoneを返す\n",
" if numberOfSuccessorsOfSource == 0:\n",
" v = s\n",
" if v != e or v == s:\n",
" # print ('There is no path.')\n",
" return None\n",
" \n",
" # 以下、sからeへのpathが存在する場合\n",
" # 終点から遡ってpathを形成する\n",
" pp = e\n",
" while (1):\n",
" if pp == s: break\n",
" \n",
" pred = G.predecessors(pp)\n",
" \n",
" count = 0\n",
"\n",
" for p in pred:\n",
" # ここに、flow < capacity の条件を追加\n",
" # distの作り方から、flow < capは自然に満たされる\n",
" if ( G.node[p]['dist'] == G.node[pp]['dist']-1):\n",
" path.insert(0, (p,pp))\n",
" pp = p\n",
" break\n",
" else:\n",
" count += 1\n",
" \n",
" # 条件を満たすedgeがない\n",
" if count == len(pred):\n",
" break\n",
" \n",
" # pathがない場合\n",
" # 無駄な条件か？（ここまで来ているのなら、pathはあるはず。念のため残しておく。）\n",
" if path[0][0] != s:\n",
" return None\n",
" \n",
" return path"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"code_folding": [
0
],
"collapsed": true
},
"outputs": [],
"source": [
"def bfsFlowPath_(G, s, e):\n",
" '''\n",
" Search a path from s to t all of whose points have strictly positive capacity.\n",
" \n",
" Inputs:\n",
" G: a graph\n",
" s: a start point\n",
" e: an end point\n",
" each edge has two attributes:\n",
" capacity: capacity\n",
" flow: its current flow which should be no more than its capacity\n",
" Output:\n",
" path: a list of edges which represents a path from s to e.\n",
" At each edge of the path, its current flow is strictly less than its capacity.\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
" # 過去に訪れた点を記録\n",
" # sは最初から入れておく\n",
" past = [s]\n",
" # pathを記録するためのリスト\n",
" path = []\n",
"\n",
" # 全ての点のsからの距離の初期値を無限大に\n",
" for p in G.nodes():\n",
" G.node[p]['dist'] = float('inf')\n",
" \n",
" # node s の距離を0に\n",
" G.node[s]['dist'] = 0\n",
" \n",
" # sに隣接する点をqueueに\n",
" # queueには、今後訪れるべき点が格納される\n",
" queue = deque()\n",
" for p in G.successors(s):\n",
" # current flow < capacity となるedgeだけをpathの候補に\n",
" # flow < capacity となるedge以外は存在しないものとして扱うのと同じ\n",
" if G[s][p]['flow'] < G[s][p]['capacity']:\n",
" queue.append(p)\n",
" \n",
" # あとで条件分岐に用いる\n",
" numberOfSuccessorsOfSource = len(queue)\n",
" \n",
" # sに隣接する点の距離を1に\n",
" for p in queue:\n",
" G.node[p]['dist'] = 1\n",
"\n",
" # BFSを用いてflow < capacityを満たすsからeへのpathがあるのか調べる\n",
" # pastに過去に訪れた点を格納\n",
" while len(queue)>0:\n",
" v = queue.popleft()\n",
" if v == e: break\n",
" else:\n",
" past.append(v)\n",
" for p in G.successors(v):\n",
" # (過去に訪れていない and flow < capacity)を満たすedge\n",
" if ( (not p in past) and ( G[v][p]['flow'] < G[v][p]['capacity']) ):\n",
" if ( not p in queue):\n",
" queue.append(p)\n",
" if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
" G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
"\n",
" # sからeへのpathが存在しない場合はNoneを返す\n",
" if numberOfSuccessorsOfSource == 0:\n",
" v = s\n",
" if v != e or v == s:\n",
" # print ('There is no path.')\n",
" return None\n",
" \n",
" # 以下、sからeへのpathが存在する場合\n",
" # 終点から遡ってpathを形成する\n",
" pp = e\n",
" while (1):\n",
" if pp == s: break\n",
" \n",
" pred = G.predecessors(pp)\n",
" \n",
" count = 0\n",
"\n",
" for p in pred:\n",
" # ここに、flow < capacity の条件を追加\n",
" # distの作り方から、flow < capは自然に満たされる\n",
" if ( G.node[p]['dist'] == G.node[pp]['dist']-1):\n",
" path.insert(0, (p,pp))\n",
" pp = p\n",
" break\n",
" else:\n",
" count += 1\n",
" \n",
" # 条件を満たすedgeがない\n",
" if count == len(pred):\n",
" break\n",
" \n",
" # pathがない場合\n",
" # 無駄な条件か？（ここまで来ているのなら、pathはあるはず。念のため残しておく。）\n",
" if path[0][0] != s:\n",
" return None\n",
" \n",
" return path"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"code_folding": [
0
],
"collapsed": true
},
"outputs": [],
"source": [
"# 多分これで合ってる（上の２つは失敗作）\n",
"def bfsFlowPath(G, s, e):\n",
" '''\n",
" Search a path from s to t all of whose points have strictly positive capacity.\n",
" \n",
" Inputs:\n",
" G: a graph\n",
" s: a start point\n",
" e: an end point\n",
" each edge has two attributes:\n",
" capacity: capacity\n",
" flow: its current flow which should be no more than its capacity\n",
" Output:\n",
" path: a list of edges which represents a path from s to e.\n",
" At each edge of the path, its current flow is strictly less than its capacity.\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
"\n",
" # 過去に訪れた点を記録\n",
" # sは最初から入れておく\n",
" past = [s]\n",
" # pathを記録するためのリスト\n",
" path = []\n",
"\n",
" # 全ての点のsからの距離の初期値を無限大に\n",
" for p in G.nodes():\n",
" G.node[p]['dist'] = float('inf')\n",
" \n",
" # node s の距離を0に\n",
" G.node[s]['dist'] = 0\n",
" \n",
" # sに隣接する点をqueueに\n",
" # queueには、今後訪れるべき点が格納される\n",
" queue = deque()\n",
" for p in G.successors(s):\n",
" # current flow < capacity となるedgeだけをpathの候補に\n",
" # flow < capacity となるedge以外は存在しないものとして扱うのと同じ\n",
" if G[s][p]['flow'] < G[s][p]['capacity']:\n",
" queue.append(p)\n",
" \n",
" # あとで条件分岐に用いる\n",
" numberOfSuccessorsOfSource = len(queue)\n",
" \n",
" # sに隣接する点の距離を1に\n",
" for p in queue:\n",
" G.node[p]['dist'] = 1\n",
"\n",
" # BFSを用いてflow < capacityを満たすsからeへのpathがあるのか調べる\n",
" # pastに過去に訪れた点を格納\n",
" while len(queue)>0:\n",
" v = queue.popleft()\n",
" if v == e: break\n",
" else:\n",
" past.append(v)\n",
" for p in G.successors(v):\n",
" # (過去に訪れていない and flow < capacity)を満たすedge\n",
" if ( (not p in past) and ( G[v][p]['flow'] < G[v][p]['capacity']) ):\n",
" if ( not p in queue):\n",
" queue.append(p)\n",
" if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
" G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
"\n",
" # sからeへのpathが存在しない場合はNoneを返す\n",
" if numberOfSuccessorsOfSource == 0:\n",
" v = s\n",
" if v != e or v == s:\n",
" # print ('There is no path.')\n",
" return None\n",
" \n",
" # 以下、sからeへのpathが存在する場合\n",
" # 終点から遡ってpathを形成する\n",
" pp = e\n",
" while (1):\n",
" if pp == s: break\n",
" \n",
" pred = G.predecessors(pp)\n",
" count = 0\n",
"\n",
" for p in pred:\n",
" # ここに、flow < capacity の条件を追加\n",
" # distの作り方から、flow < capは自然に満たされる???\n",
" if ( G.node[p]['dist'] == G.node[pp]['dist']-1 and G[p][pp]['flow'] < G[p][pp]['capacity']):\n",
" path.insert(0, (p,pp))\n",
" pp = p\n",
" break\n",
" else:\n",
" count += 1\n",
" \n",
" # 条件を満たすedgeがない\n",
" if count == len(pred):\n",
" break\n",
"\n",
" return path"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"collapsed": false,
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[('s', 'w'), ('w', 't')]\n"
]
}
],
"source": [
"# bfsFlowPathが機能することを確認\n",
"print ( bfsFlowPath(G,'s','t') )"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"# 確認その2\n",
"print ( bfsFlowPath(G,'t','w') )"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[('s', 'v'), ('v', 'w')]\n"
]
}
],
"source": [
"# 確認その3\n",
"G['s']['w']['flow'] = 10\n",
"print ( bfsFlowPath(G,'s','w') )"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[('s', 'v'), ('v', 't')]\n"
]
}
],
"source": [
"# 確認その4\n",
"G['s']['w']['flow'] = 10\n",
"print ( bfsFlowPath(G,'s','t') )"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"# 確認その5\n",
"G['s']['w']['flow'] = 2\n",
"G['s']['v']['flow'] = 3\n",
"print ( bfsFlowPath(G, 's', 'w'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*bfsFlowPath*はキチンと動いていそう。次に、Naive Greedy Algorithmを実装してみる。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"code_folding": [
0
],
"collapsed": true
},
"outputs": [],
"source": [
"def naiveGreedy(G, s, t):\n",
" '''\n",
" Inputs:\n",
" G: a graph\n",
" s: a source vertex\n",
" t: a sink vertex\n",
" Outputs:\n",
" the graph G whose flow was modified by this naive greedy algorithm\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
" # initialize flows\n",
" for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0\n",
" \n",
" # そもそもsからtへのパスがあるのか確認\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" print (\"There is no path from \" + str(s) + \" to \"+ str(t) )\n",
" return None\n",
" \n",
" # sからtへのパスがある場合(lecture noteのA Naive Greedy Algorithmの部分に相当)\n",
" while(1):\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" break\n",
" else:\n",
" # path上のedgeについて、cap - flowの最小値を調べる\n",
" min = float('inf')\n",
" for edge in path:\n",
" if ( min > G[edge[0]][edge[1]]['cap'] - G[edge[0]][edge[1]]['flow'] ):\n",
" min = G[edge[0]][edge[1]]['cap'] - G[edge[0]][edge[1]]['flow']\n",
" \n",
" # path上のedgeのflowを更新\n",
" for edge in path:\n",
" G[edge[0]][edge[1]]['flow'] += min\n",
" \n",
" return G"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# 実験1\n",
"naiveGreedy(G,'t','s')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# 実験2\n",
"G_opt = naiveGreedy(G, 's', 't') "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"code_folding": [
0
],
"collapsed": false,
"scrolled": true
},
"outputs": [],
"source": [
"# 描画(edgeに付いている数字は(capacity, 'flow')の意味)\n",
"\n",
"# Position nodes using Fruchterman-Reingold force-directed algorithm.\n",
"# pos = nx.spring_layout(G_opt, k=5.)\n",
"\n",
"# 各ノードの座標を指定することも可能\n",
"pos={'s':(0,2),'v':(3,4),'w':(3,0),'t':(6,2)}\n",
"\n",
"# flowとcapacityを同時に表示させようとしてみた\n",
"# なにが起きてるのかよくわからないけど、(capacity, 'flow')というかんじでうまいこと表示されてる\n",
"edge_labels = {(i, j): (w['cap'], str((w['flow'])) ) for i, j, w in G_opt.edges(data=True)}\n",
"nx.draw_networkx_edge_labels(G_opt, pos, edge_labels=edge_labels, font_color='r')\n",
"\n",
"# Draw labels for nodes and edges.\n",
"nx.draw_networkx_labels(G_opt, pos)\n",
"\n",
"# Finish drawing.\n",
"nx.draw(G_opt, pos)\n",
"\n",
"# Display with Matplotlib.\n",
"plt.axis('off')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"キチンと動いている。（この場合はたまたまnaive greedy algorithmでも最大流が実現されている。）\n",
"\n",
"描画の際、\n",
"[公式ドキュメント](http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.drawing.nx_pylab.draw_networkx_edge_labels.html#networkx.drawing.nx_pylab.draw_networkx_edge_labels)や[見つけたスライド](http://www.logopt.com/python_learning/wp-content/uploads/2015/10/networkx.pptx)を参考にした。\n",
"\n",
"ノード数が小さいグラフであれば描画の際に各ノードの座標が指定した方が綺麗に描けそう。"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"## Residual Graphs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ford-Fulkerson algorithmを実装する準備として、あるグラフについて、対応するResidual graphを生成する関数(*makeResidualGraph*)を作る必要がある。"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"code_folding": [
0
],
"collapsed": true
},
"outputs": [],
"source": [
"def makeResidualGraph(G):\n",
" '''\n",
" Input: a graph G\n",
" Output: its residual graph Gf\n",
" '''\n",
" Gf = G.copy()\n",
" edgeList = G.edges()\n",
" \n",
" for edge in edgeList:\n",
" # Initialize flow\n",
" Gf[edge[0]][edge[1]]['flow'] = 0\n",
" \n",
" # 逆向きのedgeがないものは追加\n",
" if not (edge[1], edge[0]) in edgeList:\n",
" Gf.add_edge(edge[1],edge[0])\n",
" Gf[edge[1]][edge[0]]['capacity'] = Gf[edge[0]][edge[1]]['flow']\n",
" Gf[edge[1]][edge[0]]['flow'] = 0\n",
" \n",
" return Gf"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"Gf = makeResidualGraph(G)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[('t', 'w'),\n",
" ('t', 'v'),\n",
" ('s', 'w'),\n",
" ('s', 'v'),\n",
" ('w', 't'),\n",
" ('w', 's'),\n",
" ('w', 'v'),\n",
" ('v', 't'),\n",
" ('v', 's'),\n",
" ('v', 'w')]"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Gf.edges()"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"2\n",
"0\n",
"0\n"
]
}
],
"source": [
"print(Gf['s']['w']['flow'])\n",
"print(Gf['s']['w']['capacity'])\n",
"print(Gf['w']['s']['flow'])\n",
"print(Gf['w']['s']['capacity'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"きちんと動いていそうだ。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Ford-Fulkerson Algorithm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ford-Fulkerson Algorithmを実装してみる。"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"code_folding": [
2
],
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"def fordFulkerson(G, s, t):\n",
" '''\n",
" Inputs:\n",
" G: a graph\n",
" s: a source vertex\n",
" t: a sink vertex\n",
" Outputs:\n",
" the graph G whose flow was modified by Ford-Fulkerson algorithm\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
"\n",
" # initialize flows\n",
" for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0\n",
"\n",
" # Forward edgesを記録\n",
" forwardEdges = G.edges()\n",
" \n",
" # Residual Graphの作成\n",
" Gf = makeResidualGraph(G)\n",
" \n",
" # そもそもGにおいてsからtへのパスがあるのか確認\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" print (\"There is no path from \" + str(s) + \" to \"+ str(t) )\n",
" return None\n",
" \n",
" # Gにおいてsからtへのパスがある場合\n",
" while(1):\n",
" # これ以上パスがみつからない場合は最適なのでそこでループを打ち切る\n",
" path = bfsFlowPath(Gf, s, t)\n",
" if path == None:\n",
" break\n",
"\n",
" # まだパスがある（最適でない）場合\n",
" else:\n",
" # path上のedgeについて、capacity - flowの最小値を調べる\n",
" diff = float('inf')\n",
" for edge in path:\n",
" diff = np.min([diff, Gf[edge[0]][edge[1]]['capacity'] - Gf[edge[0]][edge[1]]['flow'] ])\n",
" \n",
" # path上のedgeのflowを更新\n",
" for edge in path:\n",
" if edge in forwardEdges:\n",
" Gf[edge[0]][edge[1]]['flow'] += diff\n",
" # このとき、backward edgeのcapacityを更新する必要あり？\n",
" Gf[edge[1]][edge[0]]['capacity'] += diff\n",
" else:\n",
" Gf[edge[0]][edge[1]]['flow'] -= diff\n",
" Gf[edge[1]][edge[0]]['capacity'] -= diff\n",
" \n",
" # もともと無かったedgeを消去\n",
" for edge in Gf.edges():\n",
" if not edge in forwardEdges:\n",
" Gf.remove_edge(edge[0],edge[1])\n",
" \n",
" return Gf"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# Ford-Fulkersonを用いて最大流を求めてみる\n",
"T = fordFulkerson(G, 's', 't')"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAFkCAYAAAC9wjgoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzt3XucTeXix/HPntnGuGuIjiQ0zRiTSy4nGiq5nAidpFJO\nSnKLEaIjtxKT0OhCNXI56UIlnfq5RRxOhBLjOoNcUhriUBjMsGfW74/Htsc0N+zZe2bW9/16zauz\n13r22s8ca9b+rmc9F4dlWRYiIiJiWwH+roCIiIj4l8KAiIiIzSkMiIiI2JzCgIiIiM0pDIiIiNic\nwoCIiIjNKQyIiIjYnMKAiIiIzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNKQyIiIjYnMKAiIiI\nzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNKQyIiIjYnMKAiIiIzSkMiIiI2JzCgIiIiM0pDIiI\niNicwoCIiIjNKQyIiIjYnMKAiIiIzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNKQyIiIjYnMKA\niIiIzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNKQyIiIjYnMKAiIiIzSkMiIiI2JzCgIiIiM0p\nDIiIiNicwoCIiIjNKQyIiIjYnMKAiIiIzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNKQyIiIjY\nnMKAiIiIzSkMiIiI2JzCgIiIiM0pDIiIiNicwoCIiIjNOf1dAREpHJKTk9mzZw+pqakUL16c0NBQ\nSpcu7e9qiYgXKAyISLYSEhKIi4vj68WL2bVvH5ZlXdzncDgIr1mT1u3a0adPH2rXru3HmorI1XBY\nGf+6RUSA/fv383Tv3nz19ddUcjp5wOWiMVAbKAmcARKADcB8p5MjLhf3tG7N29OmUaNGDX9WXUSu\ngMKAiFxixowZDIyOpqLLxcsuF52BoBzKnwM+A553OjnmdPL6lCk89dRTvqmsiHiFOhCKyEUxMTH0\n7NmTR1JS2OZy8Sg5BwEu7H8U2O5y8UhKCj179iQmJib/KysiXqOWAREBTItAz549GQuMvIrjjAVG\nXzhejx49vFM5EclXCgMiwv79+6lTuzaPpKQw/SqPZQG9gLnBwWxLSFAfApFCQGFARGjbpg2JK1ey\nzeWijBeOdxKo43RSu0ULlixb5oUjikh+UhgQsbmEhAQiIyP5CPPs31vmAF0vHD8iIsKLRxYRb1MH\nQhGbi4uLo5LTSecs9s3HXCRWZ7Fv2oV9Cdkc9wGgktPJO++8452Kiki+URgQsbmvFy/mAZcry1ED\n9wKlgU+z2PcpcAtm7oGsFAcecLlYvmSJdyoqIvlGYUDExk6dOsWufftonM3+YKADZh6BjM8TfwP+\nC3TJ5fiNgJ1795KcnHzVdRWR/KMwIGJje/fuxbKsbO/uAR4GjgCrMmybhwkHD+Vy/EjAsiz27Nlz\nVfUUkfylMCBiY6mpqYCZYjg79wBlgU8ybPsUqA+E5nL8Epk+R0QKJoUBERsrXrw4YNYayE4Q8Hfg\n30A68CvwLbk/IgA4m+lzRKRgUhgQsbHQ0FAcDke2IwLcHgb+B6zAPCKA3B8RAOzArG4YGppbG4KI\n+JPCgIiNuVwuKpQty4ZcyrUCrgE+xjwi+CtwYx6O/wNQ66abKF269NVVVETylcKAiA2lp6cza9Ys\nwsLC+N+JE3yCWX0wO06gE6ZV4Hvy9oggFbO8cau2ba++wiKSrxQGRGxmw4YNNG3alB49enD06FEA\njmOGD+bkYeA04AAezMPnzAeOuFz07dv3aqorIj6g6YhFbOLo0aMMHz6cmTNnkvnPPgD4C5AIXlub\nIAIIrFKFDZs2UblyZS8cVUTyi1oGRIo4l8vF1KlTCQsLY8aMGX8KAmBGCRwCBnnh8yxgMHC8WDFO\nnj5NWFgYb7zxBi6XywtHF5H8oDAgUoStXr2ahg0bEh0dzR9//JFj2cg6dZgJjLuKz7MuvH8mMPWd\nd9i7dy9du3Zl0KBB3Hrrraxateoqji4i+UVhQKQISkpKomvXrtxxxx1s3bo1x7I1a9ZkwYIFbN26\nlXHjxjEK6AmcuszPPAn0AkYDMTEx9OjRgwoVKvD222/zww8/ULZsWVq0aEGXLl04ePDgFf1eIpJP\nLBEpMlJTU62JEydapUuXtjA36tn+lChRwho7dqx19uzZS44xffp0q1RwsFXN6bQ+AisVLCuHnxSw\nPgKrmtNplQoOtmbMmJFl3dLT063333/fqly5slWyZElr/PjxVkpKii/+bxGRXKgDoUgRsWzZMgYM\nGMCuXbtyLdu5c2diY2OpVq1alvv379/P071789XXX1PJ6eQBl4tGmLUGSmBmFtyBmUdgvtPJEZeL\ne1q35u1p06hRo0aOn33y5EnGjBnDm2++SY0aNXjjjTdoq+GHIn6lMCBSyP30008MHjyYf//737mW\njYiIYMqUKbRs2TJPx05ISCAuLo7lS5aw88KiRm4Oh4NaN91Eq7Zt6du3LxEREZdV74SEBAYMGMCK\nFSvo2LEjr732GjVr1rysY4iIdygMiBRSZ8+eZeLEibzyyiukpKTkWLZMmTK8+OKLREdHU6xYsSv6\nvOTkZBYsWMCjjz7KnDlz6NChw1XPLGhZFvPnz2fw4MEcOXKE5557jmHDhlGyZE5LJ4mIt6kDoUgh\nY1kWX375JbVr1+bFF1/MNQh069aNXbt2MXjw4CsOAgClS5cmPDwcgPDwcK9MMexwOOjcuTOJiYkM\nHTqUCRMmEBERweeff57lEEgRyR8KAyKFyK5du2jbti1///vf+emnn3IsW79+fdasWcPs2bP5y1/+\n4psKXqFSpUoxduxYduzYQd26dXnggQdo06YNiYmJ/q6aiC0oDIgUAsnJyQwbNow6deqwdOnSHMte\nc801F4fzRUVF+aiG3hEaGsqCBQtYuHAh+/fvp27dugwdOpSTJ0/6u2oiRZrCgEgBZlkWc+fOJTw8\nnAkTJnD+/PlsyzocDnr37s3u3bvp27cvgYGBPqypd917771s376dMWPG8PbbbxMeHs6HH36oRwci\n+URhQKSA2rp1K3fddRePPvooSUlJOZZt0qQJGzZsIC4ujooVK/qohvkrODiY4cOHs3PnTu644w4e\ne+wx7rjjDjZv3uzvqokUOQoDIgXMH3/8wYABA7j11lv55ptvcixbqVIl3nvvPb799lsaNmzooxr6\n1g033MAnn3zCihUrOH78OA0bNqRfv34cP37c31UTKTIUBkQKiPT0dGbNmkVYWBhTpkwhPT0927KB\ngYEMGjSI3bt38/jjjxMQUPT/lO+++242b95MbGwsH374IWFhYUyfPp20tDR/V02k0Cv6VxCRQmDD\nhg00bdqUHj16cPTo0RzLtmjRgi1btjB58mTKlSvnoxoWDMWKFWPgwIHs2rWL9u3b06tXL2677TbW\nr1/v76qJFGoKAyJ+dPToUXr27Mltt93G999/n2PZqlWrXmwuj4yM9FENC6brrruO9957j7Vr12JZ\nFk2bNuXJJ5/kt99+83fVRAolhQERP9mwYQNhYWHMmDEjx17yQUFBFzvSPfTQQzgcDh/WsmBr2rQp\n33//PXFxcXz55ZeEhYXxxhtv4HK5/F01kUJFYUDET+rUqUNISEiOZdq1a8eOHTuIiYmhVKlSPqpZ\n4RIYGHhxSGXXrl0ZNGgQt956K6tWrfJ31UQKDYUBET85ffo0YWFhWe6rWbMmCxYsYNGiRYSGhvq4\nZoVThQoVLk62VLZsWVq0aEGXLl04ePCgv6smUuApDIj4WFpaGnFxcYSFhbF27dpLVvsrUaLExWl5\n27dv78daFl4NGjRgzZo1vP/++6xatYrw8HBeeeUVUlNT/V01kQJLYUDEh9auXUvjxo3p27cvf//7\n3/nxxx/58ssvCQoK4oEHHiAxMZGRI0cSHBzs76oWag6Hg8cee4zdu3fTp08fRo0aRZ06dViyZIm/\nqyZSICkMiPjA4cOHefzxx4mKiiIwMJD169czc+ZMKlWqxM0338zOnTv57LPPuPHGG/1d1SKlbNmy\nxMbGsmXLFqpVq0a7du2477772Ldvn7+rJlKgKAyI5KPz58/z2muvERYWxqJFi5g+fTrfffcdt912\n2yXlatSo4aca2kPt2rX5+uuvmTdvHvHx8dSuXZvRo0dz5swZf1dNpEBQGBDJJytWrKB+/foMGTKE\nbt26sXv3bp566ilbzBZYEDkcDjp37kxiYiJDhw5lwoQJRERE8Pnnn2sBJLE9XZVEvOznn3/moYce\nolWrVoSEhLBp0yamTp2a6zBC8Y1SpUpd7KRZt25dHnjgAdq0aUNiYqK/qybiNwoDIl6SkpJCTEwM\nERERrFmzhg8//JBvvvmGevXq+btqkoXQ0FAWLFjAwoUL2b9/P3Xr1mXo0KGcPHnS31UT8TmFAREv\n2L17N7fccgsvvvgi/fr1Y9euXXTt2lWzBRYC9957L9u3b2fMmDG8/fbbhIeHs379ej06EFtRGBDx\ngooVK1KrVi22bdvGxIkTKVOmjL+rJJchODj44pTPd955JyEhIQoDYisOS2e8SM5OnADLgvLlIT0d\nsugA6P4zKuotAZs2baJhw4Zs3LiRBg0a+Ls6/vX++9CxozkvRAo5tQyIZJYxH//8M/zjH9CzJ5w7\nl2UQABMCinoQkAsOH4bhw+H55835kZHuraSQUhgQySzjl3q1ajB7tvkC6NkT4uPN9vR0/9RN/Csl\nBXr1gm3b4IsvoG5dEwDcqyS6zx2dH1LIKAyIZHb8OEyYAIsXm9chIfDOO3DmDDz3nNmmuQLs5+RJ\niImBTZvM+dC4sdm+dSu8+ioMGACrV5ttOj+kkNEZK/aV3d3biRPmAv/1155tt9wCzz4LO3bApEm+\nqZ8ULPPnw6pVMGQIVK0KaWlm+9Gj8Ouv5ry5/364/XbTcgB6bCCFhsKA2FdAAJw9Cx9/DN9/72nq\nrVED7r4bDh6E777zlG/SBKKjzV3g//7nnzqLf6SmwmefmcdGjz5qtrnv/lu1gthY8zhp50646SaY\nMsXsUz8SKSQUBsSe0tNh/HioWNE0/bZvD089BVu2mP316pk7v82bL31f796mI+H//Z95rTs/e/jv\nf+H33+HOO6FSJbPN/UVvWRAUZMJkxYqmH8F//gNaDEkKEYUBsacffzTNvm+9ZToFvv02HDgA/fub\n/Y0awZtvmi//jEJC4O9/hw8/9H2dxX9+/dV86UdFmdcZQ6DDYV47neZ1WpoZbqhWASlEFAbEnjZs\ngF274LHHzEW8c2cYNsy0DMyda8pUrWr+m/nuPyrKPB8+elQX/KLO/W//229mJEFkpHmdsVXA/frA\nAXMO/etf0Latedx0JZ8l4gcKA1J0WFbeh3SdPAk33wxJSZ5tzZtDp07w8sue48Gfv/CDg00LgS7e\nRZ/7337jRtM3ADx9S8D0Odm8Gbp3h7/+FdavhzFjYMQIsz+v56NlKViKXykMSOGX8Us7IMAMDTx9\nOueyFSqY/52xT0DJkqalYPdu00LgcFx6MXe/t0ED8z7NPGcPlmX6AZw7Z84Hp9N0IH35ZejQwTw2\nOn0aPvgAli6FLl1MYIS8DTE8exbGjjWPnjIHTM1XID6iMCCFn/uO6ptvoE0b04x///3w7rueu7jM\nd/kdOpiL8LffQnKy51g33gj168OyZeZ1xou5+70nTkDr1nDsWP79TlJwOBwmPAYEmJ8//oBRo2Dk\nSBMg16+HTz81517x4pfXGgAmWG7dCr/8Yj4rJQWOHDH73OefQoHkM4UBKXwy3z0dOmQ6+nXpYkYB\nTJliHgGMGOGZBCZjE2xamrmId+oEK1d6ygCUK2eGFFarlv3nli8PDz4If/mLd38vKbjatDEzD4L5\n9580yYSBb76Bv/3NTEJ0/rzZn9cJh9zn5MqVZjTCww+b12+9ZVqo7r7brH9wOccUuUI6w6TwcTjM\nhfenn8zrM2dMZ60vvzQX6VatzAX1+HE4dSrr94MZOVCmjJlt0D3H/PbtJijcdFP274uIMC0PYh+h\noebfHUwoLF0aXnrJtBI98YQZnhoSYsJBRu6JibJz9Kjpt3L99VCzpjl2SAg88gjcdZd5FNG6tRnN\nIJKPtGqhFD6//27uylJSYOZMs+3wYbjuOk+Zzz83k8BMmXLpXX7mjlpr18LgwaZZtnp10+Tbp4+Z\ng6B4cZ/8OoWJVi28wLLMF717OCGY/gKNG5svczCPoUqUyNvxjh/3vC+jAwdM8Oze3Ux4JZJP1DIg\nhc8115ghXqdPexYOcgeBPXsgPNzcWR04AE2bQlycec4LniDgbgm4/XZYsMCEhubNzZDDyZMVBCRn\nDocnCLj7pfztb54v9EOHoFQpWLIk5+O4+wK432dZnsdR586ZPiw33ug5ju7dJJ8oDEjh4r4Y3nmn\n+e+cOZfuDw42d/Y7d5pOgP37w7RpnrkDzpwxrQqPP+55xnvttXDvvWZIWGSkuUCrw5bkVcbWATCd\nAZ95xgw1rFs35/dm7guQseUqKMg8Qli50jwygLwNP0xPV2iQy6YwIIWL+2IYGWnu5DPPCFe1Kgwa\nZPoQVKoE//ynac49e9aUKVnS/JQvb+7eMktP9/QaF7kSxYvDbbeZtQyuvz7v73Ofe2BGFowda/oL\nRERAv35Zv8d93qemmgCcmmqOoTkL5DI5cy8ikk8yXvzc8jL5irtMxgtkdu+JjzejA66/3lNm0KDs\nn+UqBMjVCg83P3mR8W/A5TIrZX72mel/UKWKWSHx3nvNI4fs/ja2bYOePU0fmr17oWtXmDgRypb1\n3u8kRZ7CgPie+6LmvgjGx5tn+k2beiZryUnGC2JWF8hDh8wz2BUrzEWxY0fz4+YOAmlpEBh4db+L\niDe8/LIZDWNZJkjMnGmmNIasZ8J0n7uLFpn3Op1mBM25c54pkZ95xve/hxRaCgPie+6L2ty55jn9\nmTNmiF/58maI1l135f2LOnMQ+OknGDrU3CHt32/6DAwblnVLgIKA+FtAgBkdM2aM6cMyfjw8++yl\nix5ldZ66t02ebFoQJk/2jJpp0MCMpOnb1/Q7OH/edKx1D40UyYLaRMU34uPNFK5g7nRGjDDjtHv3\nNjOwvfmm6cg3caIpc6Vf1NWrwz33wPPPm4vs2LGeJlaRguiaa8yz/pkz4bXXoHJlc/4eO5b134F7\n9MK//23Cb+fOlw6fDQszLWzuWQzXrjWPxmbNMq+PHDF/FydO5OuvJYWLwoD4xhNPmIsXmLv5Nm0g\nNtZcpEJCoGVLM5FLWNiVf3G739ejh5khEMyFU4vASEHm/nLv3t3Ml/Hee2Z57Uce8QyBTU42Q2XB\n02owZ46ZOrtJE8+xzp41AeH0ac+qm/HxJnDccYd5Xb68mXUz8wRJYmsKA5L/jh41M7hVr+7Z1rw5\ntGvnef3JJ2ZxoNq1TXm4NBTkJSBk7ksA5sKpICAFWeb5Cjp0MItlzZljWgnALILUqZPpWAhmyOGx\nY6Z/Qca/q8OHTQfERx4xrzduhFWrTMgODTXbgoIgIcGz0JZazQSFAfGFa681M/u5p2bN2IM6Kcm0\nEvTrB7VqwdSpJihs3Hjpl/jlfqErAEhhkzEUWBZUrOiZ/KpKFTNUtn5987piRROaK1b0vP/sWdP6\ndvy4Z7bC0FDz2KxDB0+57dvN2h3ulT31tyIoDEh+c9911K3rWQkwoypV4IUXTIe/efPgv/81c7QP\nH272u++WZs+GL77wTZ1F/Cmr1qz77jOzELpbChwOM1x23z5Pma++Mv0OoqNNP5m0NLPwVp8+0KiR\np1xqKvz2GxQrZl6rZUBQGJD85l6S9eabzbPMM2f+PJY/KspctMA822zc2DSTuteOBxg92iwTC5od\nUOwn84JHxYqZoYOffmpWO3zmGfjHP8xkRyNGmDIBAVl/0W/ebBY+atnSvFbLgKAwIL4QHGzmVz96\nFNatM9uy+0JPSjLzAzzxhLmYnTtntvft67kgamIgsZusRhW0bWv6Azidpsn/zTfNY7Zy5TydZrP6\nov/XvzyrbqpVQC7QPAPiG23bmh7SS5eaOxL3F3p6uhkDffo0fPedmTilShVzlwOmsxOYTlIZe02L\n2J1lmWm5P/roz7N5Zne3v3SpGWoYG5tzObEdhQHxjdq1oVUrc9e/cCG0b2+2Hz9uLlBxcebOPzo6\n63nYu3TxbX1FCjqHw9PCllNrmbuVYMsWM1th587mcYJIBgoD4jtPPmkmHho82LQUBAaa3tAdOphV\nCDOu8KapgkVyl5dHZg6Hedw2YYIp/+qr+V8vKXT08FV8p3p1M8NgcLCZJvi77zzb3UHAPXpAQUDk\n6rj7A+zbB089ZSYtio01sxWqr4BkojAg+crKPHFQ6dJmgqFSpcx0xMnJl74h89rwInJlHA7TwvbF\nF2aCofffN+sWuPeJZKArr+QLy7LYtm0bt9xyCw73hcf934gI01S5YoVZREVE8kdgoFnSOCTEM69A\nBi6Xi507dxIREUGgWuNsTS0D4nUJCQm0atWKO++8E5e72T8jd2tBy5ZmXgEpNKpVq8a7775LtYwL\n40jBVrlylkEAIDAwkPvuu4/bbruN9evX+7hiUpAoDIjXnDhxgsGDB1OvXj1++eUX5syZQ5B7aGBG\naqIstEJCQnjiiScICQnxd1XECxwOBx988AHp6ek0bdqUJ598kt9++83f1RI/UBiQq5aens77779P\neHg406ZNY+zYsWzbto22bdv6u2riZQEBARQrVowATfxUZNx+++1s2LCBuLg4vvzyS8LCwnjjjTey\nbtWTIkt/0XJVNm3aRLNmzXj88cdp0aIFu3btYtiwYRR3L7AiIgVeYGAgvXv3Zvfu3Tz66KMMGjSI\nW2+9lVWrVvm7auIjCgNyRY4dO0bfvn1p1KgRp06dYuXKlcydO5eq7jXURaTQqVChAu+88w4//PAD\nZcqUoUWLFnTp0oWDBw/6u2qSzxQG5LKkpaURFxdHWFgYc+bM4fXXXyc+Pp677rrL31UTES9p0KAB\na9asYfbs2axatYrw8HBeeeUVUlNT/V01yScKA5Jna9eupXHjxvTt25f77ruP3bt3M2DAAJyaG0Ck\nyAkICKBbt27s2rWLPn36MHLkSOrUqcOSJUsulvnoo4/49NNPL51PRAolhQHJ1eHDh3n88ceJiooi\nICCAdevWMWvWLCq711YXkSKrXLlyxMbGsmXLFm644QbatWvHfffdxw8//EB0dDQPP/wwLVu2ZMeO\nHf6uqlwFh6VIJ9k4f/48U6dO5YUXXiAoKIjx48fz5JNPanISu9q+3SwqFR9v1pgoUcIsTd2sGdx7\nr3ktRZplWcyfP5/Bgwfz66+/kp5hKfLAwECio6N58cUXKVeunB9rKVdCYUCytGLFCgYMGMDOnTvp\n27cvL730ksaW29XixTB2LGzaZJbMrV3bTBaVkgJJSbBxo/nfTz4JI0ZAhQr+rrHks9WrV3PHHXdk\nua9SpUpMnDiRxx57TENQCxGFAbnEzz//zJAhQ5g3bx5RUVFMnTqV+vXr+7ta4i9vvgnvvgvPPAMP\nPQTZ3fFt2AAzZph58DVpTZGWnp7O7bffznfuhcay0aRJE6ZOnUrDhg19VDO5GgoDAkBKSgqxsbG8\n/PLLlC1blkmTJtG1a1fPugJiT7/+Ctdfn/fyP/9sVsWTIsuyLD799FOeffZZfv311xzLOhwOevXq\nRUxMDBXUYlSgKQwIixYt4plnnuHAgQMMHDiQUaNGUbZsWX9XS0QKsOTkZGJiYoiNjeV8LguOXXPN\nNcTExNCrVy/1OSqg9EDHxvbs2UP79u1p3749NWrUYOvWrUyaNElBQP5s6VJYuNDftZACpHTp0owf\nP57t27dzzz335Fj2999/5+mnn6ZRo0Z8++23PqqhXA6FARs6ffo0I0eOJDIykm3btjF//nyWLVtG\nRESEv6smBdXzz/+5L0BMDAQEXPojthMWFsbixYv58ssvqVGjRo5lN2/eTLNmzejWrRuHDh3yUQ0l\nL/TXayOWZTFv3jwiIiJ49dVXGTZsGImJiXTq1El9AyRne/dCkyaXbrv7btOf4IsvYPZs/9RLCgSH\nw0HHjh3ZsWMHY8aMITg4OMfyH3zwAeHh4Xl6xCC+oTBgEwkJCbRq1YqHHnqIW2+9lYSEBMaMGUPJ\nkiX9XTUpDCwLMl/gS5Y0Qwo7doRcmonFHkqUKMHo0aMv3mTk5NSpUwwZMoR69eqxfPlyH9VQsqMw\nUMSdOHGCwYMHU69ePX755ZeLzXk1a9b0d9WkMAkNhWXLLt22bBm4zyP1Q5YMqlevzvz581m6dCnh\n4eE5lk1MTKR169Z07tyZAwcO+KiGkpnCQBGVnp7O+++/T3h4ONOmTWPs2LFs27aNtm3b+rtqUhg9\n/TQMHWr6CSxeDC++CKNHQ58+njJ61CSZtGnT5mLH5NKlS+dYdv78+URERDBu3DhSUlJ8VENx09DC\nImjTpk3079+fdevW0aVLFyZNmqSlheXqvfSSmYTo99+halUTDvr3N/vOnTN9Bx56yL91lAIrKSmJ\n5557jo8++ijXsjVr1uT111+nffv26s/kIwoDRcixY8cYOXIk06ZNIzIykilTpmhpYfG+8+ehWDF/\n10IKqdWrV9O/f3+2bt2aa9l27drx+uuvc/PNN/ugZvamMOBjycnJ7Nmzh9TUVIoXL05oaGiuzWe5\nSUtLY/r06YwYMQKXy8XYsWN5+umntbSwiBRILpeLadOmMXLkSP74448cywYFBfHss88yYsQISpUq\nddmflR/X3CLJkny3Y8cOKzo62qp1002Ww+GwgIs/DofDqnXTTVZ0dLS1Y8eOyz72t99+a916660W\nYHXv3t06fPhwPvwGYltvvWVZ+/b5uxZSRB05csTq2bPnn66LWf1UrVrV+vjjj6309PRcj5uf19yi\nSmEgH+3bt8+6p3VrC7AqOZ1WX7BmgbUerK0X/jsLrL4X9gPWPa1bW/vycPE9dOiQ1a1bNwuwGjZs\naK1bt84Hv5HYTv/+lhUUZFkOh79rIkXY999/b/31r3/NNRAA1l133WVt27Yty+Pk5zW3qFMYyCfT\np0+3SgXiJA75AAAgAElEQVQHWzc6ndZHYKWawVfZ/qSC9RFY1ZxOq1RwsDV9+vQsj3vu3Dlr8uTJ\nVpkyZawKFSpY7777ruVyuXz824mt7NljWbNn+7sWUsSlpaVZs2bNsq699tpcA0FgYKA1cOBA648/\n/rj4/vy65tqFwkA+GDdunAVYT4F1MpcTMvPPyQvvA6xx48Zdctzly5dbtWvXtgICAqx+/fpZx44d\n89NvKCKSP37//XdrwIABVmBgYK6hoFKlSta//vUva+zYsflyzbUThQEvmz59ugVYYy/zhMz889KF\nk3PGjBnWgQMHrAcffNACrKioKCs+Pt7fv6aISL7aunWrdeedd+bp0YG3r7l2pNEEXrR//37q1K7N\nIykpTL/KY1lAT+BDpxOH00n58uWZNGkSXbt21bhbEbEFy7L45JNPePbZZ0lKSsqyTADQHZiRzTHW\nAcuAQUBO67FaQC9gbnAw2xIScl10qahRGPCitm3akLhyJdtcLsp44XgngQgg+MYbid+6VUsLi4gt\nJScnExMT86eFjQKAvwCJkO01NxZ4DtgPVMvlc04CdZxOardowZLM028XcZqO2EsSEhL46uuvedlL\nQQBMip0E7DtwgF9//dVLRxURKVxKly7N+PHj2b59O/dkWBQrHZhI9kEAzB1/XpUFxrtcfPX11yQm\nJl5ZZQsphQEviYuLo5LTSedcyiUDA4EaQDBQGWgDbM6m/ANAJaeTd955x2t1FREpjMLCwi4utla2\nbFlCIMdr7hhMqwBAdcwXXiDwcw7vses1V1PUecnXixfzgMtFUC7legOfA9GYRwDHgDWYZq76WZQv\nDjzgcrF8yRJvVlfEO8aMufT1Cy/4px5iGw6Hg44dO/KXihW5++TJHK+5DwC7gY+BN4AKF7Zfm8N7\n7HrNVRjwglOnTrFr376LCTQnizEdAydm2DYkl/c0AuL27iU5OVnTaErBknHJWXU/Eh85deoUu/fv\n55+5lLsFaIAJA/eRe58BNztecxUGvGDv3r1YlkXtPJQtD3wHHMJ0fMmLSEyv2j179lC/flbtByJ+\nMmuWv2sgNnQ519wrYcdrrvoMeEFqaioAJfNQdiKwHbgBuA3zTGt/Lu8pkelzRETs7HKuuVfCjtdc\nhQEvKF68OABn8lD2QWAfMBW4HngVk0KX5vCes5k+R8Tn/vtfOH06+/1ffQWrV/uuPmJrl3PNvRJ2\nvOYqDHhBaGgoDoeDhDyWrwz0wXQk3I/p1BKTQ/kdmE4zoaGhV1dRkSvVogXs2ZP9/rVrYdIk39VH\nbO1yrrlXMkWbHa+5CgNeULp0acJr1mRDLuXSMZNaZFQRqALk1Bj1A1Drppts05FFCiCHI+cOgg0b\nwsaNvquP2Frp0qUJvfHGXK+5AKUu/PePyzi+Ha+5CgNe0rpdO+Y7nZzLocwpzKOB7sDrmOkzH8ac\neI9m855UYL7TSau2bb1ZXZHL16ABBARk/dOpExw65O8aig24XC6mTp3KgaQkPoEcr7kADTETDw0H\nPgQ+wfMYICt2veZqOmIvSUhIIDIyko/I/ov9PDAKM0/2PkxLQSjmkUGvbN4zB+h64fgRERHerbRI\nXgUGQmws1KyZc7mOHX1TH7Gl1atX079/f7Zu3XpxW07XXLeXgTjMKK50cp6a2K7XXIUBL8qvtQmo\nXJnvfviBqlWreuGoIlcgMBA2bYJ69fxdE7GhpKQkhg4dypw5cy7Znpe1CS6H1iYQr3h72jT+53Qy\n2AvHsoDBwPFixTiXlkZ4eDivvPKKrYa6SAHy+OMQEuLvWojNnDt3jkmTJhEeHv6nIADmLv8QZkXC\nq2UBzwLHnE7enjbNC0csXBQGvKhGjRq8PmUKM4BxV3Ec68L7ZwJT33mHPXv20KdPH0aOHEmdOnVY\nYrNpMqUAmDULbrjB37UQG1m2bBl169blueeeIzk5Odty6ZhrpTeuuTOAN6ZOtd3yxQBY4nXjxo2z\nAOspsE6aPth5/jlx4X2AFRMTc8lxt2/fbt19990WYHXs2NHau3evn35DEZH8sX//fuv++++3uHAd\nzOknIiLCWr58eb5dc+1EYSCfTJ8+3SoVHGxVczqtj8BKzeWETAHrI7CqOZ1WqeBga8aMGVkeNz09\n3Zo3b551ww03WMWLF7dGjRplnT592se/ndjOE09Y1vPP+7sWUoSdOXPGevHFF63g4OBcQ0CZMmWs\n2NhY69y5cxffn1/XXLtQGMhH+/bts+5p3doCrEpOp9UXrJlgrQdry4X/zgSr74X9gHVP69bWvn37\ncj12cnKyNWLECCsoKMiqVq2aNX/+fCs9Pd0Hv5XYUosWltWtm79rIUVQenq69cUXX1jVq1fPU2tA\nt27drKSkpCyPlZ/X3KJOYcAHduzYYUVHR1sRoaGWw+G45MR2OBxWRGioFR0dbSUkJFz2sX/88Uer\nffv2FmC1atXqio4hIuIPO3futP72t7/lKQTUr1/fWrNmTZ6Om5/X3KJKQwt9LDk5mT179pCamkrx\n4sUJDQ31yixXCxcuZODAgRw4cICBAwcyatQoypYt64Uai4h4V3JyMuPGjWPy5MmcP38+x7LXXHMN\nMTEx9OrVi8DAwCv6rPy45hY1CgNFSEpKCpMnT2bcuHGUK1eOSZMm0bVrVxyOK5mdWySTn36CuDhY\ntw4OHzbbrrsOmjSBvn2henV/1k4KAcuy+PjjjxkyZAhJSUk5lnU4HPTq1Ytx48ZRsWJFH9XQvhQG\niqCff/6ZIUOGMG/ePJo1a8aUKVNssya35JNvvoF77zUzELZsCZUrm+2//QbLl8O+fbBwIdx1l1+r\nKQXX1q1biY6O5ptvvsm1bJMmTZg6dSoNGzb0Qc0EFAaKtP/85z9ER0ezc+dO+vTpw9ixYwnRxDFy\nJRo2hFatYMKErPc/9xysWKHFiuRP/vjjD0aPHs1bb71Fenp6jmUrVarExIkTeeyxxwgI0DQ4vqQw\nUMSdP3+eqVOn8sILLxAUFMT48eN58sknr+jZm9hYiRKweTOEh2e9f9cuM1VxSopv6yUFVnp6Ou+9\n9x7Dhg3j6NGjOZYNDAxkwIABvPDCC5QrV85HNZSMFL2KuGLFijFo0CB2795N+/bt6dWrF7fddhvr\n16/3d9WkMKla1dz5Z2f5cqiW3dIvYjcbNmygadOm9OjRI9cg0KJFC7Zs2cLkyZMVBPxILQM2s3bt\nWvr37098fDzdu3dn/PjxVHY//xXJzgcfQI8e0LkztGlzaZ+BpUvhs89gxgyzhoHY1tGjRxk+fDgz\nZ84kt6+WqlWrEhsby4MPPqhOzgWAwoANpaWlMWPGDIYPH47L5eKll16iX79+OJ1Of1dNCrLly2Hy\nZDOa4ORJs61sWWjaFAYNgtat/Vs/8RuXy0VcXByjRo3ijz/+yLFsUFAQQ4YMYfjw4ZQqVcpHNZTc\nKAzY2LFjxxg5ciTTpk0jMjKSKVOmcJd6g0teuFfPLF7cv/UQv1u9ejX9+/dn69atuZZt164db7zx\nBqGhoT6omVwO9RmwsQoVKvDOO+/www8/UKZMGVq0aEGXLl04ePCgv6smBV3x4goCNpeUlETXrl25\n4447cg0CNWvWZMGCBSxatEhBoIBSy4AApufvhx9+yHPPPcepU6cYNWoUgwYNorgu+JKTMWMuff3C\nC/6ph/hMeno6sbGxvPTSSzkuLQxQokQJhg8fzpAhQwgODvZRDeVKqGVAAAgICKBbt27s2rWLPn36\nMHLkSOrUqcOSJUv8XTUpyA4cuPRHijyHw8GKFStyDQKdO3dm586djBw5UkGgEFDLgGRpx44dDBgw\ngP/85z907NiR1157jZo1a/q7WiJSAKxZs4Y777wzy0mEIiIimDJlCi1btvRDzeRKqWVAshQZGcny\n5cuZN28e8fHx1K5dm9GjR3PmzBl/V01E/OT8+fO89tprtGvXjqCgoEv2lSlThtjYWLZs2aIgUAgp\nDEi2HA4HnTt3JjExkSFDhjBhwgQiIiL4/PPPcx1DLEXErFlmcSL36IGc7NgBjzyS/3USv1ixYgX1\n69dnyJAhFx8pVqlSBeDi68GDB1OsWDE/11SuhB4TSJ7t2bOHQYMGsXDhQlq1asWbb75JRESEv6sl\n+enHHyE6Gr77Dv7+d2jeHG65BUJC4OxZSEqC77+HBQtg714YMQIGD/Z3rcWLMi58FhUVxdSpUy8u\nfPbVV19RpkwZoqKi/FxLuVoKA3LZFi5cyMCBAzlw4AADBw5k1KhRlC1b1t/Vkvy0YQO8+y4sWwYH\nD4JlgcMBQUHw179Cly7wj39AmTL+rql4SUpKCrGxsbz88suULVtWS6IXcQoDckVSUlKYPHky48aN\no1y5crpQ2Mnx43D0KJQsCdddB2oWLnIWLVrEM888o8BvIwoDclUyNiE2a9aMKVOmXGxCFJHCZc+e\nPQwcOJBFixbpUaDNqAOhXJVq1arx6aefsmLFCo4fP07Dhg3p168fx48f93fVRCSPTp8+zciRI4mM\njGTbtm3Mnz+fZcuWKQjYiFoGxGvOnz/P1KlTeeGFFwgKCmL8+PH06NGDgABlzqIiPT0dl8uF0+nU\nv2sRYFkWn332Gc8++yxHjhzhn//8J//85z8pWbKkv6smPqYwIF53+PBhhg0bxtKlS/nll1+0GmIR\nkpSURFxcHH369Lk4rEwKt7p161KjRg1NLGZzCgOSb3755ReqVKlCYGBg9oXefx86doTy5X1XMbli\nmzZtomHDhmzcuJEGDRr4uzqSmxMnzMiP8uUhPR0ytea4XC4OHz5M1apV/VRBKSjUzif55oYbbsg+\nCBw+DMOHw/PPw88/X7pP+VTkymT82/n5ZzPcs2dPOHfuT0EAwOl0KggIoDAg/pCSAr16wbZt8MUX\nULeuuYi5XGa/e3hiFvOei0gOMg7trVYNZs82wbtnT4iPN9v1dyVZUBgQ3zp5EmJiYNMmeOcdaNzY\nbN+6FV59FQYMgNWrzTZ1UBO5PMePw4QJsHixeR0SYv7OzpyB554z2/R3JVnQWSG+NX8+rFoFQ4ZA\n1aqQlma2Hz0Kv/5qnnHefz/cfrtpOQA9NhDJLLu7+xMnTLD++mvPtltugWefNWtHTJrkm/pJoaMw\nIL6TmgqffWaaLx991Gxz36W0agWxsaZZc+dOuOkmmDLF7NOshiKXCggwa0N8/LFZG8L9iK1GDbj7\nbjNl9Hffeco3aWLWmHj1Vfjf//xTZynQFAbEd/77X/j9d7jzTqhUyWxzf9Fblpnn3uWCihVNP4L/\n/Af27fNffUUKovR0GD/e/J3ExED79vDUU7Bli9lfr55pcdu8+dL39e5tOhL+3/+Z12pxkwwUBsR3\nfv3VXIDcK5xlvBg5HOa1e06CtDQzHEqtAiKX+vFH87jtrbdMp8C334YDB6B/f7O/USN4803z5Z9R\nSIhZefLDD31fZynwFAYk/7m/9H/7zYwkiIw0rzO2CrhfHzgAw4bBv/4FbduaZs8r+SyRomrDBti1\nCx57zITnzp3N38yWLTB3rinjHi6Y+e8hKsr0Kzh6VEFbLqEwIPnPfdHZuNH0DQDPM04wzz43b4bu\n3c1yuOvXw5gxMGKE2Z/XoVDuZXVFChvLyvt5fvIk3HwzJCV5tjVvDp06wcsve44Hf/57CA42LQQK\nzZKJwoD4hmWZfgDnzpmLntNpOjK9/DJ06GCaL0+fhg8+gKVLoUsXc+GCvA2FOnsWxo41TaCZL3Qa\nVy0FVcYv7YAAMzTw9Omcy1aoYP53xj4BJUualoLdu00LgcNx6Xnvfm+DBuZ9mvFTMlEYEN9wOMxF\nLCDA/PzxB4waBSNHmgvZ+vXw6afQpg0UL355rQFgLnBbt8Ivv5jPSkmBI0fMPneYUCiQgsZ95/7N\nN+bcj4oyQ2vffdfTepb5Lr9DBxN+v/0WkpM9x7rxRqhfH5YtM68zhmj3e0+cgNat4dix/PudpFBS\nGBDfadPGzDwI5s5k0iQTBr75Bv72NzM5yvnzZn9eJ0ZxX+RWrjSjER5+2Lx+6y1zp3T33Wb9g8s5\npkh+ydxqdeiQ6ejXpYsZBTBlinkEMGKEZ/KtjE39aWkmPHfqZM55dxmAcuXMkMJq1bL/3PLl4cEH\n4S9/8e7vJYWero7iO6Gh4F4f3bKgdGl46SVzt/LEE2aYVEiICQcZuScmys7Ro+b56fXXQ82a5tgh\nIfDII3DXXeZRROvWZjSDiD85HCbw/vSTeX3mjOkk++WXJhy3amWC7PHjcOpU1u8HM3KgTBkz26B7\nbY/t201QuOmm7N8XEWFaHkQy0aqF4j+WZb7oMy5xvHSpmaI4JMS8PnsWSpTI2/GOH/e8L6MDB8wF\nsHt3M/GKXDGtWniVfv/dtIalpMDMmWbb4cNw3XWeMp9/bibfmjLl0rv8zB1k166FwYPN47Dq1c2j\ntj59zBwExYv75NeRokMtA+I/DocnCLifj/7tb54v9EOHoFQpWLIk5+O4+wK432dZnmbRc+fMs9Qb\nb/QcR/lX/OWaa8zQ2tOnPQsHuYPAnj0QHm5atA4cgKZNIS7O9K8BTxBwtwTcfjssWGBCQ/PmZsjh\n5MkKAnJFFAakYMjYOgCmM+Azz5ihhnXr5vzezH0BMt5BBQWZRwgrV5pHBpC34Yfp6QoN4l3u8+nO\nO81/58y5dH9wsLmz37nTdALs3x+mTfPMHXDmjGlVePxxT9+aa6+Fe+81Q3EjI815q46ycgUUBqRg\nKl4cbrvNrGVw/fV5f196uicc/PKLGW7YurV5VtqvX9bvcV+kU1PNhTg11RxDcxZc1LRpUxwOBw0b\nNgSgYcOGNG3a1M+1KmTc51NkpLmTzzwTZ9WqMGiQ6UNQqRL885/mMdrZs6ZMyZLmp3x502qWmfvc\nV0dZuQLO3IuI+EF4uPnJi4wBwOUyK7Z99pnpf1Clilkh8d57zSOH7CYm2rbNrPmekgJ790LXrjBx\nIpQt673fSYqOjOecW14mvXKXyRhMs3tPfLwZHXD99Z4ygwZl34dGIUCugsKAFB0vv2x6ZVuWCRIz\nZ5opjSHrGdnS0iAwEBYtMu91Ok1P7nPnPFMiP/OM738PKbjcX+buL974ePNMv2lTzyRZOcl4/mUV\nHg4dMn1fVqwwYbRjR/Pj5g4C7nNXxEsUBqTwCwgwvbTHjDHPUsePN+u3Z1z0KKsLp3vb5MmmBWHy\nZE/v7QYNTI/uvn1Nv4Pz500HL/fQSLEn95f33LnmfDtzxgzxK1/eDI296668f1FnDgI//QRDh5qW\nqf37TZ+BYcOybglQEBAvU7uSFA3XXGOe9c+cCa+9BpUrw/PPm5nWsrpwukcv/Pvf5iLcufOlw7jC\nwsydnnsWw7VrTRPtrFnm9ZEjpj/CiRP5+mtJARAfb6bOBnM3P2KEmR+jd28z8+Wbb5qOfBMnmjJX\n+kVdvTrcc485b3//3Zxf7kdbIvlMYUCKBveXe/fuZtz2e++ZZV4fecQzFCs52QzZAk+rwZw5ZgrX\nJk08xzp71gSE06c9q7/Fx5vAcccd5nX58mb2t8wTJEnR88QTJjSCuZtv0wZiY004DAmBli3NBFph\nYVf+xe1+X48eZoZAMOe0Ft8SH1EYkKIh83wFHTqYRVvmzDGtBGAWQerUyXQsBDPk8Ngx07+genXP\nsQ4fNh0QH3nEvN64EVatMhf70FCzLSgIEhI8C77o7q1oOnrU/JtnPD+aN4d27TyvP/nELA5Uu7Yp\nD5eeD3k5NzL3JQBzTisIiI8oDEjRkjEUWBZUrOiZhKVKFTNkq35987piRXPxrljR8/6zZ81d4PHj\nntkKQ0NN822HDp5y27ebOeTdK8zpol00XXutmdnPPSV2xlEESUmmlaBfP6hVC6ZONUFh48ZLz4fL\nPTd0LokfKAxI0ZTVXdV995lZCN0tBQ6HGba1b5+nzFdfmX4H0dHmeW1amlkApk8faNTIUy41FX77\nDYoVM6/VMlD0uP9N69b1rASYUZUq8MILpsPfvHnw3/+atTGGDzf73a1Us2fDF1/4ps4iV0hhQOwj\n84JHxYqZoYOffmpWO3zmGfjHP8xkRyNGmDIBAVl/0W/ebBY+atnSvNbdXNHjXgr75ptNH5IzZ/48\nlj8qyoRFMH1KGjc2j6fS0z2tVKNHm3MMNDugFFgKA2IfWfXybtvW9AdwOk2T/5tvmubecuU8nbey\n+qL/1788q7+pVaDoCg4261ocPQrr1plt2X2hJyWZ+QGeeMKEhnPnzPa+fT1BVBMDSQGleQbE3izL\nTA/70Ud/nlUuu7v9pUvNUMPY2JzLSdHQtq0ZmbJ0qWkJcp8j6elm7onTp+G778yEVVWqmNYlMJ1M\nwXQ+zDhaRaQAUhgQe3M4PHd6Od21uVsJtmwxsxV27mweJ0jRV7s2tGpl7voXLoT27c3248dNQIiL\nM3f+0dFZr3/RpYtv6ytyBRQGRPLSdOtwmGbfCRNM+Vdfzf96ScHx5JNm4qHBg01LQWCgGYXSoYNZ\nhTDjypqaKlgKIT3AEsmJuz/Avn3w1FNm0qLYWDNbofoK2Ef16maGweBgM03wd995truDgHv0gIKA\nFEIKAyI5cTjMnd4XX5gJht5/36xb4N4n9mBZZpbBTz4xQ05fesnMaJmRUw2tUnjp7BXJTWCgWdI4\nJMQzr0AWXC4XTn0hFHrp6ekEZH505A5+ERHmEdGKFWbxKpEiQi0DInlRuXK2QcCyLJKSkmjUqBEr\nV670ccXEmzZt2kSzZs3YuHEjaZnnpQDPo6GWLc28AiJFhMKAyFVyOBykp6dTsmRJ7r77brp06cLB\ngwf9XS25DMeOHaNPnz40atSIU6dOUaJECQKzevavR0NSRCkMiHhB1apVWbNmDbNnz2bVqlWEh4cz\nfvx4UlNT/V01yUFaWhpxcXGEhYUxd+5cXn/9deLj46ldu7a/qybiUwoDIl4SEBBAt27d2LVrF336\n9GHUqFHccsstLF682N9VkyysXbuWxo0b07dvX+677z52797NgAED1O9DbElhQMTLypUrR2xsLFu2\nbKFatWrce++9dOzYkb179/q7agIcPnyYxx9/nKioKAICAli3bh2zZs2isnsBKxEbUhgQySeRkZEs\nX76cefPmsXnzZiIjIxk9ejRnzpzxd9Vs6fz580yePJmwsDAWLVrEu+++y3fffUcTTRUsojAgkp8c\nDgedO3cmMTGRIUOGMGHCBCIiIpg/fz5WhkmL1q1bR7pWtMs3K1asoF69egwdOpRu3bqxe/duevbs\nmXUnQREbUhgQ8YFSpUoxbtw4duzYQd26dencuTNt2rQhMTGRTZs2ERUVRVRUFBs3bvR3VYuUn3/+\nmQcffJBWrVoREhLCxo0bmTp1KiEhIf6umkiBojAg4kOhoaEsWLCABQsWsH//furUqUP79u2xLIv1\n69fTuHFjevfuzf/+9z9/V7VQS0lJISYmhlq1arFmzRo++OADVq9eTf369f1dNZECSWFAxA/at2/P\n9u3buf/++zl06NDF7ZZl8e677xIWFsbbb7+d9cQ3kqOFCxcSGRnJiy++SL9+/di1axf/+Mc/cGiO\nAJFsKQyI+ElqaiqrV6/Oct/vv/9Ov379aNSoEd9++62Pa1Y47dmzh/bt29OhQwdq1qzJ1q1bmTRp\nEmXLlvV31UQKPIUBET85cOAAJUqUyLHM5s2badasGd26dbukBUE8Tp8+zYgRI4iMjGTbtm3Mnz+f\nZcuWERER4e+qiRQaCgMiflK3bl0SEhIYM2YMwcHBOZb94IMPCA8PJzY2lvNaIAcwj1TmzZtHrVq1\niI2NZdiwYSQmJtKpUyc9EhC5TAoDIn5UokQJRo8eTWJiIvfff3+OZU+dOsWQIUOoV68ey5cv91EN\nC6YdO3bQsmVLHnroIRo0aHAxVJUsWdLfVRMplBQGRAqA6tWr8/nnn7N06VLCw8NzLJuYmEjr1q3p\n3LkzBw4c8FENC4YTJ04wePBg6tWrx8GDB1m8eDFffvklNWvW9HfVRAo1hQGRAqRNmzZs3bqViRMn\nUrp06RzLzp8/n4iICMaNG0dKSoqPaugf6enpzJ49m/DwcKZNm8a4cePYtm0bbdu29XfVRIoEhQGR\nAiYoKIihQ4eya9cuunbtmmPZs2fPMmrUKCIjI1mwYMElsxoWFZs2baJZs2Y88cQTtGjRgl27djFs\n2DCKFy/u76qJFBkKAyIFVJUqVfjwww/55ptvqFu3bo5l9+3bR8eOHWnfvj0//vijj2qYv44dO0af\nPn1o1KgRp06dYuXKlcydO5eqVav6u2oiRY7CgEgB17x584vT6JYvXz7HsosXL+aWW25h+PDhnD59\n2kc19K60tDTi4uIICwtj7ty5vP7668THx3PXXXf5u2oiRZbCgEgh4HQ66dev38UFdnIaOnfu3DnG\njx9PrVq1+OSTTwrVo4O1a9fSuHFj+vbty3333cfu3bsZMGAATqfT31UTKdIUBkQKkWuvvfbi0rt/\n/etfcyx78OBBunTpwt1338327dt9VMMrc/jwYR5//HGioqIICAhg3bp1zJo1i8qVK/u7aiK2oDAg\nUgg1btz44hfmtddem2PZVatWUb9+fQYNGsSJEyd8VMO8OX/+PJMnTyYsLIxFixZdDDpNmjTxd9VE\nbEVhQKSQCggIoHv37heb0gMDA7Mtm5aWxuuvv05YWBjvvfce6enpV/35V7uI0ooVK6hXrx5Dhw6l\nW7duFx+B5PR7iEj+UBgQKeTKly/PG2+8QXx8PHfeeWeOZY8cOUL37t2Jiopi48aNuR47ISGBAQMG\nsD0+/k/7NmzYQERoKAMGDCAhISHP9f3555958MEHadWqFSEhIRc7R4aEhOT5GCLiXQ6rMPUuEpEc\nWZbFJ598wrPPPktSUlKOZR0OBz179iQmJoaKFStesm///v083bs3X339NZWcTh5wuWgM1AZKAmeA\nBGADMN/p5IjLxT2tW/P2tGnUqFEjy89LSUkhNjaWmJgYypUrx6RJk+jatavWERApCCwRKXJOnTpl\nDX2vIvMAAAY6SURBVBs2zCpWrJgF5PhzzTXXWG+99Zblcrksy7Ks6dOnW6WCg60bnU7rI7BSwbJy\n+EkF6yOwqjmdVqngYGv69Ol/qs+CBQusmjVrWk6n0xoyZIh14sQJX/9fIiI5UMuASBG2e/dunnnm\nGb766qtcy9avX5/GjRszffp0ngImA2Uu47NOAYOBGcC4ceMYMWIEe/bsYeDAgSxatIhWrVrx5ptv\namlhkQJIYUCkiLMsiwULFjBw4ED279+fa/mxwMir+LyxwGigXbt2LF++nOuuu47XXnuN+++/X48E\nRAoohQERmzh79iyTJk1i/PjxWS5sFAB0x9zZXw0L6Am8BzwdHc0rr7yipYVFCjiNJhCxiRIlSjB6\n9GgSExPp1KnTJfsCgL8Ar3nhcxyYRwzXBwby486dCgIihYDCgIjNVK9enfnz57N06VLCw8MBSAcm\n4ukjsA1zcViY4X2bLmxrlOl4bYGmmbaVBcanpfHV11+TmJjo5d9ARLxNYUDEptq0acPWrVuJiooi\nBOicYd8tQHngmwzbVmMuGFuA5AvbLGAdkNXsBg8AlZxO3nnnHa/XXUS8S2FAxMaCgoI4dvgwDwNB\nGbY7gChMAHBbDdx/Yd/aC9s2AyeBZlkcuzjwgMvF8iVLvF5vEfEuhQERGzt16hS79u2jcRb7mmMe\nDZy98HoN0A6ohyckuFsLsgoDYB4p7Ny7l+Tk5GxKiEhBoDAgYmN79+7FsixqZ7GvOXAe8xhgN3D0\nwrY78ISBNZhZCctnc/xIzNDGPXv2eLXeIuJdCgMiNpaamgqYKYYzawQEY/oNrAYqAaGYQPA9cO7C\n9uY5HL9Eps8RkYLJ6e8KiIj/FC9eHDBrDWRWDPgrJgxUw/Ol3xxIBT4CfsO0FGTH/YjB/TkiUjCp\nZUDExkJDQ3E4HGS35mBz4DtgFZ4wUAGoBUzAdCbMqWVgB2ZBpNDQUO9UWETyhcKAiI2VLl2a8Jo1\n2ZDN/uaYu/tfuPRL/w5MP4LqQJUcjv8DUOummyhdurQXaisi+UVhQMTmWrdrx3ynk3NZ7LsdCMRM\nIlQvw/bmmFaBnB4RpGKWN27Vtq3X6ioi+UNrE4jYXEJCApGRkXwEPOrF484Bul44vlYqFCnYFAZE\nhLZt2pC4ciXbXK7LWrY4OyeBOk4ntVu0YMmyZV44oojkJ4UBEWH//v3UqV2bR1JSmH6Vx7KAXsDc\n4GC2JSRQo0YNL9RQRPKT+gyICDVq1OD1KVOYAYy7iuNYF94/A3hj6lQFAZFCQvMMiAgATz31FL/9\n9hsjR47kAGYZ4st5ZHASeBYTBGJiYujRo0d+VFNE8oEeE4jIJWbMmMHA6GgquFyMd7nozKWLGGWW\nCswHnnc6OeZ08sbUqQoCIoWMwoCI/Mn+/ft5undvvvr6ayo5nTzgctEIs9ZACczcAzsw8wjMdzo5\n4nJxT+vWvD1tmh4NiBRCCgMikq2EhATi4uJYvmQJOy8sauTmcDioddNNtGrblr59+2r4oEghpjAg\nInmSnJzMnj17SE1NpXjx4oSGhmpmQZEiQmFARETE5jS0UERExOYUBkRERGxOYUBERMTmFAZERERs\nTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGREREbE5hQERE\nxOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTmFAZE\nRERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGREREbE5h\nQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTm\nFAZERERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGRERE\nbE5hQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBE\nRMTmFAZERERsTmFARETE5hQGREREbE5hQERExOYUBkRERGxOYUBERMTmFAZERERsTmFARETE5hQG\nREREbO7/AWPkJcI5fTQLAAAAAElFTkSuQmCC\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x10b64cb00>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# 描画(edgeに付いている数字は(capacity, 'flow')の意味)\n",
"\n",
"pos={'s':(0,2),'v':(3,4),'w':(3,0),'t':(6,2)}\n",
"edge_labels = {(i, j): (w['capacity'], str((w['flow'])) ) for i, j, w in T.edges(data=True)}\n",
"nx.draw_networkx_edge_labels(T, pos, edge_labels=edge_labels, font_color='r')\n",
"nx.draw_networkx_labels(T, pos)\n",
"nx.draw(T, pos)\n",
"plt.axis('off')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"## NetworkXを用いて最大流問題を解く"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"NetworkXには、各種ネットワーク問題を解くための機能が揃っている。ここでは最大流問題を解いてみる。\n",
"\n",
"* [NetworkXのmaximum flow algorithmの仕様](https://networkx.github.io/documentation/development/_modules/networkx/algorithms/flow/maxflow.html)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# 例のグラフGを生成\n",
"G = nx.DiGraph()\n",
"G.add_edges_from([('s','v',{'capacity': 3}),\n",
" ('s','w',{'capacity': 2}),\n",
" ('v','w',{'capacity': 5}),\n",
" ('v','t',{'capacity': 2}),\n",
" ('w','t',{'capacity': 3})])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false,
"scrolled": true
},
"outputs": [],
"source": [
"flow_value, flows = nx.maximum_flow(G,'s','t')\n",
"print('maximum flow: {}'.format(flow_value))\n",
"#print(flows)\n",
"\n",
"caps = nx.get_edge_attributes(G, 'capacity')\n",
"for u in nx.topological_sort(G):\n",
" for v, flow in sorted(flows[u].items()):\n",
" print('({}, {}): {}/{}'.format(u, v, flow, caps[(u, v)]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Summary"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"最後に、今回作った関数をまとめておく。"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"code_folding": [
5,
97,
135,
155
],
"collapsed": true
},
"outputs": [],
"source": [
"import networkx as nx\n",
"import matplotlib.pyplot as plt\n",
"from collections import deque\n",
"import numpy as np\n",
"\n",
"def bfsFlowPath(G, s, e):\n",
" '''\n",
" Search a path from s to t all of whose points have strictly positive capacity.\n",
" \n",
" Inputs:\n",
" G: a graph\n",
" s: a start point\n",
" e: an end point\n",
" each edge has two attributes:\n",
" capacity: capacity\n",
" flow: its current flow which should be no more than its capacity\n",
" Output:\n",
" path: a list of edges which represents a path from s to e.\n",
" At each edge of the path, its current flow is strictly less than its capacity.\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
"\n",
" # 過去に訪れた点を記録\n",
" # sは最初から入れておく\n",
" past = [s]\n",
" # pathを記録するためのリスト\n",
" path = []\n",
"\n",
" # 全ての点のsからの距離の初期値を無限大に\n",
" for p in G.nodes():\n",
" G.node[p]['dist'] = float('inf')\n",
" \n",
" # node s の距離を0に\n",
" G.node[s]['dist'] = 0\n",
" \n",
" # sに隣接する点をqueueに\n",
" # queueには、今後訪れるべき点が格納される\n",
" queue = deque()\n",
" for p in G.successors(s):\n",
" # current flow < capacity となるedgeだけをpathの候補に\n",
" # flow < capacity となるedge以外は存在しないものとして扱うのと同じ\n",
" if G[s][p]['flow'] < G[s][p]['capacity']:\n",
" queue.append(p)\n",
" \n",
" # あとで条件分岐に用いる\n",
" numberOfSuccessorsOfSource = len(queue)\n",
" \n",
" # sに隣接する点の距離を1に\n",
" for p in queue:\n",
" G.node[p]['dist'] = 1\n",
"\n",
" # BFSを用いてflow < capacityを満たすsからeへのpathがあるのか調べる\n",
" # pastに過去に訪れた点を格納\n",
" while len(queue)>0:\n",
" v = queue.popleft()\n",
" if v == e: break\n",
" else:\n",
" past.append(v)\n",
" for p in G.successors(v):\n",
" # (過去に訪れていない and flow < capacity)を満たすedge\n",
" if ( (not p in past) and ( G[v][p]['flow'] < G[v][p]['capacity']) ):\n",
" if ( not p in queue):\n",
" queue.append(p)\n",
" if G.node[p]['dist'] > G.node[v]['dist'] + 1:\n",
" G.node[p]['dist'] = G.node[v]['dist'] + 1\n",
"\n",
" # sからeへのpathが存在しない場合はNoneを返す\n",
" if numberOfSuccessorsOfSource == 0:\n",
" v = s\n",
" if v != e or v == s:\n",
" # print ('There is no path.')\n",
" return None\n",
" \n",
" # 以下、sからeへのpathが存在する場合\n",
" # 終点から遡ってpathを形成する\n",
" pp = e\n",
" while (1):\n",
" if pp == s: break\n",
" \n",
" pred = G.predecessors(pp)\n",
" count = 0\n",
"\n",
" for p in pred:\n",
" # ここに、flow < capacity の条件を追加\n",
" if ( G.node[p]['dist'] == G.node[pp]['dist']-1 and G[p][pp]['flow'] < G[p][pp]['capacity']):\n",
" path.insert(0, (p,pp))\n",
" pp = p\n",
" break\n",
" else:\n",
" count += 1\n",
" \n",
" # 条件を満たすedgeがない\n",
" if count == len(pred):\n",
" break\n",
"\n",
" return path\n",
"\n",
"def naiveGreedy(G, s, t):\n",
" '''\n",
" Inputs:\n",
" G: a graph\n",
" s: a source vertex\n",
" t: a sink vertex\n",
" Outputs:\n",
" the graph G whose flow was modified by this naive greedy algorithm\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
" # initialize flows\n",
" for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0\n",
" \n",
" # そもそもsからtへのパスがあるのか確認\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" print (\"There is no path from \" + str(s) + \" to \"+ str(t) )\n",
" return None\n",
" \n",
" # sからtへのパスがある場合(lecture noteのA Naive Greedy Algorithmの部分に相当)\n",
" while(1):\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" break\n",
" else:\n",
" # path上のedgeについて、capacity - flowの最小値を調べる\n",
" min = float('inf')\n",
" for edge in path:\n",
" if ( min > G[edge[0]][edge[1]]['capacity'] - G[edge[0]][edge[1]]['flow'] ):\n",
" min = G[edge[0]][edge[1]]['capacity'] - G[edge[0]][edge[1]]['flow']\n",
" \n",
" # path上のedgeのflowを更新\n",
" for edge in path:\n",
" G[edge[0]][edge[1]]['flow'] += min\n",
" \n",
" return G\n",
"\n",
"def makeResidualGraph(G):\n",
" '''\n",
" Input: a graph G\n",
" Output: its residual graph Gf\n",
" '''\n",
" Gf = G.copy()\n",
" edgeList = G.edges()\n",
" \n",
" for edge in edgeList:\n",
" # Initialize flow\n",
" Gf[edge[0]][edge[1]]['flow'] = 0\n",
" \n",
" # 逆向きのedgeがないものは追加\n",
" if not (edge[1], edge[0]) in edgeList:\n",
" Gf.add_edge(edge[1],edge[0])\n",
" Gf[edge[1]][edge[0]]['capacity'] = Gf[edge[0]][edge[1]]['flow']\n",
" Gf[edge[1]][edge[0]]['flow'] = 0\n",
" \n",
" return Gf\n",
"\n",
"def fordFulkerson(G, s, t):\n",
" '''\n",
" Inputs:\n",
" G: a graph\n",
" s: a source vertex\n",
" t: a sink vertex\n",
" Outputs:\n",
" the graph G whose flow was modified by Ford-Fulkerson algorithm\n",
" In case there is no path from s to t, return None.\n",
" '''\n",
"\n",
" # initialize flows\n",
" for e in G.edges():\n",
" G[e[0]][e[1]]['flow'] = 0\n",
"\n",
" # Forward edgesを記録\n",
" forwardEdges = G.edges()\n",
" \n",
" # Residual Graphの作成\n",
" Gf = makeResidualGraph(G)\n",
" \n",
" # そもそもGにおいてsからtへのパスがあるのか確認\n",
" path = bfsFlowPath(G, s, t)\n",
" if path == None:\n",
" print (\"There is no path from \" + str(s) + \" to \"+ str(t) )\n",
" return None\n",
" \n",
" # Gにおいてsからtへのパスがある場合\n",
" while(1):\n",
" # これ以上パスがみつからない場合は最適なのでそこでループを打ち切る\n",
" path = bfsFlowPath(Gf, s, t)\n",
" if path == None:\n",
" break\n",
"\n",
" # まだパスがある（最適でない）場合\n",
" else:\n",
" # path上のedgeについて、capacity - flowの最小値を調べる\n",
" diff = float('inf')\n",
" for edge in path:\n",
" diff = np.min([diff, Gf[edge[0]][edge[1]]['capacity'] - Gf[edge[0]][edge[1]]['flow'] ])\n",
" \n",
" # path上のedgeのflowを更新\n",
" for edge in path:\n",
" if edge in forwardEdges:\n",
" Gf[edge[0]][edge[1]]['flow'] += diff\n",
" # このとき、backward edgeのcapacityを更新する必要あり？\n",
" Gf[edge[1]][edge[0]]['capacity'] += diff\n",
" else:\n",
" Gf[edge[0]][edge[1]]['flow'] -= diff\n",
" Gf[edge[1]][edge[0]]['capacity'] -= diff\n",
" \n",
" # もともと無かったedgeを消去\n",
" for edge in Gf.edges():\n",
" if not edge in forwardEdges:\n",
" Gf.remove_edge(edge[0],edge[1])\n",
" \n",
" return Gf"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python [default]",
"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.5.2"
},
"toc": {
"nav_menu": {
"height": "138px",
"width": "252px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_number_sections": true,
"toc_section_display": "block",
"toc_threshold": 6,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 1
}