{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c5f11a3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "\n",
    "import random\n",
    "random.seed()\n",
    "\n",
    "class WeightedUndirectedMatrixGraph:\n",
    "    \n",
    "    # initialize a weighted undirected adjacency-matrix graph with n nodes\n",
    "    #\n",
    "    def __init__(self, n):\n",
    "        self._num_vertices = n\n",
    "        self._adj_matrix = np.zeros((n, n))\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                self._adj_matrix[i][j] = math.inf\n",
    "                self._adj_matrix[j][i] = math.inf\n",
    "    \n",
    "    # returns the number of nodes\n",
    "    #\n",
    "    def get_num_vertices(self):\n",
    "        return self._num_vertices\n",
    "    \n",
    "    # returns weight of the edge between i and j\n",
    "    #\n",
    "    def get_weight(self, i, j):\n",
    "        return self._adj_matrix[i][j]\n",
    "    \n",
    "    # the path is a list of node IDs\n",
    "    #\n",
    "    def get_length_of_path(self, path):\n",
    "        return \"METHOD MISSING - NEEDS TO BE IMPLEMENTED\"\n",
    "    \n",
    "    # print the adjacency matrix\n",
    "    #\n",
    "    def output(self):\n",
    "        print(self._adj_matrix)\n",
    "    \n",
    "    # assign weight w to the edge between i and j (both ways)\n",
    "    # i and j must be different, and both within range(n), and w must be zero or positive\n",
    "    #\n",
    "    def set_weight(self, i, j, w):\n",
    "        if i == j or i < 0 or j < 0 or i >= self._num_vertices or j >= self._num_vertices or w < 0:\n",
    "            print(\"Warning: Invalid input to the connect method. Ignoring.\")\n",
    "            return\n",
    "        self._adj_matrix[i][j] = w\n",
    "        self._adj_matrix[j][i] = w\n",
    "    \n",
    "    # assign random weights to all edges\n",
    "    #\n",
    "    def randomize(self):\n",
    "        for i in range(self._num_vertices - 1):\n",
    "            for j in range(i+1, self._num_vertices):\n",
    "                random_weight = 2**random.randrange(self._num_vertices // 2)\n",
    "                random_weight += random.randrange(2**(self._num_vertices // 2) - 1)\n",
    "                self.set_weight(i, j, random_weight)\n",
    "    \n",
    "    # solve the travelling salesman problem (TSP) by brute force\n",
    "    #\n",
    "    # this returns the shortest cycle that visits each node exactly once\n",
    "    # (also referred to as the shortest Hamilton cycle in the graph:\n",
    "    #  A Hamilton cycle is a cycle that visits each node exactly once.)\n",
    "    #\n",
    "    def solve_TSP_brute_force(self):\n",
    "        unvisited = {i for i in range(self._num_vertices)}\n",
    "        unvisited.remove(0)  # select node 0 as the initial and final node of the cycle\n",
    "        \n",
    "        # helper method that actually solves the TSP\n",
    "        #\n",
    "        shortest_cycle, travel_distance = self._TSP_brute_force(0, 0, unvisited)\n",
    "        print(\"Brute-force TSP solver done comparing\", \\\n",
    "              WeightedUndirectedMatrixGraph._num_attempts, \"cycles.\")\n",
    "        WeightedUndirectedMatrixGraph._num_attempts = 0\n",
    "        \n",
    "        return shortest_cycle, travel_distance\n",
    "    \n",
    "    # unvisited_nodes is the set of unvisited nodes\n",
    "    # initial_node is the initial node\n",
    "    # present_node is the node that is presently visited\n",
    "    #\n",
    "    # the method returns the (shortest) remaining path\n",
    "    # and the length (i.e., total weight) of the shortest remaining path\n",
    "    #\n",
    "    # the remaining path is written into the list backward, to exploit faster end-of-list\n",
    "    # operations on a Python list; since this is a cycle in an undirected graph, it does not matter\n",
    "    #\n",
    "    def _TSP_brute_force(self, initial_node, present_node, unvisited_nodes):\n",
    "        \n",
    "        # if all nodes are visited, go back to the initial node\n",
    "        #\n",
    "        if len(unvisited_nodes) == 0:\n",
    "            \n",
    "            WeightedUndirectedMatrixGraph._num_attempts += 1\n",
    "            if WeightedUndirectedMatrixGraph._num_attempts \\\n",
    "            % WeightedUndirectedMatrixGraph._mod_status_output == 0:\n",
    "                print(\"\\tChecked\", WeightedUndirectedMatrixGraph._num_attempts, \"cycles.\")\n",
    "                \n",
    "            return [initial_node, present_node], self.get_weight(initial_node, present_node)\n",
    "        \n",
    "        # check which of the optional next nodes yield the shortest remaining path\n",
    "        #\n",
    "        else:\n",
    "            shortest_remaining_weight = math.inf\n",
    "            shortest_remaining_path = []\n",
    "            \n",
    "            unvisited_nodes_copy = {i for i in unvisited_nodes}\n",
    "            for v in unvisited_nodes_copy:\n",
    "                unvisited_nodes.remove(v)\n",
    "                v_path, v_weight = self._TSP_brute_force(initial_node, v, unvisited_nodes)\n",
    "                v_path.append(present_node)\n",
    "                v_weight += self.get_weight(v, present_node)\n",
    "                unvisited_nodes.add(v)\n",
    "                \n",
    "                if v_weight < shortest_remaining_weight:\n",
    "                    shortest_remaining_weight = v_weight\n",
    "                    shortest_remaining_path = v_path\n",
    "            return shortest_remaining_path, shortest_remaining_weight\n",
    "    \n",
    "    # static variable used to count number of cycles checked by the brute-force solver\n",
    "    #\n",
    "    _num_attempts = 0\n",
    "    _mod_status_output = 2000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5b59c8df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0. 29. 60. 37. 35. 22. 19. 32. 47. 50. 30. 51.]\n",
      " [29.  0. 12. 77. 61. 38. 22. 33. 39. 46. 26. 33.]\n",
      " [60. 12.  0. 22. 59. 49.  7. 43. 34. 61.  3. 45.]\n",
      " [37. 77. 22.  0. 45. 43. 36. 44. 82. 25. 57. 11.]\n",
      " [35. 61. 59. 45.  0. 42. 49. 35. 67. 15. 36. 32.]\n",
      " [22. 38. 49. 43. 42.  0. 14. 23. 20. 22. 49. 69.]\n",
      " [19. 22.  7. 36. 49. 14.  0. 41. 31. 58. 49. 34.]\n",
      " [32. 33. 43. 44. 35. 23. 41.  0. 22.  5. 50. 61.]\n",
      " [47. 39. 34. 82. 67. 20. 31. 22.  0. 53. 51. 11.]\n",
      " [50. 46. 61. 25. 15. 22. 58.  5. 53.  0. 49.  4.]\n",
      " [30. 26.  3. 57. 36. 49. 49. 50. 51. 49.  0. 44.]\n",
      " [51. 33. 45. 11. 32. 69. 34. 61. 11.  4. 44.  0.]]\n",
      "\n",
      "Path 0 -> 1 -> 2 has the length METHOD MISSING - NEEDS TO BE IMPLEMENTED\n"
     ]
    }
   ],
   "source": [
    "n = 12\n",
    "\n",
    "g = WeightedUndirectedMatrixGraph(n)\n",
    "g.randomize()\n",
    "\n",
    "g.output()\n",
    "\n",
    "print(\"\\nPath 0 -> 1 -> 2 has the length\", g.get_length_of_path([0, 1, 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "61612fa5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Random cycle: [8, 5, 3, 0, 11, 2, 6, 1, 4, 7, 10, 9, 8]\n",
      "Length of the random cycle: METHOD MISSING - NEEDS TO BE IMPLEMENTED\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "# create a random cycle and determine its distance\n",
    "#\n",
    "random_cycle = list(range(n))\n",
    "random.shuffle(random_cycle)\n",
    "random_cycle.append(random_cycle[0])\n",
    "\n",
    "print(\"Random cycle:\", random_cycle)\n",
    "print(\"Length of the random cycle:\", g.get_length_of_path(random_cycle))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0cb8416e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\tChecked 2000000 cycles.\n",
      "\tChecked 4000000 cycles.\n",
      "\tChecked 6000000 cycles.\n",
      "\tChecked 8000000 cycles.\n",
      "\tChecked 10000000 cycles.\n",
      "\tChecked 12000000 cycles.\n",
      "\tChecked 14000000 cycles.\n",
      "\tChecked 16000000 cycles.\n",
      "\tChecked 18000000 cycles.\n",
      "\tChecked 20000000 cycles.\n",
      "\tChecked 22000000 cycles.\n",
      "\tChecked 24000000 cycles.\n",
      "\tChecked 26000000 cycles.\n",
      "\tChecked 28000000 cycles.\n",
      "\tChecked 30000000 cycles.\n",
      "\tChecked 32000000 cycles.\n",
      "\tChecked 34000000 cycles.\n",
      "\tChecked 36000000 cycles.\n",
      "\tChecked 38000000 cycles.\n",
      "Brute-force TSP solver done comparing 39916800 cycles.\n"
     ]
    }
   ],
   "source": [
    "# call the TSP solver\n",
    "#\n",
    "salesman_path, salesman_travelling_distance = g.solve_TSP_brute_force()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "91c44d27",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Solution of the TSP: [0, 5, 6, 1, 10, 2, 3, 11, 8, 7, 9, 4, 0]\n",
      "Minimum travel distance: 208.0\n",
      "\n",
      "Validate by computing the total length of the cycle: METHOD MISSING - NEEDS TO BE IMPLEMENTED\n"
     ]
    }
   ],
   "source": [
    "print(\"\\nSolution of the TSP:\", salesman_path)\n",
    "print(\"Minimum travel distance:\", salesman_travelling_distance)\n",
    "\n",
    "print(\"\\nValidate by computing the total length of the cycle:\", g.get_length_of_path(salesman_path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "94b547dc",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}