shortest_path.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shortest Path\n",
    "\n",
    "The following code solves the shortest path problem as a linear program. Obviously this is a very inefficient way to solve the shortest path. But the following code demonstrates how can use tuplelist and dictionaries in python + gurobi.\n",
    "\n",
    "The code uses the following input file: [AhujaNet.txt](https://github.com/avinashu1980/Intro_Python_Gurobi/blob/master/AhujaNet.txt). Make sure the input file is in the same folder as the notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from gurobipy import *\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following lines are for reading the input file and intializing the parameters. Note that links is a tuplelist. For more on tuplelists, refer to gurobi quick start guide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "f = open(\"AhujaNet.txt\", \"r\")\n",
    "line = f.readline()\n",
    "line = line.strip('\\n')\n",
    "data = line.split(':')\n",
    "num_nodes = int(data[1])\n",
    "line = f.readline()\n",
    "line = line.strip('\\n')\n",
    "data = line.split(':')\n",
    "num_arcs = int(data[1])\n",
    "line = f.readline()\n",
    "line = line.strip('\\n')\n",
    "data = line.split(':')\n",
    "origin = int(data[1])\n",
    "line = f.readline()\n",
    "line = line.strip('\\n')\n",
    "data = line.split(':')\n",
    "destination = int(data[1])\n",
    "line = f.readline()\n",
    "line = f.readline()\n",
    "\n",
    "links = tuplelist()\n",
    "cost  = {}\n",
    "while(len(line)):\n",
    "    line = line.strip('\\n')\n",
    "    data = line.split()\n",
    "    from_node = int(data[0])\n",
    "    to_node = int(data[1])\n",
    "    cost_arc = float(data[2])\n",
    "    links.append((from_node,to_node))\n",
    "    cost[from_node, to_node] = cost_arc\n",
    "    line = f.readline()\n",
    "f.close() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the variable addition step has become very compact compared to previous examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "m = Model('SP')\n",
    "x = m.addVars(links, obj=cost, name =\"flow\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same with the constraints. The following is the flow balance constraint which ensures the path structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimize a model with 6 rows, 9 columns and 18 nonzeros\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 4e+00]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve removed 3 rows and 3 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 3 rows, 6 columns, 12 nonzeros\n",
      "\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    6.0000000e+00   0.000000e+00   0.000000e+00      0s\n",
      "       0    6.0000000e+00   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 0 iterations and 0.01 seconds\n",
      "Optimal objective  6.000000000e+00\n"
     ]
    }
   ],
   "source": [
    "for i in range(1, num_nodes+1):\n",
    "    m.addConstr( sum(x[i,j] for i,j in links.select(i, '*')) - sum(x[j,i] for j,i in links.select('*',i)) == \n",
    "                     (1 if i==origin else -1 if i==destination else 0 ),'node%s_' % i )\n",
    "\n",
    "m.optimize() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The optimal solution is printed if found."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The final solution is:\n",
      "1 2 1.0\n",
      "2 5 1.0\n",
      "5 6 1.0\n"
     ]
    }
   ],
   "source": [
    "if m.status == GRB.Status.OPTIMAL:\n",
    "   print('The final solution is:')\n",
    "   for i,j in links:\n",
    "       if(x[i,j].x > 0):\n",
    "           print(i, j, x[i,j].x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following set of code is used to visualize the final solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAFkCAYAAAC9wjgoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzs3Xl8U1X6x/HPSVKKLRTBBUUYFtkEWaQ4AsrOgKDCuKC4\nIIKgMiiIihsqoiwjo+ICIiiL6PgbXNGRRQFBBEQtiGwiOFJwcFhlqWCXJM/vj9uUtqRN0mbP8369\nzlCTm3PP7Zyk35x77rlGRFBKKaVU4rJFugFKKaWUiiwNA0oppVSC0zCglFJKJTgNA0oppVSC0zCg\nlFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC\n0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0op\npVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgN\nA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJK\nJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCg\nlFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC0zCglFJKJTgNA0oppVSC\n0zCglFJKJThHpBugVDgZY6oCzYAqgAF+B7aIyL6INkzFHe1rKpZoGFBxzRhjgMuAwRWgM1DL23YV\njNnrhFUCM4HPRMQdznaq2Fekr1WoUHJfq1Bhr9PpXCUi2tdU1DAiEuk2KBV0+R/M1zlgrBMuqAfO\nPuBIB1oCZ2B9VTsCbATWAQvAuRkcDtjthPHA6/pBrXwp6GsOx1in03lBvXr1nH369HGkp6fTsmVL\nzjjjDIwxHDlyhI0bN7Ju3ToWLFjg3Lx5s8PhcOx2Op3a11TEaRhQcccYc7YNprnhmsvBfR/YuuJ7\ngowAa4EXQeaBscMXLhgoIjtD32oVi4wxZ9tstmlut/uayy+/3H3ffffZunbtis1Wem8TEdauXcuL\nL74o8+bNM3a7/QuXy6V9TUWMhgEVV4wxFzlgSWU4fTrY+5axnqXAbeDcC7ku6C0iy4LYzGhQFbgG\nuByojjVQEmwCHAI+B94F9oZgHxFjjLnI4XAsqVy58unTp0+39+1btt62dOlSbrvtNufevXtzXS5X\nPPY1FQM0DKi4YYxpZYcvWsBpi8B+djnrOwb0BfdScLuhl4gsCUY7o0AdYBVQA3AD9hDuy40VNI4B\nnYANIdxX2BhjWtnt9i9atGhx2qJFi+xnn12+3nbs2DH69u3rXrp0qdvtdsdTX1MxQsOAigvGmHMd\nsLk5VFkO9rQg1ZsL9AH3Z5DrhlYi8kOQqo6kDKAF4Z1A7AL2AzWxAkLMMsac63A4Njdv3rzK8uXL\n7Wlpweltubm59OnTx/3ZZ5/lut3ueOlrKkZoGFAxzxhjbPBRVej5AzjOCnL9J4CW4NwJ3zuhjYg4\ng7yLcKoH/CeC++8AfBnB/ZeLMcbYbLaPqlat2vOHH35wnHVWcHvbiRMnaNmypXPnzp3fO53OWO9r\nKobookMqHtzohqteC0EQAEgB5oLDBa2A+0Kwi3BKj+C+3UDrCO4/GG50u91Xvfbaa0EPAgApKSnM\nnTvX4XK54qGvqRiiYUDFNGOMzQHj+oBc7WPbDOBu4EKgElAbuAHY4cd+2gDDrCsMRhtjTitXoyMr\nkm13Y2WrmGSMsTkcjnF9+vSRq6/21duKGj9+PDabjebNm/vctk2bNgwbNszY7fZY72sqhmgYULGu\nqxPq3u/HbPhngA+BbsBLwJ3ASqyv+1v92NG9gAvSsDKESjxdnU5n3fvvvz+gKy/27NnDxIkTqVSp\nkt+vuffee3G5XNrXVNhoGFAxzcCdTcB5mR/b3g/sAl4ABgGPYp28dgJ/9+P15wPdwe2AoWVtb6z4\n+9//js1m4777Sh+pXrFiBenp6VSsWJGGDRvyxhtvhKmF4WeMubNJkybOyy7zp7eddP/999O2bVvS\n0/0/Q3P++efTvXt3t8PhiPu+pqKDhgEVs4wxxg6drwGHP1/V2nDq9Pn6QFPA32nb14DNBa3jefj2\n22+/ZcaMGbRo0aLU7TIzM7nyyivp2rUr33//PSNGjGDw4MEsWRJ/V8UZY4zdbu98zTXXOKwFB/2z\ncuVKPvjgA1544YWA93nNNdfYXC5XXPc1FT303gQqlp3nhGrlnRG3D2segT/SAbFCdHPg63LuOur8\n/vvv3HLLLbz++us8/fTTpW47bdo06tWrx6RJkwBo1KgRq1atYvLkyfzlL38JR3OLMMZkhbJ6p9OZ\nGsi3e7fbzfDhwxkyZAhNmzYNeIfp6emISNz2NRVddGRAxbIWABeVo4K3gD1APz+3bwbYrJX1WpZj\nt1Fr2LBhXHXVVXTp0sXntmvXrqVbt25FHuvRowdfffVVqJrnS6UQllSAiy7yv7dNmzaN3bt3+wxV\nJWnWrBk2my1u+5qKLjoyoGLZ6QBlvcBrG9bVBZcCt/r5mmQgFSQLOob4m2hIzJo1q83AgQO9Pvev\nf/2LDRs2kJGR4Vdde/fupXr16kUeq169OseOHSMnJ4fk5OQiz7ndbrNkyZLml19++U1la33k+Xs5\n4W+//caYMWN44oknqFatWpn2lZycTGpqqisrK6tKmSpQKgAaBlQsMwX/E6B9wBVYC/S/G2AdNmtE\n7cb8ElOWL1+OtzDw3//+l3vvvZelS5eSlJQUkn27XC77ypUrrweuD8kOwsDf+QKjR4/mjDPO4O67\n7y7X/vJveKQjuCrkNAyoWHYcrEXvA5lhdQzr7jzHsBboPyeA17qAE9ZpgrnAZwG8NCp07tz5Mrxc\nDbFu3ToOHDhAq1at8KxK6nK5WLlyJVOmTCEnJ+eUP4TnnHMO+/btK/LYvn37SEtLO2VUAMBut7s6\ndOjw/oQJEz4K4iEV9s8Q1Vvg2LFjnHZa6b3tp59+4rXXXuPFF19kz549gHWXwuzsbPLy8ti1axdp\naWlUrVq11HpcLhcnTpywkd/PlQolDQMqlm0F2IR12z1/5ABXAj8By4BGAe5wO5BnDSTMFZHPA3x5\nNHDgJQx069aNTZs2FXnstttu44ILLuDhhx/2+o24bdu2LFq0qMhjn332GW3btvW6Y5vNJj169Ngo\nIm+Xo/0lMsZMD0W9nuqB1E2bNp1yaqS4PXv2ICIMHz6ce+6555Tn69Wrx4gRI3j++edLrWf79u3k\n5eXZgC3laLdSftEwoGLZDjucWAcp3XxvixtrfPpr4GPgz2XY4bqTP64vw8ujVmpqKk2aNDnlsTPO\nOIMLLrgAgEcffZQ9e/YUrCVw1113MXXqVB566CEGDRrEsmXLeO+991i4cGHY2w8gIpVDVbcxxma3\n27PWrVuXUnzSZHEXXnghH3744SmPjx49mt9//52XXnqJevXq+dznunUFvS2u+pqKThoGVMwSEbfD\nmK8/hY4P+XFe9T7g30Bv4CCnjinf7Mc+lwBJ8J9ckSMBNzjGFB8N+N///scvv/xS8N916tRhwYIF\njBw5kpdeeomaNWsyc+bMU64wiAci4nY4HF9/+umnHR966KFS+9oZZ5xB7969T3l88uTJGGO46qqr\n/NrnkiVLSEpK+k9ubm7c9zUVeXrXQhXTjDG3AG9uw/eQf2es5YdL4vLx+kNADXDnwmgR8WfRwmh0\nKxCpZQKdwJPA+Ajtv1wK+tq2bTRqFOgJJujcuTO//fYb33//vc9tDx06RI0aNdy5ubmx3NdUDNFZ\nqirWveeAI1P92HA51h/8koovMwGndbZhVhnbqmLbew6H48jUqf70tlMtX77cryAAMHPmTJxOp/Y1\nFTYaBlRME5FsJzz3Csh3IdzPbmAsuARmisj+EO4q1HIjuG8T4f2Xi4hkO53O51555RX57rvQ9bbd\nu3czduxYl4jEel9TMUTDgIoHk9Lg4G2E5i+NAIOs0wMHBB4KwS7CyZ87NoeKHeuCjFg2yRiztX//\n/s7c3OD3NhFh0KBB7tzc3AMiEut9TcUQDQMq5k2FRxfBWVuBO7DG8YPpMWAZ2JwwUESOBrn6cFsP\n/Jfg/5p8EeAEMbg2Q2Eikut0Ovtv3brVDBkyRNzu4P4aH3vsMZYtW2ZzOp3x0NdUDNEwoGLaK8Y8\neTuMuQRrFaC5wBCsmWrlJVhBYIL1nw+IyOIgVBtpAtwG5BGcX5M/PPu5HfgjTPsMGRH5TkT6z507\nl8GDB4vTWf5fo4jw2GOPMWHCBICNcdLXVAzRqwlUzPIEgcJr3b2F9ZfuEqyZV4HP+bbswRplyL9i\nfpSIPFvmhkandOAurDWYqlG2VZ39cQxYDLwOrAjRPiLCGHOLMeaNSy65RObMmWMvyxUGYC1SNGTI\nEPeiRYtsWNNT/gS8LyLXBbO9SpVKRLRoibkyFZ7MBhEv5UuQ6pBbAVxPgewvYTtv5SjICyCVwFkF\ncudb/31XpI9XS3QW4DKHw7GzQoUKrqeeekr2798v/jp69Ki88MILUqlSJafD4diPFcwMsBZrBOe9\nSB+flsQpOjKgYo63EYHCFsCWu6DNf2GsDe6xgf0GML3BpAP1OPk1WIBfsFYW/BSYC67s/OWG68HD\n78D2cyB1NjQZLRLrk99UCBhjUoCnbTbbPTabzX7DDTeY3r17m/T0dOrVq1eweJOI8Msvv7Bu3To+\n/fRT5s6d68rOzvYsbX2fiBzOr88AX2ENcOkIgQoLDQMqpvgTBDKgxRgRF4Ax5gxgYBL8LQ/qAqSC\nK/+esPYscGflz51xwF4nTAdeE5E9ABONaT0EvtkOB5fAuZ56lSquoK8lJf0tLy/P6mupqVSpYvW2\nrKwssrKsu147HI69TqezSF8rVpcGAhVWGgZUzAg0CBRnjDkb61x5c6At0Ad4B3gbyAB+FS9viKnG\njB4G496GhTeJXBGUg1FxLb+vZXLqDTWzgfqU0NeK1aGBQIWNhgEVE8obBIozxtyEdXuCm8WPu+i9\nb8zqPtBuKgwdIfJqAE1XCcoYkwVUKvbw7xLADZU0EKhw0UsLVdQLdhAoi83QZSMc6wtTxhvTMFT7\nUaqw/NGDtlg327zWGPNehJuk4pSGARXVoiEIAIwRyfkUulYAW2dYNdYYeyj3p5SHBgIVDhoGVNSK\nliDg8YhIxjx4vB2c1QA+Dsc+lQINBCr0NAyoqBRtQcBjmMj492HN9dDrRWPuCue+VWLTQKBCScOA\nijrRGgQ8dP6AihQNBCpUNAyoqBLtQQB0/oCKLA0EKhQ0DKioEQtBwEPnD6hI0kCggk3DgIoaLvi9\npBvCRlMQ8ND5AyqSNBCoYNIwoKLGPSLPLoCVxZfBisYg4KHzB1QkaSBQwaJhQEWNGcZM/it0+BZ+\n89z0PpqDAOj8ARV5GghUMGgYUFFhhjGTB8G9K2DnIjjndRj1MWyI5iDgofMHVKRpIFDlpfcmUBFX\nOAishkZjRPJCvc9A703gD71/gSosGPcmKMM+9V4Gqkx0ZEBFVCSCQKjo/AEVaTpCoMpKw4CKmHgK\nAqDzB1R00ECgykLDgIqIeAsCHjp/QEUDDQQqUBoGVNjFaxDw0PUHVDTQQKACoWFAlYUdcAAm0BfG\nexDw0PkDKhoEKRAYrPe7I5htU9FFw4AKxHnANCAbyAO2AzfiZyhIlCAAOn9ARY9yBoKewDqs93su\n8DbQIOiNVBGnYUD5qyWwARjCyW8I9bA+HGZgjRaUKJGCgIfOH1DRogyBwABjgYVA80KP9cX6HOgS\noqaqCNEwoPzRElgBVKXoH31P/7kdeJ0SAkEiBgEPnT+gokUAgcAA44An8v+78PvaAVTECgldQ9RU\nFQEaBpQvniBQiZK//RtgAF4CQSIHAQ+dP6CihR+BwBMEHi2lGhuQBCxAA0Hc0DCgSuNPEPA4JRBo\nELDo/AEVTUoJBP4EAQ8NBHFGw4AqSSBBwKMgELxeocILGgRO0vkDKpoUDwQ2m+09/A8CHhoI4oiG\nAeVNWYKAhxGR2wZNnz5ihd2uQaAQnT+gooknEBhjvn766aevxUcQ2LdvH7/99lvxhzUQxAkNA6q4\n8gQBAIwxmNtuo0tOzpdjRNzBbFys0/kDKpqICC6Xa9no0aNL3W7Hjh307t2bG2+8ka1btxZ/WgNB\nHNAwoAoLOAiUdNdLYww2u70/pVxlkIh0/oCKIgYYZ4zxeWqgQYMGPPvsszRu3JgOHTpoIIhDuqKU\n8vAZBDIzM1m1ahVZWVm0aNGCdu3aYYzB7XZjs3nNlZ45BACDAVcI2h1zHhHJmGrM48NgXKY1f+CK\nSLdJJRy/Jwt63t/t27enffv22O12Ro4cyQcffEBqamrhTQsHgiuAZaFouAoNDQMK/AgCmzZtolOn\nTjRr1oyNGzdSs2ZN6taty/z587HZbBoIAjRMZPz7xvTyzB8YIfJqpNukEoZfQcDtdlsjfDYbeXl5\n2O12bDYbrVu3ZsWKFbjdXs8AaiCIUXqaQPkMAsePH+euu+7ihhtuYNmyZWzfvp1HHnmEH3/8kdat\nW5OTk1MQCErgCQQzKMP9DOKVzh9QEfIkfowI2Gw2jLHerklJSQVhf926dezbt6/EU4ToKYOYpCMD\nic2vOQK5ublkZWVx+eWXY7fbOfPMM+nbty8NGjSgf//+dO7cmTVr1mCz2RCRgg+QYgwwCGud81dC\ncCwxZ4xIzkRjug6Bb/LnD5w7RkRHTlQo9ebkyoJeZWRk8Omnn5KXl4fT6QSsOUB79uxh586drF69\nmtmzZ5OWllba+11HCGKMjgwkLr8nC6alpeF2u/n8888LHnM4HKSnpzNjxgwOHTrEo49aXzRK+GDw\nEKxvJaeVq+VxRNcfUGFkAyYCJQ7hHT9+nD//+c88/vjj/O9//2P9+vVkZGSwa9cucnNzadasGd98\n8w0333wz4PP9riMEMURHBhKT30FARLDb7fTt25fPPvuMRYsW0bNnT8D6IGjbti29evUiIyODvLw8\nkpKSSqvOAGcBDYHvg3Eg8UDnD6gwOR1oUtoGqampbN68mXbt2tGgQQOmT5/udbtSRgSK0xGCGKEj\nA4knoMsHPW/4/v3743a7mTJlCitWrCh43uFwcNFFF7Fr1y6ysrL8bYOuPVCMzh9QYeDX+65JkyYs\nXbqUxx57jCeeKHpGwTNPwFsQ0DkEsU3DQGIp04JCIkK9evWYMWMGu3fvZtKkSbzxxhsAOJ1Ovvvu\nO2rUqEHFihV9VeUGtgFbytT6OKbrD6gwOIL1zdzpa8PWrVuzZs0axo0bx8SJEwseLy0EGGNwuVwc\nPnyY48ePF99MA0GU0zCQOBoBy/Hz1EBhnrUEmjVrxrx586hYsSITJkygdu3a9OjRgzlz5jB58mRS\nUlJ8tcEGPICODHil8wdUGDyS/2+JX+M9WrVqxXfffUdycjJHjx4t8pznyiHP5Yc///wzY8eOpUWL\nFnTs2JHu3buzadOm4lUWDgRty3sgKrhMKUM7Kn4Y4BuskQGv80SOHz+O2+1GREhLS/NaiWctgYMH\nD5KZmcnChQupWbMm7du3p0GDBv60417gxTIeQ1AZY24C/gncLCJvR7o9hb1vzOo+0G4qDNX5A7Ev\nCvvaDcD/5f/s88S/0+nE4bA+NlavXs2ll14KnPw82LRpE3fccQc2m42LL76YLl26sHjxYubNm8e6\ndeuoU6dO8SpdwF6gHpAbnENS5SYiWuK/dJNSbNmyRbp37y4XXXSR1KhRQ9566y0REXG73QXbuFyu\n0qrwx8gIHbvXAtyE9e3opki3pXh5EpLXwdE94BwHDSPdHi3lK1Ha1/qJiDu/+GXGjBnSoEEDmTVr\nVsFjW7ZskQsvvFB69eolCxcuLHjc6XRKx44dZe7cuaVVeVsU/B605Bc9TZAY6pf0xNatW+nQoQNN\nmzblgQceoF+/fgwcOJANGzYUOT/oWXBk9uzZ/PLLL4Hu/z5gchnanZDG6PwBFXr/wgop4McpA4Bu\n3bpxySWX0K1bNwAOHjzIY489Rq1atRg1alTBVUYAhw8fZuPGjaVNKs6jlM8lFQGRTiNawlJuES8O\nHTok3bt3l+HDhxd5vFOnTnLPPfeISNHRgVWrVkmDBg3klltuEafT6a1Kb6JqRMBTiM5va0XKFBgt\nIP+EBZFui5aylyjvawGNEBR+33/77bfSsGFDmTNnTpFt8vLy5O2335ZmzZrJ6tWrS6xKRB6KguPX\nkl90ZCAxvA8cpNg3gLy8PI4cOcJ1110HnJwUVLdu3YL7lhceHbj00ksZNWoUTz31FHa7X19WdUSg\nHIaJjH8f1njWH4h0e1RcCmiEoPD7fuHChWRnZzNgwICCx0SEDRs2MHbsWOrWrUu7du1KqioPmF3m\nVqug0zCQGP4A/kaxyULVq1fnrbfeon379gC4XNZKuOedd94pNx3yzCYeMmQIdevW9WefGgSCQNcf\nUGEQ8CkDgJo1a1K/fv2CJYudTierVq2if//+pKamMn/+fKtC8VrlI8D+crVaBZWGgcTxLjCs+IOe\nqwDcbnfB6oEiwv79J9+nEydOZObMmQVvej9oEAiSMTp/QIVHwIGgffv2rF+/nlGjRjF37lxGjRrF\n4MGDqVq1KmvWrCm4JNnL2gQTiJKritRJGgYSyyvA3d6e8NxkqPB/AzzxxBOMHj2arl27Flxe5IMG\ngSDT9QdUmAQUCBo0aMDy5cvZsGED48ePZ8uWLVx77bWsWbOG5OTkkm5rPgF4zJ/6VXjpvQkSz9T8\nf6cUf0LEWm/c4XBQq1Ytnn32WSZNmkRGRgYtWrTwp24NAiGi9y9QYfKv/H/fxvqDXeo6BC1btmTB\nggVkZ2dTuXLlgtFFDQKxR8NAYvIaCDxv3qSkJF577TXS0tJYtWoVrVq18qdODQIhthm61IX9+fMH\nPh8tsj3SbVJxKaBAkJKSUmT1URHRIBCD9DRB4pq66YUXlnt7okePHgCsWbOG1q1b+1OXBoEw0PkD\nKozKNKkQTr1/waxZs7ahQSDqaRhIUDOMmXzByJGdtz/wwKHiz7Vu3ZqsrCyaNCn1bqceGgTCSOcP\nqDAqcyDwmDp16q+33357Y2PMu8FrlgoFDQMJaIYxkwfBvStg5/8999y5eJlUmJqa6k9VGgQiQNcf\nUGFUnkAw4cCBAzWBr4FrjTHvBbVlKqg0DCSYwkFgNTQaI5KHNYfA61UGpdAgEEG6/oAKo7IEggnA\nY08++aRg3aFQA0GU0zCQQEoIAh6BBAINAhGm8wdUmAUSCIpMFhTrmmUNBFFOw0CC8BEEPAoHgpLe\n8BoEooTOH1Bh5k8g8HrVgAaC6KdhIAH4GQQ8pgK3Yi1h7MJaQ9yV/9+D0SAQVXT+gAqzfwF/BY4B\nbk5+PuQBD1DKVQMaCKKbrjMQ5wIMAh5vAguAu4BzgAPANKybHakoo+sPqDD7GKgF3An8CTgCvAr8\n6uuFIiLGmLbAV+QHAhG5LpSNVf7RMBDHyhgEPH7DGvJTUW6MSM5EY7oOgW/y5w+cO0bEFel2qbiW\nBTxblhdqIIhOepogTpUzCKgYo/MHVCzRUwbRR8NAHNIgkJh0/oCKJRoIoouGgTijQSCx6foDKpZo\nIIgeGgbiiAYBpesPqFijgSA6aBiIExoElIfOH1CxprRAYIy5LGINSyAaBuKABgFVnM4fULHGWyAw\nxkwBvjTGzIps6+KfhoEYp0FAlUTnD6hYUzwQAMPynxqogSC0NAzEMA0CqjQ6f0DFovxAkOHlKQ0E\nIaRhIEZpEFD+0PkDKtYYY/7KyRGB4jQQhIiGgRikQUAFQucPqFgiIvOBZaVsooEgBDQMxBgNAqos\ndP6AiiUi0g0NBGGlYSCGaBBQZaXzB1Ss0UAQXhoGYoQGAVVeOn9AxRoNBOGjYSAGaBBQwaLzB1Ss\n0UAQHhoGopwGARVsZZg/cA5wD/AvYBLQOqQNVKoYDQShp2EgimkQUKEQwPwBA/wN2Am8CFwHjMRa\nEOaR8LRWKYsGgtByRLoByjsNAuXiADoCLYDTvG2wePHi5itXrqRDhw59gLpeNskBfgCW5v8cVx4R\nyZhqzOPDYFymNX/gimKbVAFmAdcUeqxwaJgAHAVeCWlDo5/2tTASkW7GmKVA1xI2GWiMQUQGhbNd\n8cBYiz2p8jLGnAFcDVycBJe4ob4bKhhw2eGwE74WWIf1hv9aSvnFaxAol7ZYf9zOBFyA19+z2+02\nLpfLbrfbXTabzds2BuuP3+/ATcC/Q9TeiHrfmNV9oN1UGDpC5NX8h9OBD4DzKBoAinNi/b69rRaX\nCLSvRYiPQAAw21sgMMY0A3oCrSvAJS442w0OG+TZITMX1mL1549EZE9oWh+dNAyUkzGmlYERBm4U\ncDQG5yWQ1ARIwfq0/BX4FtwZIFlgd8BmJ7wEzBWRIt8ENAiUS11gM5BM6X/EAiFYH/TtgG+DVGfU\nGGtM8lWw/xxInVuhQpOHc3K6A5M5+QeqNC6s7t0cOBLipkYb7WsR5m8gMNZpsBsccI8T2pwGrnTg\nYrD/CUgCsoHtwFpwbgW7C8TAfDe8JCJfhP5oooCIaClDwfpbPxlw14K8Z0D2g0gpxQWyCORKcBkQ\nhzU02NpT53SYnAeyBH5+EpIifYwxWEaLiFOCL09EXomC4wtJmQCtD1ap4j700UfZZfjdOEXkfREx\nkT6OMBfta1FQsEZapZTynsP6ti+dwPkeSK6Pz+mjIFNAGkEeVih4E6ga6WMNddGRgTIwxjRzwEc2\nqP13sA0n8K8Gm4D+4NoIRuDJaVBtsI4IlNcKrPO3oZCJ9/O98SA958iRZcmVKlXBUeZpRPcAU4LY\npmi3Au1rUaG0EQIbUBtkLpjLAqxXgLnA3eDKht+ccJ2IrCxnc6OWhoEAGWMutsOyJpDyHtjLs65r\nHjAeGAsMBa6GnWs0CJTHJuDCENV9GKgWorojxWDdEMbf0wIcP36c1NRUb08l2vwB7WtRpKRAMBR4\nFmsYt6xxU2GYAAAgAElEQVT2ADeBexU43dBHRBaXo7qopZcWBsAY08gOS9Ih5ctyBgGwzlU9CcwA\npgGXw780CEQtE+kGBFkV4D3gZawZ8T6DwPLly7nqqquYOHGit6cN1qTD04PZyAQVb30t5MTLZYdj\ngKmULwiANYv2U7D1tCYafmSMaVvOKqOShgE/GWMcDvhnHUhdDPYqQax7CDARcMMjxphOQaxaleCL\nL77g+PHjJT6/ePFivvzyyzC2KKzSgY1An0Be1KhRIwYOHMiMGTN46aWXij9tB2oAM9E/ZioC8gPB\nWhvWcNcYgtcRKwLvge3P1gTwecaYSkGqOmpoGPDf/S5o9RY4qoag8geBS8HlgLnGGK/jsCp4Onfu\nzE8//VTi82vWrOEf//hHGFsUNlcBX+H7ssEiRIQaNWrQv39/Xn75ZSZMmODt92fHWpegpHvRKxUy\n+V/YKtQDeZbgJ9KKwJtgt1vvHa/DY7FMw4AfjDFn2eDp+8G08bHtcaxE2hM4A+sXPNePfdiAOSc7\n2n3laa/yLX9hkhKfT09PZ926dWFsUVj8CXgbP08LeDidTlwuV8HP7du3p3bt2mRklDg9YDK6ZDEA\nOTk55OToOkJh0t8Frd4EU9GPjdcDvbE+p1OBZvieAVsfeMb6uL7bGHNBuVobZTQM+GeQHewP+7Hh\nQeBpYBvQksDSaX1gANgcMMwYo6tDhlirVq2w2WxeyzXXXMP//ve/SDcx2O7D+oJTarfMzc1l69at\n7Nu3DwCHw4Ej/yoDh8NBXl4eP/zwA0lJSSVVkdDzB5YsWUKvXr2oWrUqKSkppKSkULVqVXr16sXS\npUsj3by4ZKwPzBGXg9vXFzaAz7AWczgIPIG16MtVwH/9eO1dwBnWhNmhZW1vNNI/OD4YY2wOuPtG\nMGf4sX0NYC9wNtZygxcHuL+hwAyojhVaPwjw5SoAzz//PPXq1Yt0M8KpMT5GBHJzc6latSp//PEH\nrVq14tixY9SuXZv69euTmppKcnIys2fPpnHjxvTq1aukagrPH7iOElbmi0dvvPEGgwcP5rrrrmPy\n5MlUr14dgH379vHZZ5/Rq1cvZs6cSf/+/SPc0rhzsRNa+HN+KgsYgPXH/90y7CgZuBMcz8AgY8yj\nIvJ7GaqJOnppoQ/5y1duXAZ0CfC1njAwB7g1gNddCM4t8Kbo+tqB8vtyL7vdzvr162nRooW/dR8B\nQjFdJJxex/ocLPVLwKxZsxg8eDBffPEFR48eJSMjg6NHj7J9+3Z+//13LrvsMu644w5q166N2+3G\nZit1gDFe1x/w2tcaNmzIiBEjGDbM+5+lV155hcmTJ7Njx47S6o6HvhZWxpinT4eHD4LD1/mvV7Em\ntfwANAROYN1UIpBR3O1AI+vHXiKyKOAGR6NIr3oU7QW4zYAc87FqlbeSYa1eJW8E+LohIEmwJdLH\nHoNlk/hp4MCBsnv3bn83FxE5HAXHV97Szd+D7dWrl3Tu3PmUx53OgBfdyxORglU246h47WvJycmy\nbdu2En8Z27Ztk4oVK/r6ncVDXwtrscGiy8Hlz+frdSCngyy1VhkUA1IJZChItp+f0W6Qytapgsci\nfexB/B0qH9LrQV7lcO4QcEJjY4zXu6Cp8ps1axa1atWKdDPCbRmwGGv9+1ItWLCAHTt2MGrUKADc\nbjcANpsNkYBGExNq/kDTpk2ZOXNmic/PmjWLJk2ahLFFicEGf27t5xy4HVgLvvXBmuj9AXA71oiB\nv0OxBkgHY6yP67igcwZ8q3F+mH9PdQGxOvZZwO5w7jtRDBw4kHPOOaekBXTilWCdJtjMyYtdSjR/\n/nz+/Oc/c/PNN9OyZUvAugojQAk1f+C5557jyiuvZPHixXTr1q3InIFly5bx888/s2DBggi3Mr7k\n34iomr/rN/8O/IE1P2ty/mN/xbp39AzgKeB8P+o5H2yrrSt04oKGAd8qJId5EZVCc7QrhHO/iWTX\nrl0F33YTzH6gL7Dc14bp6emsWrWK5OTkIo+LSEEocLlc2O0+r1IsvP5APM4fKNCpUyc2b97MtGnT\nWLt2LXv37gXgnHPOoWfPntx1113UqVMnso2MPxUK/scPnuHWfsUevwmYjrUIhz9hoAJgrPmEcUHD\ngG852da3mbAFghyvP6pg+vzzzyPdhEj6AngcGOdrw7ZtT668+tNPP1G/fn2MMbhcLowxBUHgnXfe\n4ZdffmH79u107tyZfv2Kf9QC1hcxz/3i41adOnV45plnIt2MRJID1m2I/VED2Ip1yVZhZ+f/eziA\nnYr/u416OmfAt13brIkiYbMDsFmntfaFc78qoUzEmkPgc/4AwL///W9uvvlmXn/9dcC6GsNms/Hj\njz9yxRVX8Pe//5033niD7du389RTT3Hdddd5q8ZgXc1V3uXilSogIu4k2Ffq9RmFeE7y7yn2+K/5\n/57lZz3bwJUH//Fz86inYcC3db9A0m/h3CFgt64myA3jbhNOZmYmDz/8MB07dqRRo0Y0atSIjh07\n8tBDD5GZmRnp5oWaG2tk9Lf8n0vVvHlzUlNTi0y6/Oijj+jduze5ubkMHz6c1atXs3z5cj788ENW\nrlzJxx9/XLwaO1AbGBi8w4gtAwYMoEuXQC9SVr44Ye23fvRjgOuxhnqLT/N8DesUbSc/6nAD31k/\nxs0ypXqawLcMsMY2S1xipZipWBcKe5Lnx8Av+T8PB0q7MkGAL8GZB18H3lTlr5UrV3LFFVdQr149\nunbtWmSi16JFi5g6dSqffPIJnTp1imxDQ8vv+QO1a9fmk08+ISXF+lL/9ddfM2nSJNq1a8cdd9xR\n5HRC/fr1qVu3LkeOHPFWlQA3Yr1NEk6NGjV8rcugykAg41u4MhffcwdaYl01MBtr+LUj1hvgfeBR\n4Bw/9rcZ+MMKt3ETBiJ+bWO0F8AkwbZrwO3vOgF1QGwllF0+XrvK+rAUoHukjz0Gi9/rDLRq1Uoe\nfPDBEp8fNWqUtGrVqvBD8Xzt92h/f28ew4cPl+bNm8uGDRtOee7jjz+WqlWryooVK0p6+aYoOOaw\n9bUyiOe+FpICNAXkX35+RjtBngKpC5IM0hDkpQDWghkB4rBG1ZIjfezBKhpRfRARyYOX53PqOaaS\n7MQ6Eeut+LoOZaq14NBOQBcxD6GtW7cyaFDJVxXffvvtbNmyJYwtiqiA5g9kZ2ezdu1abr311iIr\nOIoIGzdu5OWXX6ZNmzY0a9bM28tdwPfBaHS0+uGHH5g9ezbbtm0DYNu2bQwdOpRBgwYl+sTVkBGR\nLQ5YNcXPPmzHmkH7M9YMwB+xlsr0x3FgJric8KqIxM0kbw0D/nnTwInHQ3yN9HfAO0AevCgiCXnd\nW7jUrFmTZcuWlfj80qVL+dOf4uYSYl8Kzx/w+WGal5eH0+mkYsWT94Y7fPgwixcvpm/fvvz888+8\n+OKLVKtWrfhLBcjF+hyOS4sXL6Zly5Y88MADXHTRRSxevJgOHTrw008/sWvXLrp3766BIESc8OIq\nsC8O8X4mYQUCrGUJ4kekhyZipQCDAVkU4NLC/pYckKaQ57DWPK8Q6eON0eL30O3cuXMlKSlJbrzx\nRpk9e7YsXLhQFi5cKLNnz5Z+/fqJw+GQOXPmFH5JIgzddhQRtz+/vylTpki1atVk6tSpMm7cOLnj\njjskJSVFrrrqKsnOzhYREZfLVfgleSKSLSJXRsFxhqyvtW3bVkaPts66/N///Z9UrVpVHn300YLn\nH374YfnLX/7i69ebCH0t6AUwdlh2HsiREH1OrwexW+F5bKSPN+i/v0g3IFZKfkdbUh3yfglyB3OD\n3AtirEsYW0b6WGO4BHQed8mSJdKzZ085/fTTxWazic1mk9NPP1169uwpn332WfHNE+UD2u/5A089\n9ZR06dJFGjduLD179pTZs2cXPFcsCDhF5CcRaRYFxxfSvpaWliY7duwo+B04HA5Zv359wfObNm2S\n6tWr+/jNJkxfC2p5Euyvw/bKINeDuIL8OX0YpDE44/ULm961MADGmBoO+LYOnL0CHOcFoU4BnsRa\nAhN4UET+EYRqE5Xfdy0sLifHOvVXfLW9QhLlTnI2rNu9d8SPq41OnDgBWF8qUlNTC34utmzxP7Fu\nAx8Xt3rN57WvValShfXr13P++dYadpUrV+b7778vuFX2rl27aNy4MX/88UdpdSdKXwuascbYL4aN\nvaDJ+1iXDw7Cut+Az/Ux/XAE6A6u9fC7C9qJyNYgVBtVdM5AAETkVyd0yoQDbcC5qpz1HcM69/DU\nyYceNsboh0DZlTnZJicnlxYEwM9rmOOAZ/7AYfyYP5CSkkJKSgqpqal4vlgYYxARJ9b8gMFAf+Ir\nCEAJfa1OnTpFbk/81VdfFZl7snv3bs4991xfdSdKXwuKwkEA4FqsywZnYa2Bvb+c9W8E2llB4LgL\n/hKPQQA0DARMRHY4oc1eWNcBGAlkBVoH1q3jLgDnG9Y9MwblV1UN+EkDQZntJ3STPA+FqN5o5Fl/\nIKDPh4LRAKeTP379NRdojbW2SzwOP3rta0OHDsXlOpmhLrzwQhyOkwMsixYt8mfRoUTqa+VSPAh4\n3ArMB9YAjUH+j8ATVjbwNJAOsgN25I8IfBuUhkejSJ+niNWCNfp0nw1yUsA5DOT7/PP/JZ1zOgIy\nA6SZtdaF2K21LuoUqvNerA+YQ0DVSB9jDJaRIlLkZHWQ5InIc1FwfOEuAa8/ICLy67//vT8vNVVe\ngLui4Bi0r8VpeRLsC2BLSZ+32SCPwz9s1npCUg/yngfZ72P+1g6QB0FOB6exRsfGE0frCZRUdM5A\nORljagJ3OmCoE86oDK50MBeCLRXrr/7/gK8h72drtUuxw0KXdfe2z6TYJYTGmHuxbujyG1BfRPy9\nb4aCc7FG9U4neKtrurDuSXIx1v1NEkkg8wecWF++/vZCnTpvddi1a/85kDobmowW2R7qhkaA9rUI\nKmlEwCMHmAlj/ybyJIAx5jJj3TXzOgFHTci7BJL+hLVi4R/AjyDfgOswOOyQ5YLXsdYSiMf+ewoN\nA0FijKkAdAYuNpCeZHXS04A8N+x3wrdYS1cuF5HdPurSQFB2jbFuhlOmiYRe7ARuxrqzaSI6G2v1\n1TMo+bSBC8jEOkW7EWCiMa2HwDfb4eASOHeMiF+LwcQY7WsREGgQKMwYUx3oCqTb4c92K9RVALKd\n8JP75Of0UhE5EbqjiD4aBqKUBoJyawi04OTty4uYPXt2m+XLlw/t3LnztIEDB671skkOsA3rj1ui\nv0naA59jhYHCgUCw7kT4NtbVAkWmz0w1ZvQwGPc2LLxJ5IpwNTYCtK+FSXmCgCqdhoEopoEgdIwx\nN2Fd8naziLwd6fbEgF7Am1iXvDmxTnkdx1rFdQ4l/BF735jVfaDdVBg6QuTVMLU1qmhfCw4NAqGl\nVxNEMRF5Ab3KQEWHhVgfwsOAF7GGs2tgXcVV4jeKzdBlIxzrC1PGG9MwLC1VcUeDQOhpGIhyGghU\nFNkHTANGYZ0aOObrBWNEcj6FrhXA1hlWjTUmGGvAqASiQSA8NAzEAA0EKpY9IpIxDx5vB2c1gI8j\n3R4VOzQIhI+GgRihgUDFsmEi49+HNddDrxeNuSvS7VHRT4NAeGkYiCEaCFQs0/kDyl8aBMJPw0CM\n0UCgYpXOH1D+0CAQGRoGYpAGAhWrdP6A8iUFenXWIBB2GgZilAYCFat0/oAqzSiRf8+Eh53FHtcg\nEFoaBmKYBgIVq3T+gCrJWGOSGsOdBuse2KBBIBw0DMQ4DQQqFun8AeXNWGOSLoUfO0Hd1+H56TDq\nCIgGgdDTMBAHNBCoWKTzB1RhhYPATHj+TpH77xF5dgrU1SAQehoG4oQGAhWLdP6AAu9BwPPcYyK7\nIti0hKFhII5oIFCxSOcPJLbSgoAKHw0DcUYDgYo1On8gcWkQiB4aBuKQBgIVa3T+QOLRIBBdNAzE\nKQ0EKtbo/IHEoUEg+mgYiGPlDAT1sW5X+yEwA2gc/BYqVZTOH4gZtYAXsT4fZgMt/X2hBoHopGEg\nzpUhEBjgYeBHYDDwV2AgsBUYk/+8UiGh8wdiwh3Az8AwrM+HW4DvgBeAUv//0iAQvTQMJIAAAoEB\nxgETsfqGI/9xR/5zTwLPooFAhZDOH4hq9wHTsT4TPH/4PZ8Tw4HXKSEQaBCIbhoGEoQfgcATBB71\nUdV9aCBQIabzB6LSfcBzpTxvgAF4CQQaBKKfhoEEUkog8DcIeGggUCGn8weiiq8g4HFKINAgEBs0\nDCSY4oGgSpUqVQksCHhoIFAhpfMHooa/QcCjIBDMHzgwWYNAbNAwkIAKB4LRo0fvIfAg4KGBQIWU\nzh+IuECDgIcRkQFtevQ42Mlm0yAQAzQMJCgReXHBggVLHnzwwdPKWZUGAhVSOn8gYsoaBAAwxpjq\n119faf+yZVvuFHkwiO1SIaBhIDEZYFyvXr3+EqT6NBCokNL5A2EXcBAQkVMeMzYbNTp1akIpVxmo\n6KBhIPH4NVnQ88YWEVwulz/1aiBQIaPzB8LKZxDIzMzkrbfeYtq0aaxZswYAYwxut9vb5iVeZaCi\nh8P3JiqO+H3VgDGm4N/ffvsNu93Oxo0badCgAeedd15JL7sv/98HgFO/JihVDo+IZEw15vFhMC7T\nmj9wRaTbFId8BoFNmzbRqVMnmjVrxsaNG6lZsyZ169Zl/vz52Gw23G43Ntsp3zM9gQCsxcz8+oah\nwkfDQGLxGQTy8vL46quv2LlzJ59//jkul4tvv/2Wxo0bs3DhQqpUqcKmTZs499xzS6pCA4EKmWEi\n4983ppdn/sAIkVcj3aY44jMIHD9+nLvuuosbbriBl19+mcOHD7NkyRLGjh1L69atWbNmDcnJyb4C\ngQEGAV6HEVRk6GmCxPE3fAQBt9vNm2++SadOndi5cyc1atSgf//+fP7551xxxRV06NCBDh06cPjw\nYV/70lMGKmR0/kBI+DVHIDc3l6ysLC6//HLsdjtnnnkmffv25a233uLEiRN07twZAJvN5nUOAScD\nwbhgNl6Vn4aBxFAF+LuvjWw2G61bt6Z69ers37+fiRMn0qNHD7755humT59OzZo1efTRR2nSpIk/\n+9RAoEJC5w8End+TBdPS0nC73Xz++ecFjzkcDtLT05kxYwaHDh3i0Uet7xyeU40leBCoXfYmq2DT\nMJAYrgEq+7Nh8+bN+eSTT5g/fz6DBw9m4cKFTJw4kQsuuIARI0bQunVrwPvMYS80EKiQ0PUHgsbv\nICAi2O12+vbty7fffsuiRYsKnjPG0LZtW3r16kVGRgZ5eXn+VHlr2ZqsQkHDQGJI9ndDESE9PZ3V\nq1fzwQcfMGDAAFq2bMkjjzxCq1atCrbzkfoL00CgQkLXHyi3gC4f9Lzn+/fvj9vtZsqUKaxYsaLg\neYfDwUUXXcSuXbvIysryVZ2bAD6XVOhpGEgM3/u7oecNv2HDBs4991xycnLYsmULTZs29bq9jhCo\nSCo+f2CsMadNM0bPR/tWpgWFRIR69eoxY8YMdu/ezaRJk3jjjTcAcDqdfPfdd9SoUYOKFSv6qiqJ\nAD6XVOhpGEgMXwFLAac/G8+fP59Ro0bRpk0bXnrpJc4991zcbneRa4g9IcAYg8vl4vDhwxw/fry0\nau8DninzESjlReH5A91h7V9h31AY/aox2tdKNoIATg0U5llLoFmzZsybN4+KFSsyYcIEateuTY8e\nPZgzZw6TJ08mJSWltGqdwDbg/bIegAo+4+c3OxX7agDfANXxcUnpzp07mTRpEv3796ddu3YFj+fl\n5ZGUlFRw2dDPP//Mm2++ybvvvovNZqNy5cq8+uqrNGvWrLTqbwXeDMLxlIkxJguoVOzh30XErzkV\nKjq9Y8yy66GL57+PAq9Cp4dEvohgswAwxtwE/BO4WUTejnBzumJ9MSjR8ePHcbvdiAhpaWlet/F8\nBhw8eJDMzEwWLlxIzZo1ad++PQ0aNCitehfwO9AW+KGMx6BCQMNAYqkDrMKPQJCdnV0w1Pfll1/S\nvn174OSHwKZNm7jjjjuw2WxcfPHFdOnShcWLFzNv3jzWrVtHnTp1vFUrwB7gfCA3WAcVCA0D8edd\nY1b0hY7FH98MJz6Ac54Q8XkCO5SiKAwYrC8EF1HCSoBbt25l5MiRHDhwgH379jFp0iRuvvlmRKTg\nFGIJawj4wxMEOqKnCKKOniZILJnAZcA+fJwySE625vbMmDGD22+/ndmzZwPW5Ydbt27lpptuolq1\najz22GO88MIL9O7dm5dffplmzZrx5ZdfllStAWoCFwTncJSCLPiPt8cvhJSWsDLc7YliVYHWlBIE\nOnToQNOmTXnggQfo168fAwcOZMOGDUUmDHuCwOzZs/nll1/83bcGgWgnIloSr9QRkf+KSJ748PPP\nP8stt9wiu3fvFhGRAwcOyNVXXy09e/aU5cuXF9n2wIEDUrVqVZk6daqvaltE6tiBLKwRisIlK1Lt\n0VL+MgbMp/CTgHgr0+CZSLYPuCm/n90U4d9VNSnBoUOHpHv37jJ8+PAij3fq1EnuueceERFxu90F\nj69atUoaNGggt9xyizidzpKq9XCKyBGJ4Ptei++iIwOJKRM/Rwjq1q3LnDlzqFWrlvXCzEy2bNnC\nDTfcQKdOnQq2czqdLFmyhJo1a9KyZcuSqhNgF7Cl3EegVL4nReRraPtTCaeeboQHnzHmlNMICegw\nsBYv9wXIy8vjyJEjXHfddQAFk4Xr1q3Lb7/9BhS9nPjSSy9l1KhRPPXUU9jtpa75pCMCMULDQOLK\nxM9AUPjNvnDhQrKzsxkwYEDBYyLChg0bGDt2LHXr1i0y6bAYAzzka39KBepxkQPz4YYTXp6rAlwB\nC58yJtHnhQjwMF4+96tXr85bb71VMDfIc6fS884775T5AUePHgVgyJAh1K1bt7T9aRCIIRoGElsm\nfgYCj5o1a1K/fn2cTmtzp9PJqlWr6N+/P6mpqcyfPx8ocf2BccC8ILRbqVM8IDL/XzDL23M6f6DA\nF1j3KTmF5yoAt9tNUlISYL2P9+/fX7DNxIkTmTlzZsH7vxQaBGKMhgGVSQCBoH379qxfv55Ro0Yx\nd+5cRo0axeDBg6latSpr1qwpuA7ZywqFE4Angt56pQrZDYM/K2FCYW9oqesPAPAqcHdJTxa/yZBn\nZOCJJ55g9OjRdO3aFYej1IuRNAjEIA0DCgIIBA0aNGD58uVs2LCB8ePHs2XLFq699lpfty6dADyG\n3tJYhZjOH/DbVEoJBJ4w4HA4qFWrFs8++yyTJk0iIyODFi1alFavBoEYVWq8UwklEysQ+FyHoGXL\nlixYsIDs7GwqV65cMKSoQUBFg8dFDjxrzA1/gw+Lr4NXaP5AxNcfiAJT8/+dUvwJz/s4KSmJ1157\njbS0NFatWlXk/iReaBCIYToyoArLxM8RgpSUFKpVq1bk3KKXiUbPo0FARYDOH/DbVGdOzvCSnuzR\nowcAa9asKbhjaQk0CMQ4DQOquEwCnFQIp97FcPz48VStWvU2Y8zpQW2dUn7S+QO+jTUmaUXFiiNd\nw4Z5fb5169ZkZWXRpEmT0qrRIBAHdDliVZI6+Ll0sRcT7Hb7AbfbPRn4DagvIoeD3L4y0eWIE8vT\nxpx1I/y3PlQo/ly47l8QRcsRFzHWmKRL4cdOUHcmPH+nyM94OWXggwaBOKEjA6okmZRhhID8OQIu\nl+sFYCRQDfjJGFM16C1Uygddf8A7L0HgfnxMKvRCg0Ac0TCgSpNJYIGgyGRBEdFAoCJO5w8UVUIQ\n8PA3EGgQiDMaBpQvmfgXCLxeNaCBQEUDnT9g8REEPHwFAg0CcUjDgPJHJlYg2AW4Cz3uCQdjKOWq\nAQ0EKtJ0/QG/g4DHVGAI1vu98JcAF3AI6IAGgbiiYUD5KxPrPuiPAXuwJgauBNoDT+Hj8kENBCrS\nEnn+QIBBwON1oBWwACsA7AP+ATQFNoassSoi9GoCFVbGmHuBiF1loFcTqFnGzBwEg7w99zFs6C1y\nUTD3F+mrCcoYBFSC0ZEBFVY6QqAiLZHmD2gQUP7SMKDCTgOBiqREmT+gQUAFQsOAiggNBCqS4n3+\ngAYBFSgNAypiNBCoSIrX9Qc0CKiy0DCgIqq0QGCK3/BAqSCLt/kDGgRUWWkYUBHnLRAYY14GfjHG\npEa2dSqexdP8AQ0Cqjw0DKioUCwQ/Iq1Atp5WOFAA4EKmXiYP6BBQJWXhgEVNfIDwZdAxUIPn4MG\nAhVisTx/QIOACgYNAypqGGNewFrRsDgNBCrkYnH+gAYBFSwaBlQ0KW2JUw0EKqRibf6ABgEVTBoG\nVNQQkVnA7aVsooFAhVSszB/QIKCCTcOAiioaCFSkRfv8AQ0CKhQ0DKioo4FARVq0zh/QIKBCRcOA\nikoaCFQkReP8AQ0CKpQ0DKiopYFARVI0zR/QIKBCTcOAimoaCFQkRcP8AQ0CKhw0DKiop4FARVIk\n5w9oEFDhYkQk0m1Qyi/GmEHAzFI22QvUF5HjXl5bAbgQWAMkF3s6B+gEfC8ifwSntSqePG3MWTfC\nf+tDheLPHQVehU4PiXwBRfpaa6AZ0BK4DFgKzAfW4Udf0yCgwknDgIopgQYCY0xjYKjdbr/d5XKl\n2mw2zj//fM4880wAjhw5wo4dO3A6ndhsthy32/1P4BURWRfqY1Gx5Vlj/vo3+DDFy3Ob4cTl0H4P\nDLDD7S5ItYHUB+eZYBewHQXXdrA5wdggxw0l9jUNAirsRESLlpgqwCBASin/A+rYbLZ3AalWrVre\nI488Il999ZUcP35cisvOzpaMjAwZP3681KhRIw8Qu92+DKgT6WPVEl1lJswUkMJlH0jf/L5XDfIe\nAfkK5Hix7QQkGyQDZDxIDbD6GhTpa09C0hL4OQ/kVXgu0sesJTGKjgyomORrhMBut0taWpr7+eef\nt994440kJxc/M+Cdy+Xi448/5p577nHu3bs3z+Vy3QdMl/h9o1QA0gATovqPYZ2GiQtPGmPawY7u\ncBTBpVEAAA0XSURBVD7Au8BQrF/eP4AbOfUcVElcwMfAPeDcC3kuuO9vMPNqHRFQkRDpNKJFS1kL\npYwQXH311bJv3z4pq2PHjsmdd97pqe8F8k+pxVHpJSKfiYizzL8k/7hFZLWI3BTBYw1qeQrO2gE5\nz+T3tWvzRweKjwL4W46B3Jlf1xVwNFdHBLREoES8AVq0lKd4CwSPP/64uN1uCYZp06Z56n0+jgJB\nP7H+SLuC8kvyzbOfe4N8HBErDa3LDeVxEHc5gkDhMi2//zaHjDjqa1pipOhpAhXzCp8yePjhh5k4\ncWJQ6586dSp33303wM0i8nZQKw8/O9YkyzMjsO884AwgKwL7DhpjTGfg84eB4PY0mArcbf0YD31N\nxRANAyrmGWMqORyOXZdcckm1lStXYrMFf/mMfv36yfvvv3/M6XQ2FpG9Qd9B+LQDVkdw/zcA70Rw\n/+VijKnkgK1toMYXYA/FQi39QN6HY06I9b6mYoguOqTiwZN2u/30N954o9QgsHXrVq6//nrOP/98\nUlNTOeuss+jYsSOffPKJzx1MmTLFVKlSJdVms70YzIZHQJ0I7tsZ4f0Hw5N2OG+OjyDwBdaHa/Fi\nB77xsYMpYKpYlybGel9TMUTDgIppxpjKdrt96P333287//zzS912165d/P7779x222289NJLPPHE\nExhj6N27N6+//nqprz3zzDMZN26cQ0T6GmNqBfMYwswR4f0nRXj/ZWaMqWyHofeDrfSedtK9wFuF\nyptAfR+vORMYBw6BWO9rKpZEetKCFi3lKcBdxhj37t27pSzcbre0bNlSLrjgAp/bZmVlSUpKihN4\nOtLHXY5ya0nHN23aNGnevLmkpaVJWlqatG3bVhYtWlTq72T58uXSqlUrSU5OlgYNGsicOXNK2zxP\nREZHwe+g7H0N3Lv9mAy4AsRYw/0+t/VWskBSrJGUWO5rWmKo6MiAimkOh2PAFVdcQa1aZfsCZYyh\nVq1aHDlyxOe2lSpVYsCAAfakpKSBZdpZlKtVqxbPPPMM69evZ926dXTp0oU+ffrwww8/eN0+MzOT\nK6+8kq5du/L9998zYsQIBg8ezJIlS8Lc8vBwwIArgEB72u9YawoEohIwAOxJEJd9TUWhSKcRLVrK\nWgCHzWbLfu655yQQx48fl4MHD8p//vMfef7558XhcEj//v39eu28efM8lxqeFenjL2MpcWTAm2rV\nqsmsWbO8Pvfggw9Ks2bNijzWr18/6dmzZ0nVxezIAOCwQfZzfn6zX5E/MpCW/68DpHP+6oP+jg7M\nO3m5bKz2NS0xVCJ9/lCp8rjA7XYnp6enB/Si+++/n+nTpwNgs9m49tprefnll/16baF9pQOLA9px\nDHG73bzzzjucOHGCtm3bet1m7dq1dOvWrchjPXr0YOTIkeFo4imMMaG8ZNHmhmR/e1oF4DqgF9Yc\ngK3As0AHrDtltfCjjvSiP8ZtX1PRQcOAimUNAZo2bRrQi0aOHEnfvn359ddfeeedd3C5XOTk+Ldi\nbr169UhOTnbn5OQ0Ig4/oDdv3kzbtm3Jzs6mcuXKfPjhhzRu3Njrtnv37qV69epFHqtevTrHjh0j\nJyfH7yWgg6hSqHfgb09rm188rgSuBZoDjwAL/aijHpAM7hyIy76moouGARXLUsA6lx+Ihg0b0rBh\nQwBuueUWevToQe/evVm7dq3P1xpjOO200yQnJ6etMeZAGdocUbNmzWozcGDJp6EbN27M999/z9Gj\nR3nvvfe49dZbWblyZYmBIBBut9ssWbKk+eWXX35TuSuLkPKkjfOBPsCH/H97dxcaVXrHcfx3XpTG\nlyxIuyuoEAXvQiCGXqglbiQYwauCWtkLhfZCr7KGZSUWtvRmg3ghRCpelKHK6k1owV7I0Kikho0s\nwcBAsmCwJaINeXNak22im3nOPL04vmB9mTGTcTzzfD9wboYz538m/JP85pznOU987b/QYhCepJo4\nDLxuoURgWREGkGSRFC8uVIr9+/fr2LFjunv3rrZu3Vpwf2NMoPjhOb8qqXAF9PX16W1hIAxDbdmy\nRZLU2NiowcFBdXd36/z586/su379ek1NTb302tTUlGpra197VSCKoqC/v/+gpIOlfYrKKa3T4sGH\ni5LmVVyweFrPlFgWKIgwgCTLSvHl6kLPGHibx48fS5JmZ2cL7ruwsKCFhQVJ+qOkvy+5aIW0tLT8\nQvFCe0XJ5/NvvIWyfft2pdPpl17r7e194xiDIAii5ubmv3R1df21+DN+J5fLdNznJvV0ucIl+qek\nn6i4ILAgaT7+G/3vEkoCxan0CEY2tqVukj6WZHt6emwxpqenX3ktl8vZbdu22dWrV9v5+fmCxxgY\nGHg2wrux0p9/idsbZxOcPHnS9vf323v37tnh4WHb2dlpgyCwN27csNZa29nZaQ8ffvH2sbExu2bN\nGnvixAl7584de+7cObtixQp77dq1N5Uo62wCxWselGv7ryTbU+RMgJnXvJaR7ErJ/rLIYwy8mE2Q\n1F5jS9DGlQEklrV2euXKlVO3b9/+5MCBAwX3P3r0qObm5tTc3KwNGzZocnJSly9f1ujoqM6cOaNV\nqwrfmh0aGpLv+7l8Pv/9cnyGD8n09LSOHDmiiYkJffTRR2poaFBvb692794tKb4C8+DBg+f719XV\n6erVq+ro6NDZs2e1ceNGpVKpV2YYvC/W2rXlPP5Kz5u8LX1SuNPi+0c1iheC+FjS94ovJa1R8Ysb\nDUnypVw+fjtQVixUhETzff/ipk2bPhsbGwsLLVDU09OjVCql4eFhZbNZrV27Vk1NTWpvb9e+ffuK\nqrdz585ocHDw21wu9+kynH4lHJZ0sUK1jaTfS/q6QvVL4nvexU3SZ2PxMwfe6g+K71n8Q9KcpJ9J\napX0O8WzBIqxU4oGpW9z1n661HMGikUYQKJ5nrdd0q10Oq29e/eWtdbw8LAaGhok6YC19s9lLVY+\nhIElet5rksrbadKw4mmISnavIUF4HDGS7rswDEdOnTqVL3ewPX36tA3DcEZSuQbA4cP2XSiNnJLy\n5f4KdTp+aiG9hveGMIBEs9ZaY8yXN2/e9FOpVNnqpNNpXbp0yTPG/NZamytbofKbr2BtX/FAvESy\n1lojfXlT8svXaVJa0iXJM1LSew0Jwm0CVAXf91M1NTVHRkZGgs2bNy/rsbPZrOrr683MzExfFEVt\nNtm/NBsk/auC9X8u6XYF65fM97xUjXRkRAqWt9PiubL1kpmR+iIp6b2GBOHKAKqCtfaLxcXF8dbW\nVjMxMbFsx52bm1NbW1v08OHDH6Io+k0V/HEel9Sn0p+f866MpLuKB8knmpW+WJTGWyWzfJ0WDzRs\nk6KH0g+RVA29hgQhDKAqWGsfGWNa7t+/n92xY4cZHR0t+Zjj4+PatWtXlMlkHhtjWq21Dwq/KxEO\nSnq2LnFO8T/qqEzbs8vck5L2KJ43n2jW2kdGarkvZXdIpvROixPaLinKSI+NVE29hoTgNgGqiud5\ndWEYXvd9f3NXV5d//PhxBUHwTsew1urChQtqb2+Pnjx5kjXGtFlrM2U65UpZIalF8cD4n6o8Xwys\npEeSrkv6m6QnZahRMZ7n1YXSdV/a3CX5xyW9W6fFP6ALktql6ImUNfGtgWrrNSQAYQBVx/O8VYqn\nr31eX1+f7+joCA4dOlTwoUKLi4u6cuWKuru7o1u3bgWe531jrf3cWvuf93LiSJyXek3Kd0jBIRVe\nWWhR0hVJ3VJ0Swo86Rsr0WuoGMIAqpbneTuCIPgqiqK22traaM+ePWFTU5MaGxu1bt06eZ6n2dlZ\nZTIZDQ0Nqbe312Sz2TAMwwFjzNfW2nThKsDTXpO+iqS2WinaI4VNkholrVO8AuGspIziQRO9kslK\nYSgNGIleQ8URBlD1PM/bIunXQRDskrQtiqKXvrj5vv+j7/sZY8yApD9Za0cqcqJIvOe9JsW99n8X\nCXzpR1/KGIlewweFMACneJ7nS6qTtFYv5r2PxVPIgeVDryFJCAMAADiOqYUAADiOMAAAgOMIAwAA\nOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiO\nMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAA\nAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA\n4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMI\nAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMA\nADiOMAAAgOMIAwAAOI4wAACA4wgDAAA4jjAAAIDjCAMAADiOMAAAgOMIAwAAOI4wAACA4/4H+Wp9\npVTSlp8AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7ecbc18>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "G=nx.DiGraph()\n",
    "list_nodes = list(range(1, num_nodes+1))\n",
    "G.add_nodes_from(list_nodes)\n",
    "for i,j in links:\n",
    "    G.add_edge(i,j)\n",
    "\n",
    "# Adding the position attribute to each node\n",
    "node_pos = {1: (0, 0), 2: (2, 2), 3: (2, -2), 4: (5, 2), 5: (5, -2), 6: (7, 0)}\n",
    "\n",
    "# Create a list of edges in shortest path\n",
    "red_edges = [(i,j) for i,j in links if x[i,j].x > 0]\n",
    "\n",
    "#Create a list of nodes in shortest path\n",
    "sp = [ i for i,j in links if x[i,j].x > 0 ]\n",
    "sp.append(destination)\n",
    "\n",
    "# If the node is in the shortest path, set it to red, else set it to white color\n",
    "node_col = ['white' if not node in sp else 'red' for node in G.nodes()]\n",
    "# If the edge is in the shortest path set it to red, else set it to white color\n",
    "edge_col = ['black' if not edge in red_edges else 'red' for edge in G.edges()]\n",
    "# Draw the nodes\n",
    "nx.draw_networkx(G,node_pos, node_color= node_col, node_size=450)\n",
    "# Draw the node labels\n",
    "# nx.draw_networkx_labels(G1, node_pos,node_color= node_col)\n",
    "# Draw the edges\n",
    "nx.draw_networkx_edges(G, node_pos,edge_color= edge_col)\n",
    "# Draw the edge labels\n",
    "nx.draw_networkx_edge_labels(G, node_pos,edge_color= edge_col, edge_labels=cost)\n",
    "# Remove the axis\n",
    "plt.axis('off')\n",
    "\n",
    "# Show the plot\n",
    "plt.show()"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}