Template.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# .... Title ...."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... Author ..."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://github.coventry.ac.uk/........"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1) Notation and definitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $G$ be a [complete]( \"graph is undirected, has no self-loops, and each node is connected to all the other vertices\")  [weighted]( \"the edges have a weight (a positive integer)\") graph with $n$ vertices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Optimisation TSP**:\n",
    "> Given $G$, find a Hamiltonian cycle of minimal total cost.\n",
    "\n",
    "This problem is **NP-Hard** because its decision version is **NP-complete** (Garey and Johnson, 1979, p. 211)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2) Testing methodology"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    ".................................................................\n",
    ".................................................................\n",
    "...  You can add or improve this section and its subsections  ...\n",
    ".................................................................\n",
    ".................................................................\n",
    "```\n",
    "\n",
    "* **Exact method (Exhaustive search)**:\n",
    "    Average _time_ for instances with increasing $n$.\n",
    "\n",
    "* **Greedy and meta-heuristics**:\n",
    "    Average _time_ and _\"quality\"_ as $n$ increases.\n",
    "\n",
    "Instances will be generated randomly as shown in the next subsection."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1) Random instances sampling strategy"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Four types of TSP instances will be generated by creating an **adjacency matrices** $M$ as follows:\n",
    "1. **Asymmetric**: The edge weights are independent and uniformly random in an interval $[1,\\text{MAX\\_WEIGHT}]$, i.e the graph is assumed to be directed.\n",
    "2. **Symmetric**: Like the asymmetric case but the graph is undirected, and the matrix is therefore symmetric: $M_{ij}=M_{ji}$.\n",
    "3. **Euclidean**: Generate points using $(x,y)$ coordinates, then generate the adjacency matrix by calculating all the required distances. Recall that the distance between two points $(x_1,y_1)$ and $(x_2,y_2)$ is $\\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. The points are generated in the rectangle defined by the points $(0,0)$ and $(\\text{MAX\\_Y},\\text{MAX\\_Y})$.\n",
    "4. **Graphs with obvious shortest cycle**: A graph where all the distances are 2 except for the edges on a predefined cycle, where the distance is 1. Such a graph would be useful for testing/debugging the \"nearest neighbour greedy\" search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation of the instances generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First start by importing relevant libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import randint, shuffle # random integers and random shuffling of a list\n",
    "from itertools import permutations # iterate over all possible permutations of a list\n",
    "from itertools import chain # concatenate range()'s'\n",
    "from math import inf as oo # Infinity (∞) is larger than any number\n",
    "from math import sqrt, log, factorial  # square root, logarithm, and n!\n",
    "from time import perf_counter # for measuring time. NB. 'perf_counter' is better/more accurate than 'time'\n",
    "import networkx as nx # to draw sample graphs\n",
    "import pandas as pd # to show the adjacency matrix in a nice format\n",
    "import matplotlib.pyplot as plt # to plot graphs of time and quality vs n\n",
    "import seaborn as sns # nice statistical plots -- see e.g. https://seaborn.pydata.org/tutorial/relational.html#relational-tutorial\n",
    "sns.set_style(\"white\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let the set of vertices be $\\{0, 1, 2,\\ldots, n-1\\}$.\n",
    "\n",
    "For simplicity, we will consider $0$ to be the start and end point of cycles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    ''' Random graphs '''\n",
    "    def __init__(self, n=0, type='asymmetric', MAX_WEIGHT=100, MAX_X=200, MAX_Y=200):\n",
    "        self.n = n\n",
    "        self.vertices = list(range(n)) # [0,1,...,n-1]\n",
    "        self.type = type\n",
    "        self.adj_matrix = [[oo for i in range(n)] for j in range(n)]\n",
    "        # Generate a random adjacency matrix according to the required type\n",
    "        if   type=='symmetric': self.__random_symmetric_graph(n,MAX_WEIGHT)\n",
    "        elif type=='Euclidean': self.__random_euclidean_graph(n,MAX_X,MAX_Y)\n",
    "        elif type=='easy':      self.__random_cycle_graph(n)\n",
    "        else:                   self.__random_asymmetric_graph(n,MAX_WEIGHT) # assume 'asymmetric' otherwise\n",
    "            \n",
    "    def __getitem__(self, i):\n",
    "        ''' Allow indexing to get the weights '''\n",
    "        return self.adj_matrix[i]\n",
    "                \n",
    "    def __random_asymmetric_graph(self,n, MAX_WEIGHT):\n",
    "        ''' Asymmetric adjacency matrix of size nxn '''\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i==j: continue # no self-loops\n",
    "                self.adj_matrix[i][j] = randint(1,MAX_WEIGHT)\n",
    "\n",
    "    def __random_symmetric_graph(self,n,MAX_WEIGHT):\n",
    "        ''' Symmetric adjacency matrix of size nxn '''\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                w = randint(1,MAX_WEIGHT)\n",
    "                self.adj_matrix[i][j] = w\n",
    "                self.adj_matrix[j][i] = w\n",
    "\n",
    "    def __random_cycle_graph(self,n):\n",
    "        ''' Symmetric adjacency matrix of size nxn with one reandomly chosen cycle\n",
    "        All the edge weights are 2 except for the cycle (weight=1) '''\n",
    "        self.adj_matrix = [[2 for _ in range(n)] for _ in range(n)] # All weights=2\n",
    "        # Select a random cycle which will have weight=1\n",
    "        cycle = list(range(1,n)) # don't include 0 as we want to be at the start\n",
    "        shuffle(cycle) # in-place random permutation\n",
    "        cycle = [0]+cycle+[0] # cycle starting and ending at 0\n",
    "        for a,b in zip(cycle, cycle[1:]): # set the cycle's weights to 1\n",
    "            self.adj_matrix[a][b] = 1\n",
    "            self.adj_matrix[b][a] = 1\n",
    "\n",
    "    def __random_euclidean_graph(self,n,MAX_X,MAX_Y):\n",
    "        ''' Symmetric adjacency matrix of a Euclidean graph of size nxn '''\n",
    "        # (1/2) Generate random (x,y) points\n",
    "        points = set()\n",
    "        while len(points)<n: # We may get duplicate (x,y) so we try until we get enough points\n",
    "            x,y = randint(0,MAX_X), randint(0,MAX_Y)\n",
    "            points.add((x,y))\n",
    "        points = list(points) # Sets are not indexed, so convert into a list\n",
    "        # (2/2) Now compute the adjacency matrix\n",
    "        for i in range(n):\n",
    "            p1 = points[i]\n",
    "            for j in range(i+1,n):\n",
    "                p2 = points[j]\n",
    "                distance = sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)\n",
    "                self.adj_matrix[i][j] = distance\n",
    "                self.adj_matrix[j][i] = distance\n",
    "        self.points=points"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cost(G, cycle):\n",
    "    ''' Calculate the cost of the given cycle [0,...,0] in G '''\n",
    "    return sum(G[a][b] for a,b in zip(cycle, cycle[1:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functions to show the graphs as **adjacency matrices** or as a **drawing**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show(G):\n",
    "    ''' Show adjacency matrix. Useful for debugging.\n",
    "    'type' is a string from: Euclidean, Cycle, ...\n",
    "    The distances are round to 1 decimal point for clarity/simplicity\n",
    "    '''\n",
    "    print(f\"{G.n}x{G.n} {G.type} graph:\")\n",
    "    if G.type=='Euclidean': print(\"Points:\",G.points)\n",
    "    r = pd.DataFrame({str(i): G[i] for i in range(G.n)})\n",
    "    display(r)\n",
    "    \n",
    "def nx_graph(G):\n",
    "    ''' Convert G into NetworkX format '''\n",
    "    nxG = nx.Graph() if G.type!='asymmetric' else nx.DiGraph() # undirected/directed graph\n",
    "    nxG.add_nodes_from(G.vertices) # Add the vertices\n",
    "    # Now add the edges\n",
    "    for a in G.vertices:\n",
    "        for b in G.vertices:\n",
    "            if a==b: continue # no self-loops\n",
    "            nxG.add_edge(a, b, weight=G[a][b])        \n",
    "    if G.type=='Euclidean': # add (x,y) coordinates if available\n",
    "        pos=dict(enumerate(G.points)) # vertex:(x,y) pairs\n",
    "        nx.set_node_attributes(nxG, pos, 'coord')\n",
    "    return nxG\n",
    "\n",
    "def draw(G):\n",
    "    ''' Draw the graph G using NetworkX '''\n",
    "    nxG = nx_graph(G)\n",
    "    weights_dictionary = nx.get_edge_attributes(nxG,'weight')\n",
    "    edges,weights = zip(*weights_dictionary.items())\n",
    "    pos = nx.circular_layout(nxG) if G.type!='Euclidean' else nx.get_node_attributes(nxG,'coord')\n",
    "    nx.draw(nxG, pos, \\\n",
    "            with_labels=True, node_color='red', font_color='white', font_weight='bold', font_size=14,\\\n",
    "            edge_color=weights, width=1.5, connectionstyle=\"arc3,rad=0.1\", edge_cmap=plt.cm.copper)\n",
    "    # see https://matplotlib.org/stable/gallery/color/colormap_reference.html\n",
    "    nx.draw_networkx_edge_labels(nxG, pos, edge_labels=weights_dictionary, label_pos=0.5 if G.type!=\"asymmetric\" else 0.25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3) Nearest Neigbour Greedy method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Idea\n",
    "\n",
    "Start at city 0, move to the nearest city, then from there to the next nearest city, and so on, until all cities are visited. Finally, return back to the start city."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Pseudocode\n",
    "\n",
    "1. $city \\gets 0$\n",
    "2. $visited\\gets []$\n",
    "3. **while** not all cities are visited **do**\n",
    "4. $\\quad$ $nearest\\_city \\gets \\text{nearest city to $city$ that has not been visited yet}$\n",
    "5. $\\quad$ Append $city$ to $visited$ $\\qquad\\qquad\\text{(i.e. mark $city$ as visited)}$\n",
    "5. $\\quad$ $city\\gets nearest\\_city$\n",
    "6. **end while**\n",
    "8. **return** $visited$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Running time analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The while-loop costs $O(n)$, and searching for the nearest city on line 4 costs $O(n)$ also, while the rest can be assumed to cost $O(1)$.\n",
    "So the total cost of this greedy approach is therefore $O(n)\\times O(n) = O(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def greedy_nearest_neighbour(G):\n",
    "    ''' Returns best found cycle and its cost '''\n",
    "    unvisited = G.vertices.copy()\n",
    "    visited = [] # solution to be built\n",
    "    city = 0 # Start city\n",
    "    while len(unvisited)>0:\n",
    "        # Find nearest neighbour\n",
    "        nearest_city = None\n",
    "        shortest_distance = oo\n",
    "        for neighbour in unvisited:\n",
    "            if G[city][neighbour] < shortest_distance:\n",
    "                shortest_distance = G[city][neighbour]\n",
    "                nearest_city = neighbour\n",
    "        # Update 'cycle' and 'cities' and G then 'city'\n",
    "        visited.append(city)\n",
    "        unvisited.remove(city)\n",
    "        city = nearest_city\n",
    "    return (visited, cost(G, visited+[0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4) Metaheuristic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "............................................................\n",
    "............................................................\n",
    "............................................................\n",
    "............................................................\n",
    "............................................................\n",
    "............................................................\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "............................................................\n",
    "............................................................\n",
    "\n",
    "(Based on your theoretical analysis and experimental findings, give clear and precise practical recommendations on which methods to use given the size and/or structure of the graph.)\n",
    "\n",
    "............................................................\n",
    "............................................................\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of references"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "............................................................\n",
    "............................................................\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}