TSP- Using Christofides Algo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8f9bf28a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from itertools import permutations\n",
    "import networkx as nx\n",
    "import math\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d6dab096",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Neighbours:  {0: [2, 1], 2: [0, 3], 1: [3, 0], 3: [1, 2]}\n",
      "\n",
      "Points:  [[0, 2, 1, 2], [2, 0, 2, 1], [1, 2, 0, 2], [2, 1, 2, 1]]\n",
      "\n",
      " Travelling Sales Man tour:  [2, 3, 1, 0, 2]\n",
      "\n",
      "Cost of the salesman tour:  6.242640687119286\n"
     ]
    }
   ],
   "source": [
    "'''from functions.matching import find_minimum_weight_matching leads to a mapping problem in python 3\n",
    "We will therefore use a different minimum weight matching approach with almost similar results'''\n",
    "\n",
    "#from functions.matching import find_minimum_weight_matching\n",
    "\n",
    "def solve_tsp(points):\n",
    "    # build a graph\n",
    "    Graph = build_graph(points)\n",
    "    graph = Graph\n",
    "\n",
    "    # Define the minimum spanning tree\n",
    "    minimum_spanning_tree = minimum_spanning_tree_fun(Graph)\n",
    "    #print(\"minimum_spanning_tree: \", minimum_spanning_tree)\n",
    "\n",
    "    # get the odd vertices\n",
    "    oddvertices = find_oddvertices(minimum_spanning_tree)\n",
    "    #print(\"Odd vertices in minimum_spanning_tree: \", oddvertices)\n",
    "\n",
    "    # Append minimum weight matching edges to minimum_spanning_tree\n",
    "    min_weight = minimum_weight_matching(minimum_spanning_tree, Graph, oddvertices)\n",
    "    #print(\"Minimum weight matching: \", minimum_spanning_tree)\n",
    "\n",
    "    # find a euler tour (e_tour)\n",
    "    e_tour = find_e_tour(minimum_spanning_tree, Graph)\n",
    "    tour = e_tour\n",
    "\n",
    "\n",
    "    cost = cost_of_tour(tour, graph)\n",
    "\n",
    "    print (\"\\nPoints: \",points)\n",
    "    print(\"\\n Travelling Sales Man tour: \", e_tour)\n",
    "    print(\"\\nCost of the salesman tour: \", cost)\n",
    "\n",
    "    return cost, tour,graph, minimum_spanning_tree\n",
    "\n",
    "#Get euclidean distance between two points\n",
    "def get_distance(x1, y1, x2, y2):\n",
    "    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)\n",
    "\n",
    "\n",
    "def build_graph(points):\n",
    "    graph = {}\n",
    "    for current in range(len(points)):\n",
    "        for next_point in range(len(points)):\n",
    "            if current != next_point:\n",
    "                if current not in graph:\n",
    "                    graph[current] = {}\n",
    "\n",
    "                graph[current][next_point] = get_distance(points[current][0], points[current][1], points[next_point][0],\n",
    "                                                        points[next_point][1])\n",
    "\n",
    "    return graph\n",
    "\n",
    "\n",
    "class jonint_find:\n",
    "    def __init__(self):\n",
    "        self.weights = {}\n",
    "        self.parents = {}\n",
    "\n",
    "    def __getitem__(self, object):\n",
    "        if object not in self.parents:\n",
    "            self.parents[object] = object\n",
    "            self.weights[object] = 1\n",
    "            return object\n",
    "\n",
    "        # find sales tour of objects leading to the source\n",
    "        sales_tour = [object]\n",
    "        source = self.parents[object]\n",
    "        while source != sales_tour[-1]:\n",
    "            sales_tour.append(source)\n",
    "            source = self.parents[source]\n",
    "\n",
    "        # compress the sales_tour and return\n",
    "        for ancestor in sales_tour:\n",
    "            self.parents[ancestor] = source\n",
    "        return source\n",
    "\n",
    "    def __iter__(self):\n",
    "        return iter(self.parents)\n",
    "\n",
    "    def union(self, *objects):\n",
    "        sources = [self[x] for x in objects]\n",
    "        most_weighted = max([(self.weights[r], r) for r in sources])[1]\n",
    "        for r in sources:\n",
    "            if r != most_weighted:\n",
    "                self.weights[most_weighted] += self.weights[r]\n",
    "                self.parents[r] = most_weighted\n",
    "\n",
    "\n",
    "def minimum_spanning_tree_fun(Graph):\n",
    "    tree = []\n",
    "    branches = jonint_find()\n",
    "    for W, u, v in sorted((Graph[u][v], u, v) for u in Graph for v in Graph[u]):\n",
    "        if branches[u] != branches[v]:\n",
    "            tree.append((u, v, W))\n",
    "            branches.union(u, v)\n",
    "\n",
    "    return tree\n",
    "#get cost of the salesman tour\n",
    "def cost_of_tour(tour, graph):\n",
    "    \"\"\"Returns Cost of the salesman tour\"\"\"\n",
    "    cost_of_travel = 0\n",
    "    tour = tour[0:len(tour)-1]\n",
    "    preceding_vertex = tour[len(tour)-1]\n",
    "    for present_vertex in tour:\n",
    "        if preceding_vertex > present_vertex:\n",
    "            cost_of_travel = cost_of_travel + graph[present_vertex][preceding_vertex]\n",
    "        else:\n",
    "            cost_of_travel = cost_of_travel + graph[preceding_vertex][present_vertex]\n",
    "        preceding_vertex = present_vertex\n",
    "    return cost_of_travel\n",
    "\n",
    "\n",
    "\n",
    "def minimum_weight_matching(minimum_spanning_tree, Graph, oddvertices):\n",
    "    \n",
    "    random.shuffle(oddvertices)\n",
    "\n",
    "    while oddvertices:\n",
    "        v = oddvertices.pop()\n",
    "        distance = float(\"inf\")\n",
    "        u = 1\n",
    "        closest = 0\n",
    "        for u in oddvertices:\n",
    "            if v != u and Graph[v][u] < distance:\n",
    "                distance = Graph[v][u]\n",
    "                closest = u\n",
    "\n",
    "        minimum_spanning_tree.append((v, closest, distance))\n",
    "        oddvertices.remove(closest)\n",
    "\n",
    "\n",
    "def find_oddvertices(minimum_spanning_tree):\n",
    "    temp_gr = {}\n",
    "    vertices = []\n",
    "    for ej in minimum_spanning_tree:\n",
    "        if ej[0] not in temp_gr:\n",
    "            temp_gr[ej[0]] = 0\n",
    "\n",
    "        if ej[1] not in temp_gr:\n",
    "            temp_gr[ej[1]] = 0\n",
    "\n",
    "        temp_gr[ej[0]] += 1\n",
    "        temp_gr[ej[1]] += 1\n",
    "\n",
    "    for vertex in temp_gr:\n",
    "        if temp_gr[vertex] % 2 == 1:\n",
    "            vertices.append(vertex)\n",
    "\n",
    "    return vertices\n",
    "        \n",
    "        \n",
    "def find_e_tour(matched_minimum_spanning_tree, Graph):\n",
    "    # get ne1igbours\n",
    "    n = {}\n",
    "    for ej in matched_minimum_spanning_tree:\n",
    "        if ej[0] not in n:\n",
    "            n[ej[0]] = []\n",
    "\n",
    "        if ej[1] not in n:\n",
    "            n[ej[1]] = []\n",
    "\n",
    "        n[ej[0]].append(ej[1])\n",
    "        n[ej[1]].append(ej[0])\n",
    "\n",
    "    print(\"Neighbours: \", n)\n",
    "\n",
    "    # obtains the hamiltonian circuit\n",
    "    begin_vertex = matched_minimum_spanning_tree[0][0]\n",
    "    E_P = [n[begin_vertex][0]]\n",
    "\n",
    "    while len(matched_minimum_spanning_tree) !=0:\n",
    "        for i, v in enumerate(E_P):\n",
    "            if len(n[v]) !=0:\n",
    "                break\n",
    "\n",
    "        while len(n[v]) !=0:\n",
    "            w = n[v][0]\n",
    "\n",
    "            remove_duplicate_edge_from_matched_minimum_spanning_tree_fun(matched_minimum_spanning_tree, v, w)\n",
    "\n",
    "            del n[v][(n[v].index(w))]\n",
    "            del n[w][(n[w].index(v))]\n",
    "\n",
    "            i += 0\n",
    "            E_P.insert(i, w)\n",
    "\n",
    "            v = w\n",
    "\n",
    "    return E_P\n",
    "\n",
    "\n",
    "def remove_duplicate_edge_from_matched_minimum_spanning_tree_fun(matched_minimum_spanning_tree, k1, k2):\n",
    "\n",
    "    for i, item in enumerate(matched_minimum_spanning_tree):\n",
    "        if (item[0] == k2 and item[1] == k1) or (item[0] == k1 and item[1] == k2):\n",
    "            del matched_minimum_spanning_tree[i]\n",
    "\n",
    "    return matched_minimum_spanning_tree\n",
    "\n",
    "\n",
    "\n",
    "def find_minimum_weight_matching_slow(graph):\n",
    "    # Graph should have an even number of vertices to have a perfect\n",
    "    # matching.\n",
    "    assert len(graph) % 2 == 0\n",
    "\n",
    "    import itertools\n",
    "\n",
    "    def score(matching):\n",
    "        result = 0\n",
    "        for u, v in matching:\n",
    "            result += graph[u][v]\n",
    "        return result\n",
    "\n",
    "    best = None\n",
    "    for permutation in itertools.permutations(range(len(graph))):\n",
    "        matching = []\n",
    "        for i in range(0, len(graph), 2):\n",
    "            matching.append((permutation[i], permutation[i + 1]))\n",
    "        if best is None or score(matching) < score(best):\n",
    "            best = matching\n",
    "\n",
    "    return best\n",
    "\n",
    "def examples():\n",
    "    # NB: There are many optimal solutions for TSP instances below, so\n",
    "    # treat these asserts just as examples of a possible program behaviour.\n",
    "\n",
    "    # We start at point 0 with coordinates (0, 0), then go to point 1\n",
    "    # with coordinates (2, 2) and then return to point 0.\n",
    "    assert solve_tsp([(0, 0), (2, 2)]) == [0, 1, 0]\n",
    "\n",
    "    # Here we have four points in the corners of a unit square.\n",
    "    # One possible tour is (1, 0) -> (0, 0) -> (0, 1) -> (1, 1) -> (1, 0).\n",
    "    assert solve_tsp([(1, 1), (0, 0), (1, 0), (0, 1)]) == [2, 1, 3, 0, 2]\n",
    "\n",
    "    # Examples of find_minimum_weight_matching_slow (and find_minimum_weight_matching) usage.\n",
    "\n",
    "    # Here we have a graph with two vertices and one edge. The single possible perfect matching\n",
    "    # is just a (0, 1) edge of a graph.\n",
    "    assert find_minimum_weight_matching_slow([[0, 1], [1, 0]]) == [(0, 1)]\n",
    "\n",
    "    # In a graph below there are two edges with weight 1 and all the other edges have weight 2.\n",
    "    # The only possible way to obtain a perfect matching of weight 2 is to select both of the edges\n",
    "    # with weight 1.\n",
    "    assert find_minimum_weight_matching_slow([\n",
    "        [0, 2, 1, 2],\n",
    "        [2, 0, 2, 1],\n",
    "        [1, 2, 0, 2],\n",
    "        [2, 1, 2, 1],\n",
    "    ]) == [(0, 2), (1, 3)]\n",
    "    \n",
    "    \n",
    "    \n",
    "#Define the points here\n",
    "points = [\n",
    "        [0, 2, 1, 2],\n",
    "        [2, 0, 2, 1],\n",
    "        [1, 2, 0, 2],\n",
    "        [2, 1, 2, 1],\n",
    "    ]\n",
    "\n",
    "\n",
    "# MAIN ---------------------------------------------------------\n",
    "\n",
    "def main(points):\n",
    "    output = solve_tsp(points)\n",
    "    return output\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "49358073",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Neighbours:  {0: [1, 1], 1: [0, 0]}\n",
      "\n",
      "Points:  [(0, 0), (2, 2)]\n",
      "\n",
      " Travelling Sales Man tour:  [1, 0, 1]\n",
      "\n",
      "Cost of the salesman tour:  5.656854249492381\n"
     ]
    }
   ],
   "source": [
    "#points 1\n",
    "points = [(0, 0), (2, 2)]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main(points)"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}