Ant Colony Optimisation for TSP in ROOT framework.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the Traveling Salesman Problem in Python and C++ using the ROOT framework\n",
    "\n",
    "##### Abstract\n",
    "In this document we are going to show how to develop an Ant Colony Optimization algorithm for solving the TSP using the data analysis software package by CERN, ROOT. The interface is in python to keep things simple but the logic is in C++."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key Benefits of this work\n",
    "\n",
    "* Test the ROOT framework capabilities when working with Python and C++\n",
    "* Demonstrate how to solve the Traveling Salesman Problem with important applications in science and engineering\n",
    "* Demonstrate how to implement the Ant Colony Metaheuristic to get near optimal solutions for the Traveling Salesman Problem fast in Modern C++\n",
    "* Show how Python and C++ can be combined to have easy interfaces and fast solutions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Imagine that you are a salesman and you want to visit all your customers once and return to your home. In order to save costs as much as possible you would want to find the shortest possible route that visits each customer exactly once and returns to your starting point. This is exactly what is studied in **The Traveling Salesman Problem (TSP)**.\n",
    "\n",
    "TSP has numerous other applications even in seemingly different domains like *X-Ray crystallography*. In this application studied in (Bland & Shallcross, 1989), there is an X-ray diffractometer that is used to to obtain information about the structure of the crystalline material. The diffractometer has 4 motors for moving and needs to be positioned in various positions, sometimes hundreds of thousands. The time to move from position to position can be computed quite accurately. The sequence of the positions does not influence the end result, however, it influcences the time taken to complete the experiment. The problem of minimizing positioning time is essentially the traveling salesman problem. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ant Colony Optimization for TSP\n",
    "\n",
    "The Traveling Salesman Problem is *NP-Hard* which means that in order to solve it exactly, an exponential amount of time is needed and it is impractical for problems with a large number of nodes and that is why many approximation and heuristic algorithms have been suggested to find solutions.\n",
    "\n",
    "In this document we will discuss and develop and *Ant Colony Optimization*(**ACO**) algorithm in order to find solutions for the TSP. It should be emphasized that ACO is a *metaheuristic* algorithm which implies that there is no guarantee that it will find the optimal solution in a reasonable amount of time, but it will find at least a very good one in a very short amount of time.\n",
    "\n",
    "ACO imitates nature and more specifically the movement of ants in order to find good quality solutions fast. Ants when they move they leave a pheromone trail behind them and their purpose is to find food and return to their nest. The consequence of that is that the shortest paths have more pheromone laid over them since pheromone evaporates as time passes and for the longest paths evaporates more. Additionally, each ant is attracted with high probability to follow trails with more pheromone but with a small probability can follow its own path. Therefore, over time most ants converge to the shortest found path and some of the ants always explore for new shorter paths.\n",
    "\n",
    "In the following picture we can see 2 ants that begin from the same source going to the same destination, but they choose different paths. The one that selected the shortest path will return find the destination and return to the source faster. Consequently, it will have completed 2 tours from the same path before the ant that selected the longer path and that path will have more pheromone on it, attracting more of the subsequent ants searching for food.\n",
    "\n",
    "\n",
    "![Ant Colony, the upper path will have more pheromone](ant_colony.png)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "require(['codemirror/mode/clike/clike'], function(Clike) { console.log('ROOTaaS - C++ CodeMirror module loaded'); });"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "IPython.CodeCell.config_defaults.highlight_modes['magic_text/x-c++src'] = {'reg':[/^%%cpp/]};"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Welcome to ROOTaaS 6.06/00\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300pt\" height=\"300pt\" viewBox=\"0 0 300 300\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 6.535156 -8.222656 C 6.972656 -7.417969 7.191406 -6.3125 7.191406 -4.90625 C 7.191406 -3.578125 6.992188 -2.476562 6.597656 -1.605469 C 6.023438 -0.359375 5.082031 0.265625 3.78125 0.265625 C 2.605469 0.265625 1.730469 -0.242188 1.15625 -1.265625 C 0.675781 -2.117188 0.4375 -3.261719 0.4375 -4.695312 C 0.4375 -5.808594 0.582031 -6.761719 0.867188 -7.5625 C 1.40625 -9.046875 2.378906 -9.789062 3.789062 -9.789062 C 5.054688 -9.789062 5.96875 -9.265625 6.535156 -8.222656 Z M 5.296875 -1.703125 C 5.675781 -2.265625 5.867188 -3.320312 5.867188 -4.859375 C 5.867188 -5.972656 5.726562 -6.886719 5.453125 -7.605469 C 5.179688 -8.324219 4.652344 -8.679688 3.863281 -8.679688 C 3.136719 -8.679688 2.609375 -8.339844 2.273438 -7.660156 C 1.9375 -6.976562 1.769531 -5.976562 1.769531 -4.648438 C 1.769531 -3.648438 1.878906 -2.847656 2.09375 -2.242188 C 2.421875 -1.316406 2.980469 -0.855469 3.773438 -0.855469 C 4.410156 -0.855469 4.917969 -1.136719 5.296875 -1.703125 Z M 5.296875 -1.703125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.339844 -6.929688 L 1.339844 -7.875 C 2.226562 -7.960938 2.847656 -8.105469 3.199219 -8.308594 C 3.550781 -8.511719 3.8125 -8.992188 3.984375 -9.75 L 4.957031 -9.75 L 4.957031 0 L 3.644531 0 L 3.644531 -6.929688 Z M 1.339844 -6.929688 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.960938 -2.203125 C 1.265625 -2.828125 1.855469 -3.394531 2.734375 -3.902344 L 4.046875 -4.664062 C 4.632812 -5.003906 5.046875 -5.296875 5.285156 -5.539062 C 5.65625 -5.914062 5.84375 -6.347656 5.84375 -6.835938 C 5.84375 -7.40625 5.671875 -7.859375 5.332031 -8.191406 C 4.992188 -8.527344 4.535156 -8.695312 3.964844 -8.695312 C 3.121094 -8.695312 2.539062 -8.375 2.214844 -7.738281 C 2.042969 -7.398438 1.945312 -6.921875 1.929688 -6.316406 L 0.675781 -6.316406 C 0.691406 -7.167969 0.847656 -7.863281 1.148438 -8.402344 C 1.679688 -9.351562 2.621094 -9.824219 3.972656 -9.824219 C 5.09375 -9.824219 5.910156 -9.519531 6.429688 -8.914062 C 6.945312 -8.308594 7.203125 -7.632812 7.203125 -6.890625 C 7.203125 -6.105469 6.929688 -5.4375 6.378906 -4.882812 C 6.058594 -4.558594 5.488281 -4.164062 4.664062 -3.703125 L 3.726562 -3.1875 C 3.28125 -2.941406 2.929688 -2.703125 2.671875 -2.480469 C 2.21875 -2.085938 1.929688 -1.644531 1.8125 -1.164062 L 7.15625 -1.164062 L 7.15625 0 L 0.4375 0 C 0.484375 -0.84375 0.65625 -1.578125 0.960938 -2.203125 Z M 0.960938 -2.203125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.117188 -0.6875 C 0.59375 -1.324219 0.335938 -2.097656 0.335938 -3.007812 L 1.621094 -3.007812 C 1.675781 -2.375 1.792969 -1.914062 1.976562 -1.625 C 2.296875 -1.109375 2.871094 -0.855469 3.703125 -0.855469 C 4.351562 -0.855469 4.871094 -1.027344 5.265625 -1.375 C 5.65625 -1.71875 5.851562 -2.167969 5.851562 -2.714844 C 5.851562 -3.390625 5.644531 -3.859375 5.234375 -4.128906 C 4.820312 -4.398438 4.246094 -4.53125 3.515625 -4.53125 C 3.433594 -4.53125 3.347656 -4.53125 3.265625 -4.527344 C 3.179688 -4.527344 3.09375 -4.523438 3.007812 -4.519531 L 3.007812 -5.605469 C 3.136719 -5.59375 3.242188 -5.582031 3.328125 -5.578125 C 3.414062 -5.574219 3.507812 -5.570312 3.609375 -5.570312 C 4.070312 -5.570312 4.449219 -5.644531 4.742188 -5.789062 C 5.261719 -6.046875 5.523438 -6.5 5.523438 -7.15625 C 5.523438 -7.644531 5.351562 -8.019531 5.003906 -8.285156 C 4.65625 -8.550781 4.253906 -8.679688 3.792969 -8.679688 C 2.972656 -8.679688 2.40625 -8.40625 2.09375 -7.859375 C 1.917969 -7.558594 1.820312 -7.132812 1.796875 -6.578125 L 0.582031 -6.578125 C 0.582031 -7.304688 0.726562 -7.925781 1.019531 -8.4375 C 1.519531 -9.347656 2.402344 -9.804688 3.664062 -9.804688 C 4.664062 -9.804688 5.433594 -9.582031 5.980469 -9.136719 C 6.527344 -8.691406 6.800781 -8.046875 6.800781 -7.203125 C 6.800781 -6.601562 6.640625 -6.117188 6.316406 -5.742188 C 6.117188 -5.507812 5.855469 -5.328125 5.539062 -5.195312 C 6.054688 -5.054688 6.453125 -4.78125 6.742188 -4.378906 C 7.03125 -3.976562 7.179688 -3.480469 7.179688 -2.898438 C 7.179688 -1.964844 6.871094 -1.203125 6.253906 -0.617188 C 5.640625 -0.0273438 4.765625 0.265625 3.636719 0.265625 C 2.480469 0.265625 1.640625 -0.0507812 1.117188 -0.6875 Z M 1.117188 -0.6875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.484375 -2.140625 C 1.554688 -1.539062 1.832031 -1.121094 2.320312 -0.890625 C 2.570312 -0.773438 2.859375 -0.714844 3.1875 -0.714844 C 3.8125 -0.714844 4.273438 -0.914062 4.578125 -1.3125 C 4.878906 -1.710938 5.027344 -2.152344 5.027344 -2.636719 C 5.027344 -3.222656 4.847656 -3.675781 4.492188 -3.996094 C 4.132812 -4.316406 3.703125 -4.476562 3.203125 -4.476562 C 2.839844 -4.476562 2.53125 -4.40625 2.269531 -4.265625 C 2.011719 -4.125 1.789062 -3.929688 1.605469 -3.679688 L 0.691406 -3.734375 L 1.328125 -8.25 L 5.6875 -8.25 L 5.6875 -7.230469 L 2.121094 -7.230469 L 1.765625 -4.898438 C 1.960938 -5.046875 2.144531 -5.15625 2.320312 -5.234375 C 2.632812 -5.363281 2.992188 -5.425781 3.40625 -5.425781 C 4.175781 -5.425781 4.828125 -5.179688 5.359375 -4.679688 C 5.894531 -4.183594 6.164062 -3.554688 6.164062 -2.796875 C 6.164062 -2.003906 5.917969 -1.304688 5.429688 -0.695312 C 4.9375 -0.0898438 4.15625 0.210938 3.082031 0.210938 C 2.398438 0.210938 1.792969 0.0195312 1.269531 -0.367188 C 0.742188 -0.75 0.449219 -1.34375 0.386719 -2.140625 Z M 1.484375 -2.140625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.023438 -1.277344 L 2.25 -1.277344 L 2.25 0 L 1.023438 0 Z M 1.023438 -1.277344 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 5.601562 -7.046875 C 5.976562 -6.355469 6.164062 -5.410156 6.164062 -4.207031 C 6.164062 -3.066406 5.992188 -2.125 5.65625 -1.375 C 5.164062 -0.304688 4.359375 0.226562 3.242188 0.226562 C 2.234375 0.226562 1.484375 -0.210938 0.992188 -1.085938 C 0.582031 -1.816406 0.375 -2.796875 0.375 -4.023438 C 0.375 -4.976562 0.5 -5.796875 0.742188 -6.480469 C 1.203125 -7.753906 2.039062 -8.390625 3.246094 -8.390625 C 4.332031 -8.390625 5.117188 -7.945312 5.601562 -7.046875 Z M 4.539062 -1.460938 C 4.863281 -1.945312 5.027344 -2.84375 5.027344 -4.164062 C 5.027344 -5.117188 4.910156 -5.902344 4.675781 -6.519531 C 4.441406 -7.132812 3.984375 -7.441406 3.3125 -7.441406 C 2.691406 -7.441406 2.234375 -7.148438 1.949219 -6.566406 C 1.660156 -5.980469 1.515625 -5.121094 1.515625 -3.984375 C 1.515625 -3.128906 1.609375 -2.441406 1.792969 -1.921875 C 2.074219 -1.128906 2.554688 -0.734375 3.234375 -0.734375 C 3.78125 -0.734375 4.21875 -0.976562 4.539062 -1.460938 Z M 4.539062 -1.460938 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.824219 -1.886719 C 1.082031 -2.421875 1.589844 -2.90625 2.34375 -3.34375 L 3.46875 -3.996094 C 3.972656 -4.289062 4.328125 -4.539062 4.53125 -4.746094 C 4.851562 -5.070312 5.007812 -5.441406 5.007812 -5.859375 C 5.007812 -6.347656 4.863281 -6.734375 4.570312 -7.023438 C 4.277344 -7.308594 3.886719 -7.453125 3.398438 -7.453125 C 2.675781 -7.453125 2.175781 -7.179688 1.898438 -6.632812 C 1.75 -6.339844 1.667969 -5.933594 1.652344 -5.414062 L 0.578125 -5.414062 C 0.589844 -6.144531 0.726562 -6.742188 0.984375 -7.203125 C 1.441406 -8.015625 2.25 -8.421875 3.40625 -8.421875 C 4.367188 -8.421875 5.066406 -8.160156 5.511719 -7.640625 C 5.953125 -7.121094 6.175781 -6.542969 6.175781 -5.90625 C 6.175781 -5.234375 5.9375 -4.660156 5.46875 -4.183594 C 5.195312 -3.90625 4.703125 -3.570312 3.996094 -3.175781 L 3.195312 -2.730469 C 2.8125 -2.519531 2.507812 -2.320312 2.289062 -2.125 C 1.898438 -1.785156 1.65625 -1.410156 1.554688 -0.996094 L 6.132812 -0.996094 L 6.132812 0 L 0.375 0 C 0.414062 -0.722656 0.5625 -1.351562 0.824219 -1.886719 Z M 0.824219 -1.886719 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 6.273438 -8.25 L 6.273438 -7.328125 C 6.003906 -7.066406 5.648438 -6.613281 5.199219 -5.964844 C 4.753906 -5.316406 4.359375 -4.617188 4.015625 -3.867188 C 3.675781 -3.136719 3.414062 -2.46875 3.242188 -1.867188 C 3.128906 -1.480469 2.980469 -0.859375 2.800781 0 L 1.632812 0 C 1.898438 -1.601562 2.484375 -3.195312 3.390625 -4.78125 C 3.925781 -5.710938 4.492188 -6.515625 5.078125 -7.1875 L 0.4375 -7.1875 L 0.4375 -8.25 Z M 6.273438 -8.25 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface2\">\n",
       "<rect x=\"0\" y=\"0\" width=\"300\" height=\"300\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 94.046875 10 L 209.3125 290 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 94.046875 10 L 290 82.480469 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 94.046875 10 L 10 208.695312 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 209.3125 290 L 290 82.480469 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 209.3125 290 L 10 208.695312 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(26.666667%,26.666667%,26.666667%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 290 82.480469 L 10 208.695312 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 104.046875 10 C 104.046875 15.523438 99.570312 20 94.046875 20 C 88.523438 20 84.046875 15.523438 84.046875 10 C 84.046875 4.476562 88.523438 0 94.046875 0 C 99.570312 0 104.046875 4.476562 104.046875 10 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 219.3125 290 C 219.3125 295.523438 214.835938 300 209.3125 300 C 203.789062 300 199.3125 295.523438 199.3125 290 C 199.3125 284.476562 203.789062 280 209.3125 280 C 214.835938 280 219.3125 284.476562 219.3125 290 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 300 82.480469 C 300 88.003906 295.523438 92.480469 290 92.480469 C 284.476562 92.480469 280 88.003906 280 82.480469 C 280 76.960938 284.476562 72.480469 290 72.480469 C 295.523438 72.480469 300 76.960938 300 82.480469 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 20 208.695312 C 20 214.21875 15.523438 218.695312 10 218.695312 C 4.476562 218.695312 0 214.21875 0 208.695312 C 0 203.171875 4.476562 198.695312 10 198.695312 C 15.523438 198.695312 20 203.171875 20 208.695312 \"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"90.230469\" y=\"16.503906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"206.164062\" y=\"296.484375\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-3\" x=\"286.179688\" y=\"89.003906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-4\" x=\"6.242188\" y=\"215.207031\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"151.292969\" y=\"155.574219\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"157.966797\" y=\"155.574219\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"161.300781\" y=\"155.574219\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-4\" x=\"191.648438\" y=\"41.210938\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"198.322266\" y=\"41.210938\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"204.996094\" y=\"41.210938\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"208.330078\" y=\"41.210938\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"51.636719\" y=\"114.921875\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"58.310547\" y=\"114.921875\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"61.644531\" y=\"114.921875\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"233.484375\" y=\"191.816406\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"240.158203\" y=\"191.816406\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"243.492188\" y=\"191.816406\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-4\" x=\"93.484375\" y=\"261.347656\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"100.158203\" y=\"261.347656\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"103.492188\" y=\"261.347656\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-5\" x=\"149.5625\" y=\"157.589844\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"156.236328\" y=\"157.589844\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"159.570312\" y=\"157.589844\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x11cd0db50>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# In this piece of code we load the necessary packages, ROOT, igraph\n",
    "# We also define vector2d_from_list which transforms a python list of lists\n",
    "# to a C++ vector\n",
    "# Additionally, we create a toy graph of cities represented by distgraph\n",
    "# and we visualize it using igraph\n",
    "\n",
    "from __future__ import division\n",
    "\n",
    "import ROOT\n",
    "import igraph\n",
    "\n",
    "distgraph = [\n",
    "    [0,5,20,5],\n",
    "    [5,0,5,2],\n",
    "    [20,5,0,7],\n",
    "    [5,2,7,0]\n",
    "]\n",
    "\n",
    "from ROOT import std\n",
    "\n",
    "dg = std.vector('std::vector<double>')()\n",
    "\n",
    "def vector2d_from_list(lst):\n",
    "    ret = std.vector('std::vector<double>')()\n",
    "    for row in distgraph:\n",
    "        temp = std.vector('double')()\n",
    "        for col in row:\n",
    "            temp.push_back(col)\n",
    "        ret.push_back(temp);\n",
    "    return(ret)\n",
    "        \n",
    "\n",
    "g = igraph.Graph.Weighted_Adjacency(distgraph, mode = igraph.ADJ_MAX, loops = False, attr = \"weight\")\n",
    "g.vs['label'] = range(len(distgraph))\n",
    "igraph.plot(g, labels = True, edge_label=g.es[\"weight\"], bbox = (300,300), margin = 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This statement is needed for C++ to work subsequently\r\n"
     ]
    }
   ],
   "source": [
    "\n",
    "%%cpp\n",
    "\n",
    "std::cout << \"This statement is needed for C++ to work subsequently\" << std::endl;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "%%cpp -d\n",
    "// Here define a function that prints a 2d C++ vector\n",
    "// and we test it using distgraph (we transform it to C++ and print it)\n",
    "// The \"cpp -d\" magic is provided by ROOT to have C++ in the notebook\n",
    "void print_vector2d(const std::vector<std::vector<double> >& v)\n",
    "        {\n",
    "            for (const auto& row:v){\n",
    "                for (const auto& col:row) {\n",
    "                    std::cout << col << \" \";\n",
    "                }\n",
    "                std::cout << endl;\n",
    "            }\n",
    "        }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 5 20 5 \r\n",
      "5 0 5 2 \r\n",
      "20 5 0 7 \r\n",
      "5 2 7 0 \r\n"
     ]
    }
   ],
   "source": [
    "ROOT.print_vector2d(vector2d_from_list(distgraph))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Here we define the initial value of the\n",
    "# pheromone (the attraction factor) as\n",
    "# inversely proposional to the size of our graph\n",
    "# (the number of our cities)\n",
    "init_pherom = 1/len(distgraph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Here we initialize the pheromone matrix to the initial\n",
    "# value of the pheromone\n",
    "pheromones = [\n",
    "    [(init_pherom if x!=y else 0.0) for x in range(len(distgraph))] \n",
    "              for y in range(len(distgraph))\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0.0, 0.25, 0.25, 0.25],\n",
       " [0.25, 0.0, 0.25, 0.25],\n",
       " [0.25, 0.25, 0.0, 0.25],\n",
       " [0.25, 0.25, 0.25, 0.0]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pheromones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0.0, 0.25, 0.25, 0.25],\n",
       " [0.25, 0.0, 0.25, 0.25],\n",
       " [0.25, 0.25, 0.0, 0.25],\n",
       " [0.25, 0.25, 0.25, 0.0]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pheromones\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ant Logic\n",
    "\n",
    "Each ant selects the arc to follow with the following probability $$p_{ij}=\\frac{\\eta_{ij}^\\beta \\tau_{ij}^\\alpha}{\\sum\\limits_{k}\\eta_{ij}^\\alpha \\tau_{ij}^\\beta}$$\n",
    "\n",
    "where<br>\n",
    "      $p_{ij}$ is the probability to select the edge $(i,j)$<br>\n",
    "      $\\eta_{ij}$ is a heuristic function for edge $(i,j)$<br>\n",
    "      $\\tau_{ij}$ is the pheromone of edge $(i,j)$<br>\n",
    "      $\\alpha$ is the weight we give to the pheromone<br>\n",
    "      $\\beta$ is the weight we give to the heuristic function<br>\n",
    "      \n",
    "Here as a heuristic we use the inverse of distance $\\eta_{ij}=\\frac{1}{d_{ij}}$\n",
    "          \n",
    "Here we define the settings as a list with [$\\alpha$, $\\beta$, $\\rho$, QVAL]. \n",
    "The parameters that we use from experimental evidence are $\\alpha$ = 1.0, $\\beta$ = 5.0, $\\rho$ = 0.5, $QVAL$ = 100.\n",
    "The last 2 parameters will be explained in a next section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%%cpp -d\n",
    "#include <vector>\n",
    "#include <cmath>\n",
    "#include <random>\n",
    "#include <cassert>\n",
    "\n",
    "/**\n",
    " This class represents the logic for the movement of an ant\n",
    " An Ant needs to be provided:\n",
    " the city from which it will start (initCity)\n",
    " the pheromones (pheromones)\n",
    " the distance matrix that represents the graph of the cities (distgraph)\n",
    " \n",
    " After the ant has run (Ant::run)\n",
    " we can get:\n",
    " the path that it followed (builtPath)\n",
    " the length of the path (tourLength)\n",
    "*/\n",
    "class Ant {\n",
    "    int initCity;\n",
    "    std::vector<std::vector<double> >* pheromones;\n",
    "    std::vector<std::vector<double> >* dist;\n",
    "    std::vector<unsigned char> visited{};\n",
    "\n",
    "public:\n",
    "    std::vector<double> settings{1.0, 5.0, 0.5, 100};\n",
    "    double tourLength;\n",
    "    std::vector<int> builtPath{};\n",
    "\n",
    "    int getInitCity() const\n",
    "    {\n",
    "        return initCity;\n",
    "    }\n",
    "\n",
    "    void setInitCity(int initCity)\n",
    "    {\n",
    "        Ant::initCity = initCity;\n",
    "        std::fill(std::begin(visited), std::end(visited), 0);\n",
    "        visited[initCity] = 1;\n",
    "    }\n",
    "\n",
    "    Ant(int city, std::vector<std::vector<double> >* pherom, std::vector<std::vector<double> >* distgraph)\n",
    "            :initCity(city), pheromones(pherom), dist(distgraph)\n",
    "    {\n",
    "        visited.resize(dist->size());\n",
    "        visited[city] = 1;\n",
    "    }\n",
    "\n",
    "    /**\n",
    "    This function returns the probability that the Ant will follow the edge (from, to)\n",
    "    */\n",
    "    double prob(int from, int to)\n",
    "    {\n",
    "        double nom = (std::pow(1/(*dist)[from][to], settings[1])*std::pow((*pheromones)[from][to], settings[0]));\n",
    "        double denom = 0.0;\n",
    "        for (int i = 0; i<visited.size(); ++i) {\n",
    "            if (visited[i]==0) {\n",
    "                denom += (std::pow(1/(*dist)[from][i], settings[1])*std::pow((*pheromones)[from][i], settings[0]));\n",
    "            }\n",
    "        }\n",
    "        if (denom>0.00001) {\n",
    "            return nom/denom;\n",
    "        }\n",
    "        else {\n",
    "            return 1.0;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "    Here is the main logic of the ant\n",
    "    It builds a path according to the probability defined above prob(from, to)\n",
    "    After running it, builtPath contains the indexes of the nodes visited and\n",
    "    tourLength its length\n",
    "    */\n",
    "    double run()\n",
    "    {\n",
    "        int visitNum = 0;\n",
    "        int size = dist->size();\n",
    "        int curCity = initCity;\n",
    "        std::random_device rand;\n",
    "        double tourLen = 0.0;\n",
    "        visited.clear();\n",
    "        visited.resize(size);\n",
    "        visited[curCity] = 1;\n",
    "        builtPath.clear();\n",
    "        builtPath.resize(size);\n",
    "        builtPath[visitNum] = curCity;\n",
    "        while (visitNum<(size-1)) {\n",
    "\n",
    "            double probNum;\n",
    "            double visitProb;\n",
    "            int index;\n",
    "\n",
    "            index = curCity;\n",
    "            do {\n",
    "                ++index;\n",
    "                if (index>=size) {\n",
    "                    index = 0;\n",
    "                }\n",
    "                if (visited[index]) {\n",
    "                    visitProb = 0;\n",
    "                }\n",
    "                else {\n",
    "                    visitProb = prob(curCity, index);\n",
    "                }\n",
    "                probNum = static_cast<double>(rand())/rand.max();\n",
    "            }\n",
    "            while (probNum>visitProb);\n",
    "            tourLen += (*dist)[curCity][index];\n",
    "            curCity = index;\n",
    "            visited[index] = 1;\n",
    "            visitNum++;\n",
    "            builtPath[visitNum] = curCity;\n",
    "        }\n",
    "        tourLen += (*dist)[curCity][initCity];\n",
    "        tourLength = tourLen;\n",
    "        return tourLen;\n",
    "    }\n",
    "\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ant Colony Optimization (ACO) logic\n",
    "\n",
    "The Ant Colony Optimization that we use here places ants in each node of the graph and lets them build their paths. Then it updates the pheromones of the edges.\n",
    "\n",
    "Each ant $k$ contributes $$\\Delta\\tau_{ij}^k(t) = \\frac{QVAL}{L^k(t)}$$ pheromone, where $QVAL$ is a parameter that in our case we have set to 100 and $L^k(t)$ is the tour length of ant $k$.\n",
    "\n",
    "The actual update of the pheromone $\\tau_{ij}$ on edge $(i,j)$ allowed by ACO is $$\\tau_{ij}=\\tau_{ij}+(\\Delta\\tau_{ij}^k(t) * \\rho)$$ where $\\rho$ is a parameter between 0.0 and 1.0 that controls the amount of evaporation and the strength of the previous parameter. Finally, the pheromones evaporate according to the equation $$\\tau_{ij} = \\tau_{ij}*(1-\\rho)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "%%cpp -d\n",
    "\n",
    "/**\n",
    "This class implements the main logic of the Ant Colony Optimization (ACO)\n",
    "The user can set the settings in the order (alpha, beta, rho, QVAL).\n",
    "The graph in the format of a distance matrix (distgraph) must be provided, and also\n",
    "the user can set the number of iterations and the number of ants used. If the number\n",
    "of iterations is not set, 10 iterations are done and if the ants are not provided, ants\n",
    "equal to the number of nodes are used.\n",
    "\n",
    "After ACO is ran (ACO::run) we can retrieve the best path (getBestPath)\n",
    "and the cost (bestCost)\n",
    "*/\n",
    "class ACO {\n",
    "private:\n",
    "    std::vector<std::vector<double> > dist;\n",
    "    std::vector<std::vector<double> > pheromones{{}};\n",
    "\n",
    "    std::vector<int> bestPath{};\n",
    "public:\n",
    "    std::vector<double> settings{1.0, 5.0, 0.5, 100};\n",
    "    int numAnts = -1;\n",
    "    int maxIter;\n",
    "    double bestCost;\n",
    "\n",
    "    const std::vector<int>& getBestPath() const\n",
    "    {\n",
    "        return bestPath;\n",
    "    }\n",
    "\n",
    "    ACO(std::vector<std::vector<double> > distgraph, int iters = 10, int numAnt = -1)\n",
    "            :dist(distgraph), numAnts(numAnt), maxIter(iters) { if (numAnt==-1) numAnts = dist.size(); }\n",
    "\n",
    "    /**\n",
    "    Here the main logic is implemented\n",
    "    First the pheromones are initialized with init_pheromone value\n",
    "    and then we place one ant in each city and we let them\n",
    "    build their paths. Afterwards we update the pheromones and\n",
    "    finally evaporate them\n",
    "    */\n",
    "    double run()\n",
    "    {\n",
    "        double size = dist.size();\n",
    "        assert(size>0);\n",
    "        double init_pheromone = 1/size;\n",
    "        pheromones.resize(size);\n",
    "        for (int i = 0; i<size; ++i) {\n",
    "            pheromones[i].resize(size);\n",
    "        }\n",
    "        for (int i = 0; i<size; ++i) {\n",
    "            for (int j = i+1; j<size; ++j) {\n",
    "                pheromones[i][j] = init_pheromone;\n",
    "                pheromones[j][i] = init_pheromone;\n",
    "            }\n",
    "        }\n",
    "        bestCost = std::numeric_limits<double>::max();\n",
    "\n",
    "        for (int i = 0; i<maxIter; ++i) {\n",
    "            std::vector<Ant> ants(numAnts, {0, &pheromones, &dist});\n",
    "            int index = 0;\n",
    "            // Run ants\n",
    "            for (auto& ant:ants) {\n",
    "                ant.setInitCity(index);\n",
    "                ant.settings = settings;\n",
    "                double curCost = ant.run();\n",
    "                if (curCost<=bestCost) {\n",
    "                    bestCost = curCost;\n",
    "                    bestPath = ant.builtPath;\n",
    "                }\n",
    "                if (++index>=size) index = 0;\n",
    "            }\n",
    "            // Update pheromones\n",
    "            for (const auto& ant:ants) {\n",
    "                for (int i = 0; i<size; ++i) {\n",
    "                    int from = i;\n",
    "                    int to = i + 1;\n",
    "                    if ((i+1) == size) {\n",
    "                        to = 0;\n",
    "                    }\n",
    "                    int antFrom = ant.builtPath[from];\n",
    "                    int antTo = ant.builtPath[to];\n",
    "                    pheromones[antFrom][antTo] += (settings[2] * (settings[3]/ant.tourLength));\n",
    "                    pheromones[antTo][antFrom] = pheromones[antFrom][antTo];\n",
    "                }\n",
    "            }\n",
    "\n",
    "            // Evaporate\n",
    "            for (int i = 0; i<size; ++i) {\n",
    "                for (int j = 0; j<size; ++j) {\n",
    "                    pheromones[i][j] *= settings[2];\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        return bestCost;\n",
    "\n",
    "    }\n",
    "\n",
    "\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "aco = ROOT.ACO(vector2d_from_list(distgraph), 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "c = aco.run()"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "print c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aco.bestCost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p = aco.getBestPath()"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "print list(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<ROOT.vector<int> object at 0x7faf26b3edd0>\n"
     ]
    }
   ],
   "source": [
    "print p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 0]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 0]\n"
     ]
    }
   ],
   "source": [
    "print list(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300pt\" height=\"300pt\" viewBox=\"0 0 300 300\" version=\"1.1\">\n",
       "<defs>\n",
       "<g>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 6.535156 -8.222656 C 6.972656 -7.417969 7.191406 -6.3125 7.191406 -4.90625 C 7.191406 -3.578125 6.992188 -2.476562 6.597656 -1.605469 C 6.023438 -0.359375 5.082031 0.265625 3.78125 0.265625 C 2.605469 0.265625 1.730469 -0.242188 1.15625 -1.265625 C 0.675781 -2.117188 0.4375 -3.261719 0.4375 -4.695312 C 0.4375 -5.808594 0.582031 -6.761719 0.867188 -7.5625 C 1.40625 -9.046875 2.378906 -9.789062 3.789062 -9.789062 C 5.054688 -9.789062 5.96875 -9.265625 6.535156 -8.222656 Z M 5.296875 -1.703125 C 5.675781 -2.265625 5.867188 -3.320312 5.867188 -4.859375 C 5.867188 -5.972656 5.726562 -6.886719 5.453125 -7.605469 C 5.179688 -8.324219 4.652344 -8.679688 3.863281 -8.679688 C 3.136719 -8.679688 2.609375 -8.339844 2.273438 -7.660156 C 1.9375 -6.976562 1.769531 -5.976562 1.769531 -4.648438 C 1.769531 -3.648438 1.878906 -2.847656 2.09375 -2.242188 C 2.421875 -1.316406 2.980469 -0.855469 3.773438 -0.855469 C 4.410156 -0.855469 4.917969 -1.136719 5.296875 -1.703125 Z M 5.296875 -1.703125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.339844 -6.929688 L 1.339844 -7.875 C 2.226562 -7.960938 2.847656 -8.105469 3.199219 -8.308594 C 3.550781 -8.511719 3.8125 -8.992188 3.984375 -9.75 L 4.957031 -9.75 L 4.957031 0 L 3.644531 0 L 3.644531 -6.929688 Z M 1.339844 -6.929688 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.960938 -2.203125 C 1.265625 -2.828125 1.855469 -3.394531 2.734375 -3.902344 L 4.046875 -4.664062 C 4.632812 -5.003906 5.046875 -5.296875 5.285156 -5.539062 C 5.65625 -5.914062 5.84375 -6.347656 5.84375 -6.835938 C 5.84375 -7.40625 5.671875 -7.859375 5.332031 -8.191406 C 4.992188 -8.527344 4.535156 -8.695312 3.964844 -8.695312 C 3.121094 -8.695312 2.539062 -8.375 2.214844 -7.738281 C 2.042969 -7.398438 1.945312 -6.921875 1.929688 -6.316406 L 0.675781 -6.316406 C 0.691406 -7.167969 0.847656 -7.863281 1.148438 -8.402344 C 1.679688 -9.351562 2.621094 -9.824219 3.972656 -9.824219 C 5.09375 -9.824219 5.910156 -9.519531 6.429688 -8.914062 C 6.945312 -8.308594 7.203125 -7.632812 7.203125 -6.890625 C 7.203125 -6.105469 6.929688 -5.4375 6.378906 -4.882812 C 6.058594 -4.558594 5.488281 -4.164062 4.664062 -3.703125 L 3.726562 -3.1875 C 3.28125 -2.941406 2.929688 -2.703125 2.671875 -2.480469 C 2.21875 -2.085938 1.929688 -1.644531 1.8125 -1.164062 L 7.15625 -1.164062 L 7.15625 0 L 0.4375 0 C 0.484375 -0.84375 0.65625 -1.578125 0.960938 -2.203125 Z M 0.960938 -2.203125 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph0-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.117188 -0.6875 C 0.59375 -1.324219 0.335938 -2.097656 0.335938 -3.007812 L 1.621094 -3.007812 C 1.675781 -2.375 1.792969 -1.914062 1.976562 -1.625 C 2.296875 -1.109375 2.871094 -0.855469 3.703125 -0.855469 C 4.351562 -0.855469 4.871094 -1.027344 5.265625 -1.375 C 5.65625 -1.71875 5.851562 -2.167969 5.851562 -2.714844 C 5.851562 -3.390625 5.644531 -3.859375 5.234375 -4.128906 C 4.820312 -4.398438 4.246094 -4.53125 3.515625 -4.53125 C 3.433594 -4.53125 3.347656 -4.53125 3.265625 -4.527344 C 3.179688 -4.527344 3.09375 -4.523438 3.007812 -4.519531 L 3.007812 -5.605469 C 3.136719 -5.59375 3.242188 -5.582031 3.328125 -5.578125 C 3.414062 -5.574219 3.507812 -5.570312 3.609375 -5.570312 C 4.070312 -5.570312 4.449219 -5.644531 4.742188 -5.789062 C 5.261719 -6.046875 5.523438 -6.5 5.523438 -7.15625 C 5.523438 -7.644531 5.351562 -8.019531 5.003906 -8.285156 C 4.65625 -8.550781 4.253906 -8.679688 3.792969 -8.679688 C 2.972656 -8.679688 2.40625 -8.40625 2.09375 -7.859375 C 1.917969 -7.558594 1.820312 -7.132812 1.796875 -6.578125 L 0.582031 -6.578125 C 0.582031 -7.304688 0.726562 -7.925781 1.019531 -8.4375 C 1.519531 -9.347656 2.402344 -9.804688 3.664062 -9.804688 C 4.664062 -9.804688 5.433594 -9.582031 5.980469 -9.136719 C 6.527344 -8.691406 6.800781 -8.046875 6.800781 -7.203125 C 6.800781 -6.601562 6.640625 -6.117188 6.316406 -5.742188 C 6.117188 -5.507812 5.855469 -5.328125 5.539062 -5.195312 C 6.054688 -5.054688 6.453125 -4.78125 6.742188 -4.378906 C 7.03125 -3.976562 7.179688 -3.480469 7.179688 -2.898438 C 7.179688 -1.964844 6.871094 -1.203125 6.253906 -0.617188 C 5.640625 -0.0273438 4.765625 0.265625 3.636719 0.265625 C 2.480469 0.265625 1.640625 -0.0507812 1.117188 -0.6875 Z M 1.117188 -0.6875 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-0\">\n",
       "<path style=\"stroke:none;\" d=\"\"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-1\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.484375 -2.140625 C 1.554688 -1.539062 1.832031 -1.121094 2.320312 -0.890625 C 2.570312 -0.773438 2.859375 -0.714844 3.1875 -0.714844 C 3.8125 -0.714844 4.273438 -0.914062 4.578125 -1.3125 C 4.878906 -1.710938 5.027344 -2.152344 5.027344 -2.636719 C 5.027344 -3.222656 4.847656 -3.675781 4.492188 -3.996094 C 4.132812 -4.316406 3.703125 -4.476562 3.203125 -4.476562 C 2.839844 -4.476562 2.53125 -4.40625 2.269531 -4.265625 C 2.011719 -4.125 1.789062 -3.929688 1.605469 -3.679688 L 0.691406 -3.734375 L 1.328125 -8.25 L 5.6875 -8.25 L 5.6875 -7.230469 L 2.121094 -7.230469 L 1.765625 -4.898438 C 1.960938 -5.046875 2.144531 -5.15625 2.320312 -5.234375 C 2.632812 -5.363281 2.992188 -5.425781 3.40625 -5.425781 C 4.175781 -5.425781 4.828125 -5.179688 5.359375 -4.679688 C 5.894531 -4.183594 6.164062 -3.554688 6.164062 -2.796875 C 6.164062 -2.003906 5.917969 -1.304688 5.429688 -0.695312 C 4.9375 -0.0898438 4.15625 0.210938 3.082031 0.210938 C 2.398438 0.210938 1.792969 0.0195312 1.269531 -0.367188 C 0.742188 -0.75 0.449219 -1.34375 0.386719 -2.140625 Z M 1.484375 -2.140625 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-2\">\n",
       "<path style=\"stroke:none;\" d=\"M 1.023438 -1.277344 L 2.25 -1.277344 L 2.25 0 L 1.023438 0 Z M 1.023438 -1.277344 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-3\">\n",
       "<path style=\"stroke:none;\" d=\"M 5.601562 -7.046875 C 5.976562 -6.355469 6.164062 -5.410156 6.164062 -4.207031 C 6.164062 -3.066406 5.992188 -2.125 5.65625 -1.375 C 5.164062 -0.304688 4.359375 0.226562 3.242188 0.226562 C 2.234375 0.226562 1.484375 -0.210938 0.992188 -1.085938 C 0.582031 -1.816406 0.375 -2.796875 0.375 -4.023438 C 0.375 -4.976562 0.5 -5.796875 0.742188 -6.480469 C 1.203125 -7.753906 2.039062 -8.390625 3.246094 -8.390625 C 4.332031 -8.390625 5.117188 -7.945312 5.601562 -7.046875 Z M 4.539062 -1.460938 C 4.863281 -1.945312 5.027344 -2.84375 5.027344 -4.164062 C 5.027344 -5.117188 4.910156 -5.902344 4.675781 -6.519531 C 4.441406 -7.132812 3.984375 -7.441406 3.3125 -7.441406 C 2.691406 -7.441406 2.234375 -7.148438 1.949219 -6.566406 C 1.660156 -5.980469 1.515625 -5.121094 1.515625 -3.984375 C 1.515625 -3.128906 1.609375 -2.441406 1.792969 -1.921875 C 2.074219 -1.128906 2.554688 -0.734375 3.234375 -0.734375 C 3.78125 -0.734375 4.21875 -0.976562 4.539062 -1.460938 Z M 4.539062 -1.460938 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-4\">\n",
       "<path style=\"stroke:none;\" d=\"M 0.824219 -1.886719 C 1.082031 -2.421875 1.589844 -2.90625 2.34375 -3.34375 L 3.46875 -3.996094 C 3.972656 -4.289062 4.328125 -4.539062 4.53125 -4.746094 C 4.851562 -5.070312 5.007812 -5.441406 5.007812 -5.859375 C 5.007812 -6.347656 4.863281 -6.734375 4.570312 -7.023438 C 4.277344 -7.308594 3.886719 -7.453125 3.398438 -7.453125 C 2.675781 -7.453125 2.175781 -7.179688 1.898438 -6.632812 C 1.75 -6.339844 1.667969 -5.933594 1.652344 -5.414062 L 0.578125 -5.414062 C 0.589844 -6.144531 0.726562 -6.742188 0.984375 -7.203125 C 1.441406 -8.015625 2.25 -8.421875 3.40625 -8.421875 C 4.367188 -8.421875 5.066406 -8.160156 5.511719 -7.640625 C 5.953125 -7.121094 6.175781 -6.542969 6.175781 -5.90625 C 6.175781 -5.234375 5.9375 -4.660156 5.46875 -4.183594 C 5.195312 -3.90625 4.703125 -3.570312 3.996094 -3.175781 L 3.195312 -2.730469 C 2.8125 -2.519531 2.507812 -2.320312 2.289062 -2.125 C 1.898438 -1.785156 1.65625 -1.410156 1.554688 -0.996094 L 6.132812 -0.996094 L 6.132812 0 L 0.375 0 C 0.414062 -0.722656 0.5625 -1.351562 0.824219 -1.886719 Z M 0.824219 -1.886719 \"/>\n",
       "</symbol>\n",
       "<symbol overflow=\"visible\" id=\"glyph1-5\">\n",
       "<path style=\"stroke:none;\" d=\"M 6.273438 -8.25 L 6.273438 -7.328125 C 6.003906 -7.066406 5.648438 -6.613281 5.199219 -5.964844 C 4.753906 -5.316406 4.359375 -4.617188 4.015625 -3.867188 C 3.675781 -3.136719 3.414062 -2.46875 3.242188 -1.867188 C 3.128906 -1.480469 2.980469 -0.859375 2.800781 0 L 1.632812 0 C 1.898438 -1.601562 2.484375 -3.195312 3.390625 -4.78125 C 3.925781 -5.710938 4.492188 -6.515625 5.078125 -7.1875 L 0.4375 -7.1875 L 0.4375 -8.25 Z M 6.273438 -8.25 \"/>\n",
       "</symbol>\n",
       "</g>\n",
       "</defs>\n",
       "<g id=\"surface8\">\n",
       "<rect x=\"0\" y=\"0\" width=\"300\" height=\"300\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;\"/>\n",
       "<path style=\"fill:none;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(74.509804%,74.509804%,74.509804%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 46.277344 290 L 10 38.96875 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 46.277344 290 L 263.808594 10 \"/>\n",
       "<path style=\"fill:none;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(74.509804%,74.509804%,74.509804%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 46.277344 290 L 290 245.855469 \"/>\n",
       "<path style=\"fill:none;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(74.509804%,74.509804%,74.509804%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 10 38.96875 L 263.808594 10 \"/>\n",
       "<path style=\"fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 10 38.96875 L 290 245.855469 \"/>\n",
       "<path style=\"fill:none;stroke-width:5;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(74.509804%,74.509804%,74.509804%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 263.808594 10 L 290 245.855469 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 56.277344 290 C 56.277344 295.523438 51.800781 300 46.277344 300 C 40.753906 300 36.277344 295.523438 36.277344 290 C 36.277344 284.476562 40.753906 280 46.277344 280 C 51.800781 280 56.277344 284.476562 56.277344 290 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 20 38.96875 C 20 44.492188 15.523438 48.96875 10 48.96875 C 4.476562 48.96875 0 44.492188 0 38.96875 C 0 33.445312 4.476562 28.96875 10 28.96875 C 15.523438 28.96875 20 33.445312 20 38.96875 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 273.808594 10 C 273.808594 15.523438 269.332031 20 263.808594 20 C 258.285156 20 253.808594 15.523438 253.808594 10 C 253.808594 4.476562 258.285156 0 263.808594 0 C 269.332031 0 273.808594 4.476562 273.808594 10 \"/>\n",
       "<path style=\"fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;\" d=\"M 300 245.855469 C 300 251.378906 295.523438 255.855469 290 255.855469 C 284.476562 255.855469 280 251.378906 280 245.855469 C 280 240.332031 284.476562 235.855469 290 235.855469 C 295.523438 235.855469 300 240.332031 300 245.855469 \"/>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-1\" x=\"42.464844\" y=\"296.503906\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-2\" x=\"6.851562\" y=\"45.453125\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-3\" x=\"259.988281\" y=\"16.523438\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph0-4\" x=\"286.242188\" y=\"252.367188\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"11.96875\" y=\"170.058594\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"18.642578\" y=\"170.058594\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"21.976562\" y=\"170.058594\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-4\" x=\"132.199219\" y=\"155.589844\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"138.873047\" y=\"155.589844\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"145.546875\" y=\"155.589844\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"148.880859\" y=\"155.589844\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"151.96875\" y=\"262.882812\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"158.642578\" y=\"262.882812\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"161.976562\" y=\"262.882812\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-1\" x=\"120.734375\" y=\"19.4375\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"127.408203\" y=\"19.4375\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"130.742188\" y=\"19.4375\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-4\" x=\"149.625\" y=\"137.382812\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"156.298828\" y=\"137.382812\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"159.632812\" y=\"137.382812\"/>\n",
       "</g>\n",
       "<g style=\"fill:rgb(0%,0%,0%);fill-opacity:1;\">\n",
       "  <use xlink:href=\"#glyph1-5\" x=\"276.464844\" y=\"133.503906\"/>\n",
       "  <use xlink:href=\"#glyph1-2\" x=\"283.138672\" y=\"133.503906\"/>\n",
       "  <use xlink:href=\"#glyph1-3\" x=\"286.472656\" y=\"133.503906\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<igraph.drawing.Plot at 0x120742e10>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here we highlight with gray the shortest tour found using igraph\n",
    "g.es[\"color\"] = \"black\"\n",
    "g.es[\"width\"] = 1\n",
    "g.vs[\"color\"] = \"white\"\n",
    "path = list(p)\n",
    "\n",
    "# Here we change the color and width of the selected edges before plotting them\n",
    "for i in range(len(path)):\n",
    "    src = i\n",
    "    dst = i + 1\n",
    "    if dst == (len(path)):\n",
    "        dst = 0\n",
    "    edge = (path[src], path[dst]) if path[src] < path[dst] else (path[dst], path[src])\n",
    "    index = g.get_edgelist().index(edge)\n",
    "    g.es[index][\"color\"] = \"gray\"\n",
    "    g.es[index][\"width\"] = 5\n",
    "\n",
    "igraph.plot(g, labels = True, edge_label=g.es[\"weight\"], bbox = (300,300), margin = 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "Bland, R.E., & D.E Shallcross (1989). Large traveling salesman problem arising from experiments in X-ray crystallography: a preliminary report on computation. Operations Research Letters, Vol. 8(3), pp. 125-128.\n",
    "\n",
    "Dorigo, M. & Gambardella, L.M. (1996). “Ant Colonies for the Traveling Salesman Problem”, University Libre de Bruxelles, Belgium."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}