TSP

TSP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6e729cac-5273-4331-a422-c3f4f6d0d1a8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b5420484-61a0-4b13-992d-c7bdc42d062e",
   "metadata": {},
   "outputs": [],
   "source": [
    "pp = pd.read_csv('remaining_points_new.csv', delimiter=\";\", names=['id', 'lat', 'lon'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "cfe88730-67f4-4f4b-a8c8-971cc73290e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>lat</th>\n",
       "      <th>lon</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>P96</td>\n",
       "      <td>57.7405</td>\n",
       "      <td>6.17724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>P92</td>\n",
       "      <td>57.7814</td>\n",
       "      <td>6.14218</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>P277</td>\n",
       "      <td>57.7448</td>\n",
       "      <td>6.06973</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>P100</td>\n",
       "      <td>57.7647</td>\n",
       "      <td>6.03700</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>P122</td>\n",
       "      <td>57.7371</td>\n",
       "      <td>6.00355</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     id      lat      lon\n",
       "0   P96  57.7405  6.17724\n",
       "1   P92  57.7814  6.14218\n",
       "2  P277  57.7448  6.06973\n",
       "3  P100  57.7647  6.03700\n",
       "4  P122  57.7371  6.00355"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pp.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "3c9dc553-c9b4-4f4d-baae-330dc3aa97ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Prepare data\n",
    "ids = pp['id'].tolist()\n",
    "coords = pp.set_index('id')[['lat', 'lon']].to_dict('index')\n",
    "\n",
    "# Build complete graph\n",
    "G = nx.path_graph(ids)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7eb42a33-2afd-47c4-82e3-621bd76ee61b",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = nx.shortest_path_length(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "06b74b7f-74bd-47d2-a8af-a99e6aa8760d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "NodeView(('P96', 'P92', 'P277', 'P100', 'P122', 'P276', 'P91', 'P89', 'P95', 'P103', 'P110', 'P111', 'P113', 'P278', 'P86', 'P88', 'P90', 'P93', 'P94', 'P97', 'P98', 'P279', 'P87', 'P280', 'P325', 'P327', 'P335', 'P337', 'P339', 'P294', 'P295', 'P296', 'P297', 'P298', 'P328', 'P329', 'P332', 'P333', 'P336', 'P340', 'P334', 'P342', 'P99', 'P330', 'R3600', 'P326', 'P331', 'P304', 'P310', 'P311', 'P317'))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "a687faf5-f4c7-4a35-90be-5eb9bd4322b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "test = nx.shortest_path_length(G, source='P96', target='P311')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "35e1cd6d-1849-4472-b0d0-8959160192fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "49"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "07618d64-a038-41bb-959f-ca867500dae0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49 ('P311', {'P311': 0, 'P310': 1, 'P317': 1, 'P304': 2, 'P331': 3, 'P326': 4, 'R3600': 5, 'P330': 6, 'P99': 7, 'P342': 8, 'P334': 9, 'P340': 10, 'P336': 11, 'P333': 12, 'P332': 13, 'P329': 14, 'P328': 15, 'P298': 16, 'P297': 17, 'P296': 18, 'P295': 19, 'P294': 20, 'P339': 21, 'P337': 22, 'P335': 23, 'P327': 24, 'P325': 25, 'P280': 26, 'P87': 27, 'P279': 28, 'P98': 29, 'P97': 30, 'P94': 31, 'P93': 32, 'P90': 33, 'P88': 34, 'P86': 35, 'P278': 36, 'P113': 37, 'P111': 38, 'P110': 39, 'P103': 40, 'P95': 41, 'P89': 42, 'P91': 43, 'P276': 44, 'P122': 45, 'P100': 46, 'P277': 47, 'P92': 48, 'P96': 49})\n"
     ]
    }
   ],
   "source": [
    "# la riga con indice == 49\n",
    "# e' quella con il percorso piu' breve\n",
    "# da percorrere all'inverso\n",
    "\n",
    "for i,v in enumerate(p):\n",
    "    if i ==  49:\n",
    "        print(i, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13c3ec68-7a9a-4c50-ae6f-d9bbbc8ff5bd",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}