ACO.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ant Colony Optimisation (ACO) for the Travelling Salesman Problem (TSP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $G$ be a complete weighted graph with $n$ vertices.\n",
    "\n",
    "**Optimisation TSP**:\n",
    "> Given $G$, find a Hamiltonian cycle of minimal total cost.\n",
    "\n",
    "This problem is **NP-Hard** (Garey and Johnson, 1979, p. 211)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the `scikit-opt` library, or an equivalent one, to benchmark the performance of the Ant Colony Optimisation (ACO) metaheuristic on a variety of graph **sizes** ($n=50,100,150,200,250,300$) and **topologies** (Euclidean, Symmetric, Asymmetric).\n",
    "\n",
    "Compare its results against the results obtained using the **nearest neighbour** greedy approach. (An implementation is provided below.)\n",
    "\n",
    "What is the effect of the ACO's hyperparameters on time and quality of solutions?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Marking scheme\n",
    "\n",
    "|Item|Mark|\n",
    "|:----|---:|\n",
    "|Euclidean|/4|\n",
    "|Symmetric|/4|\n",
    "|Asymmetric|/4|\n",
    "|Effect of `size_pop`|/4|\n",
    "|Effect of `max_iter`|/4|\n",
    "|||\n",
    "|**Total**:     |/20|\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph types and generation of random instances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below provides 3 types of TSP instances by creating an **adjacency matrices** $M$ as follows:\n",
    "\n",
    "1. **Asymmetric**: The edge weights are independent and uniformly distributed 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 adjacency 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. \n",
    "   > 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}$.\n",
    "   \n",
    "   The points are generated in the rectangle defined by the points $(0,0)$ and $(\\text{MAX\\_Y},\\text{MAX\\_Y})$."
   ]
  },
  {
   "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": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:31.774523Z",
     "start_time": "2022-10-25T11:38:23.464728Z"
    }
   },
   "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": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:31.830857Z",
     "start_time": "2022-10-25T11:38:31.778480Z"
    }
   },
   "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": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:31.846797Z",
     "start_time": "2022-10-25T11:38:31.837802Z"
    }
   },
   "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": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:31.879902Z",
     "start_time": "2022-10-25T11:38:31.850793Z"
    }
   },
   "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": [
    "#### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:31.900873Z",
     "start_time": "2022-10-25T11:38:31.879902Z"
    }
   },
   "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": [
    "# Ant Colony Optimisation (ACO)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Ant Colony optimisation was successfully executed using the Sci-kit package, using the aca.run() function. \n",
    "\n",
    "## For n = 50 \n",
    "\n",
    "Results are as follows :- \n",
    "\n",
    "Cost of travel, Euclidean =  117.30634693659576\n",
    "Cost of travel, Euclidean - Greedy= 124.5160306576604\n",
    "Cost of travel for asymmetric graph is =  117\n",
    "Cost of travel for asymmetric graph Greedy= 71\n",
    "Cost of travel for symmetric graph is =  87\n",
    "Cost of travel for symmetric graph Greedy= 81\n",
    "\n",
    "## Images of graphs and plots \n",
    "\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/EcuGraphn50.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    " \n",
    "![title](ACO/Eucpltn50.png)\n",
    "\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/Asygraph50.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/Asyplt50.png)\n",
    "\n",
    "\n",
    "$$ Symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgraph50.png)\n",
    "\n",
    "$$ Symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplt50.png)\n",
    "\n",
    "$$ $$ \n",
    "\n",
    "## For n = 100\n",
    "\n",
    "Results are as follows :- \n",
    "\n",
    "Cost of travel, Euclidean =  178.95818153604972\n",
    "Cost of travel, Euclidean - Greedy= 206.00052858467922\n",
    "Cost of travel for asymmetric graph is =  182\n",
    "Cost of travel for asymmetric graph Greedy= 120\n",
    "Cost of travel for symmetric graph is =  211\n",
    "Cost of travel for symmetric graph Greedy= 132\n",
    "\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/EcuGraphn100.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    " \n",
    "![title](ACO/Ecuplt100.png)\n",
    "\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/Asygraph100.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/Asyplt100.png)\n",
    "\n",
    "\n",
    "$$ symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgraph100.png)\n",
    "\n",
    "$$ symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplt100.png)\n",
    "\n",
    "\n",
    "$$ $$ \n",
    "\n",
    "## For n = 150\n",
    "\n",
    "Results are as follows :- \n",
    "\n",
    "Cost of travel, Euclidean =  178.95818153604972\n",
    "Cost of travel, Euclidean - Greedy= 206.00052858467922\n",
    "Cost of travel for asymmetric graph is =  182\n",
    "Cost of travel for asymmetric graph Greedy= 120\n",
    "Cost of travel for symmetric graph is =  211\n",
    "Cost of travel for symmetric graph Greedy= 132\n",
    "\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/Asygraph150.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    " \n",
    "![title](ACO/Ecuplt100.png)\n",
    "\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/ecu(asy)graph150.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/asyplot150.png)\n",
    "\n",
    "\n",
    "$$ Symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgraph150.png)\n",
    "\n",
    "$$ Symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplot150.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## For n = 200\n",
    "Results are as follows :- \n",
    "Cost of travel, Euclidean =  287.6057902102739\n",
    "Cost of travel, Euclidean - Greedy= 301.31792232560036\n",
    "Cost of travel for asymmetric graph is =  242\n",
    "Cost of travel for asymmetric graph Greedy= 220\n",
    "Cost of travel for symmetric graph is =  210\n",
    "Cost of travel for symmetric graph Greedy= 221\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/Ecugraph200.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    "\n",
    "![title](ACO/ecuplt200.png)\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/Asygrf200.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/Asyplt200.png)\n",
    "\n",
    "\n",
    "$$ Symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgrf200.png)\n",
    "\n",
    "$$ Symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplt200.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## For n = 250\n",
    "Results are as follows :- \n",
    "Cost of travel, Euclidean =  280.671643559593\n",
    "Cost of travel, Euclidean - Greedy= 307.56913052707324\n",
    "Cost of travel for asymmetric graph is =  221\n",
    "Cost of travel for asymmetric graph Greedy= 225\n",
    "Cost of travel for symmetric graph is =  422\n",
    "Cost of travel for symmetric graph Greedy= 225\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/Ecugrf250.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    "\n",
    "![title](ACO/ecuplt250.png)\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/Asygrf.250.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/Asyplt250.png)\n",
    "\n",
    "\n",
    "$$ Symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgrf250.png)\n",
    "\n",
    "$$ Symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplt250.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## For n = 300\n",
    "Results are as follows :- \n",
    "Cost of travel, Euclidean =  329.06640228446554\n",
    "Cost of travel, Euclidean - Greedy= 378.66916482167045\n",
    "Cost of travel for asymmetric graph is =  271\n",
    "Cost of travel for asymmetric graph Greedy= 270\n",
    "Cost of travel for symmetric graph is =  289\n",
    "Cost of travel for symmetric graph Greedy= 263\n",
    "\n",
    "$$ Euclidean \\space graph $$\n",
    "\n",
    "![title](ACO/Ecugrf300.png)\n",
    "\n",
    "$$ Euclidean \\space Plot $$\n",
    "\n",
    "![title](ACO/Ecuplt300.png)\n",
    "\n",
    "$$ Asymmetric \\space graph $$\n",
    "\n",
    "![title](ACO/Asygrf300.png)\n",
    "\n",
    "$$ Asymmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/Asyplt300.png)\n",
    "\n",
    "\n",
    "$$ Symmetric \\space graph $$\n",
    "\n",
    "![title](ACO/symgrf300.png)\n",
    "\n",
    "$$ Symmetric \\space Plot $$\n",
    " \n",
    "![title](ACO/symplt300.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "In conclusion we were successful to solve the traveling salesman problem using the ant colony optimization alorigthm. As required, we created three diffirent types of weighted graphs (Euclidian, Assymetric & Symetric). After studing the scikit-learn we preformed ant colony optimization on the graph using the ACA_TSP() from the package. Everytime we compared the cost of traveling with the greedy neighbor approach as required, we did the expriment for vertices n=50, 100, 150, 200, 250, 300 which are the results shown above. \n",
    "It is important to note that the accuracy of ant colony optimization alogrithim is directly dependent on size_pop & max_iter which is the maximum number of iterations. We can say that if we increase the maximum number of iterations from 200 to 1000, accuracy of the results is better. As seen above, for n= 300, max_iter=200 and size_pop=50 we can see that greedy neighbor gives better results (lower cost of travel) than the ant optimzation. Therefore it is needed that max_iter > n.  \n",
    "\n",
    "Please refer to ACO.py for python code. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of references"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "M. Alhanjouri and Belal Alfarra. Ant colony versus genetic algorithm based on travelling salesman\n",
    "problem. 2013\n",
    "\n",
    "scikit-opt. (n.d.-b). Retrieved 2 November 2022, from https://scikit-opt.github.io/scikit-opt/"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.11.0 ('venv': venv)",
   "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.11.0"
  },
  "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
  },
  "vscode": {
   "interpreter": {
    "hash": "9646fcfabfca22912ce5fe7fa2239f453c97b6dafcc6a8d175371d4d5afbb8ca"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}