TSP_Basic_01 notebook.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Created on Sat Jul 29 09:18:18 2017\n",
    "@author: Andres L Dorado\n",
    "\"\"\"\n",
    "import json\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read source file\n",
    "with open( 'tsp_data_01.json' ) as tsp_data:\n",
    "    data = json.load( tsp_data )\n",
    "    \n",
    "#print( data, len( data) )\n",
    "\n",
    "print(json.dumps(data, indent=4, sort_keys=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# determine number of cities and routes\n",
    "numberOfCities = len( data['Cities'] ) \n",
    "if len( data ) > 1:\n",
    "    numberOfRoutes = len( data['Routes'] ) \n",
    "else:\n",
    "    numberOfRoutes = 0\n",
    "\n",
    "print( '# Cities:', numberOfCities, '# Routes:', numberOfRoutes )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cities = []\n",
    "cityNames = []\n",
    "\n",
    "# read cities and routes\n",
    "for r in data['Cities']:\n",
    "    cities.append( r )\n",
    "    cityNames.append( r['name'] )\n",
    "\n",
    "print( cityNames )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "distances = [ [ 0 for col in range( numberOfCities ) ] for row in range( numberOfCities ) ]\n",
    "\n",
    "#def cityIndex( _cities, _city ):\n",
    "#    index = 0\n",
    "#    for r in _cities:\n",
    "#        if r['name'] == _city:\n",
    "#            return index\n",
    "#        index += 1\n",
    "\n",
    "if numberOfRoutes != 0:\n",
    "    # read routes\n",
    "    for r in data['Routes']:\n",
    "        distances[ cityNames.index( r['cityFrom'] ) ][ cityNames.index( r['cityTo'] ) ] = r['distance']\n",
    "        distances[ cityNames.index( r['cityTo'] ) ][ cityNames.index( r['cityFrom'] ) ] = r['distance']    \n",
    "else:\n",
    "    for i in range( len( cities ) - 1 ):\n",
    "        for j in range( i+1, len( cities ) ):\n",
    "            # calculate distance\n",
    "            deltaXSq = math.pow( ( cities[i]['x'] - cities[j]['x'] ), 2 )\n",
    "            deltaYSq = math.pow( ( cities[j]['y'] - cities[i]['y'] ), 2 )\n",
    "            distances[i][j] = math.sqrt( deltaXSq + deltaYSq )\n",
    "            distances[j][i] = math.sqrt( deltaXSq + deltaYSq )        \n",
    "\n",
    "#print( distances )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "first_city = input( 'Enter the starting point: ' )\n",
    "init = cityNames.index( first_city )\n",
    "\n",
    "cost = 0\n",
    "print( 'First City', first_city, '(Cost =', cost, ')' )\n",
    "cityNames[init]=''\n",
    "curr = init\n",
    "\n",
    "cities_left = len( cityNames ) - 1\n",
    "while cities_left > 0:\n",
    "    min_dist = 10000\n",
    "    for i in range( len( cityNames ) ):\n",
    "        dist = distances[curr][i]\n",
    "        if cityNames[i] != '' and min_dist > dist:\n",
    "            next = i\n",
    "            min_dist =  dist\n",
    "    cost += min_dist\n",
    "    print( 'Next City', cityNames[next], 'Distance', min_dist, '(Cost =', cost,')' )\n",
    "    cityNames[next]=''\n",
    "    curr = next\n",
    "    cities_left -= 1\n",
    "\n",
    "cost += distances[curr][init]\n",
    "print( 'Total Cost', cost )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}