Skip to content

Instantly share code, notes, and snippets.

@epifanio
Created June 28, 2025 08:18
Show Gist options
  • Save epifanio/3d975afbe6f9e98d967e247eba9805c9 to your computer and use it in GitHub Desktop.
Save epifanio/3d975afbe6f9e98d967e247eba9805c9 to your computer and use it in GitHub Desktop.
TSP
Display the source blob
Display the rendered blob
Raw
{
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment