Centre of mass based TSP solution (2)

I updated the code to a working state. My previous question. Even if this code working I wonder if I can write this code in a more efficient way. Maybe less for loops Etc.

from tkinter import *
import math
import random

class city:
def __init__(self,coordinates,name):
self.coordinates = coordinates
self.name = name

path = []
origin_list=[]
removed_cities=[]
total_distance_base=[]
distances_to_current=[]
distances_to_centre=[]
distances_to_centre_step_two=[]
distances_to_centre_complete=[]
total_distance=[]
total_distance_complete=[]
last_list=[]
fake_origin_list = []

def city_creator():
sum_of_coordinates_x = 0
sum_of_coordinates_y = 0
for i in range(50):
randone = random.randint(0, 700)
randtwo = random.randint(0, 700)
a = city((randone,randtwo),i)
origin_list.append(a)
sum_of_coordinates_x+=randone
sum_of_coordinates_y+=randtwo
return [sum_of_coordinates_x,sum_of_coordinates_y]

sum_all = city_creator()
sum_x = sum_all[0]
sum_y = sum_all[1]

def distances_to_centre_of_mass(x,y,lst):
distances_to_centre_step_two.clear()
distances_to_centre.clear()
distances_to_centre_complete.clear()
avg_x = int(x//len(lst))
avg_y = int(y//len(lst))
for city in lst:
distances_to_centre.append([int(math.sqrt((avg_x-city.coordinates[0])**2
+(avg_y-city.coordinates[1])**2)),city.name])
for dist in distances_to_centre:
distances_to_centre_step_two.append(dist[0])
distances_to_centre_step_two.sort()
for final in distances_to_centre_step_two:
for i in distances_to_centre:
if final == i[0] and (i in distances_to_centre_complete)==False:
distances_to_centre_complete.append(i)
return distances_to_centre_complete

fcity = distances_to_centre_of_mass(sum_x,sum_y,origin_list)

def path_creator():
while len(origin_list) != 0:
sumx = 0
sumy = 0
for d in origin_list:
sumx += d.coordinates[0]
sumy += d.coordinates[1]
distances_to_centre_of_mass(sumx, sumy, origin_list)

last_list.clear()
total_distance_base.clear()
total_distance.clear()
last_list.clear()
distances_to_current.clear()
for i in origin_list:
if len(origin_list) == 50:
distances_to_current.append(
[int(math.sqrt((fcity[-1][0] - i.coordinates[0]) ** 2 +
(fcity[-1][1] - i.coordinates[1]) ** 2)), i.name]
)
else:
distances_to_current.append(
[int(math.sqrt((removed_cities[-1].coordinates[0]-i.coordinates[0])**2+
(removed_cities[-1].coordinates[1]-i.coordinates[1])**2)),i.name]
)
for a in distances_to_current:
for b in distances_to_centre_complete:
if a[1] == b[1]:
total_distance.append([5*a[0]+2*b[0],a[1]])
total_distance_base.append(5*a[0]+2*b[0])
total_distance_base.sort()
for a in total_distance_base:
for b in total_distance:
if a == b[0] and (b in path)==False:
print(b)
path.append(b)
for c in origin_list:
print(c.name,b)
if c.name == b[1]:
origin_list.remove(c)
removed_cities.append(c)
break
break

path_creator()
print(path)
print(len(path))
print(len(removed_cities))

window=Tk()
window.config(bg='White')
window.title('Hello Python')
window.geometry("1000x1000+10+20")
canvas = Canvas(width = 800, height = 900, bg = "white")

for a in path:
for b in removed_cities:
if a[1] == b.name and (b in fake_origin_list) == False:
fake_origin_list.append(b)
print(len(fake_origin_list))
for i in fake_origin_list:
canvas.create_oval(i.coordinates[0]-3,i.coordinates[1]-3,i.coordinates[0]+3,i.coordinates[1]+3, fill="Black")
for i in range(len(fake_origin_list)):
if i == len(fake_origin_list)-1:
total_road += math.sqrt((fake_origin_list[i].coordinates[0]-fake_origin_list[0].coordinates[0])**2 + (fake_origin_list[i].coordinates[1] - fake_origin_list[0].coordinates[1])**2)
canvas.create_line(fake_origin_list[i].coordinates[0], fake_origin_list[i].coordinates[1], fake_origin_list[0].coordinates[0],fake_origin_list[0].coordinates[1], width=2, fill='Blue')
else:
total_road += math.sqrt((fake_origin_list[i].coordinates[0]-fake_origin_list[i+1].coordinates[0])**2 + (fake_origin_list[i].coordinates[1] - fake_origin_list[i+1].coordinates[1])**2)
canvas.create_line(fake_origin_list[i].coordinates[0],fake_origin_list[i].coordinates[1],fake_origin_list[i+1].coordinates[0],fake_origin_list[i+1].coordinates[1],width=2,fill='Blue')
window.mainloop()

• A couple of different approaches come to mind that may make this faster: 1. Using OR tools for the formulation. For instance here is gurobipy example code for solving the TSP "efficiently". 2. If you are not interested in an exact solution, but one that is good, it should be noted you are solving the Euclidean version of the problem which has a well known polynomial time approximation scheme.
– Dair
Mar 30 at 20:19
• There is a bug in this implementation on lines 78-79, where a euclidean distance between an element (distance, city_name) and a point (x, y) is performed, which does not make a lot of sense. Apr 12 at 20:01

Avoiding mutable global variables

In general global mutable variables (total_distance_base, removed_cities, etc.) should be avoided because their state is hard to track, and if every part of the program can modify them, debugging can become quite hard.

Whenever possible, variables should be created inside functions to make them inaccessible from other parts of the program (reduce their scope), and should be returned if they are needed elsewhere.

For example, total_distance_base is only used inside the path_creator function, so it should be initialized inside the function and inside the while statement.

ℹ️ Constant global variables are OK, but are usually spelled in UPPERCASE

Use of main clause

All the variables that are not global should be encapsulated in a main function, to avoid polluting the global scope, and to help IDEs / editors to spot the unused ones:

def main() -> None:
...

if __name__ == "__main__":
main()

Avoiding magic numbers

There are hard-coded values that can easily introduce a bug:

For example: what happens if someone decides to generate 100 cities instead of 50, and forgets to update the corresponding 50 inside the path_creator function?

Also, another developer (or even you in a few months) might not understand what those values correspond to. What is the purpose of the 5 and 2 on lines 89 and 90? Consider giving them a meaningful name.

Structuring the data

city (which should be named City according to PEP8) is a great example of data structure, and helps a lot when reading the code. More structures of the same kind should be introduced. Each time a specific element is accessed with a hard-coded index, it is a good habit to wonder if a data structure is not lacking. Also, lists should not contain heterogeneous elements, like "(distance, city name)". Some more appropriate data structures can be:

from dataclasses import dataclass
from typing import NamedTuple

class Point(NamedTuple):
x: float
y: float

@dataclass
class City:
coordinates: Point
name: int

@dataclass
class Path:
distance: int
city_name: int
• The city class can be replaced with a dataclass, which is more concise
• A NamedTuple can be used to declare a Point, as they are immutable (immutability can avoid a lot of trouble), and iterating over coordinates can be useful (unpacking: x, y = point, math.dist...)

Structuring the data helps readability by replacing integers accessors by text identifiers:

path[1]
# Would become:
path.city_name

It helps to avoid bugs, like the one on lines 78-79, where a Euclidean distance between an element "(distance, city name)" and a point (x, y) is performed.

Naming

Some variables names are not evocative (a, b, c...), and can, most of the time, be replaced with a meaningful name related to the object they hold (city, distance...)

Syntactic shortcuts

Some statements can be rewritten to be more concise and readable:

• (b in path)==False -> b not in path
• Use of enumerate:
for i in range(len(fake_origin_list)):
fake_origin = fake_origin_list[i]

# Can be rewritten to:
for i, fake_origin in enumerate(fake_origin_list):
...

Some patterns indicate that lists are not the most appropriate data structure to use:

for element in elements:
if element not in my_list:
my_list.append(element)

This pattern usually indicates that a set is missing, which is a data structure that intrinsically does not allow duplication. With a set, this would simply become:

my_set.update(elements)

Which is faster to write, understand and execute. Similar optimization can probably be introduced with dict, for example mappings from city names (which are unique) to distances.

Use of min instead of sort

This pattern:

total_distance_base.sort()
for a in total_distance_base:
...  # Use a
break

Can be replaced by this one, which avoids having to sort the whole total_distance_base list (O(n*log(n))):

try:
a = min(total_distance_base)
except ValueError:
pass  # No elements in total_distance_base
else:
...  # Use a

Type hints

Type annotations are especially useful to make it clear what a function expects/returns, and what empty containers expect:

distances_to_centre: list[Path] = []

Refactor

Here is an example of refactor that does not change the behavior of the algorithme (only the prints have been removed). The introduction of sets and dicts should make it scale better to more cities. To verify that the behavior has not changed, the random.seed() function can be set with the same value in your own implementation.

import math
import random
import tkinter as tk
from dataclasses import dataclass
from typing import NamedTuple, Collection, Sequence, Mapping

class Point(NamedTuple):
x: int
y: int

# Options to set to True to make City instances storable in a set:
@dataclass(frozen=True, unsafe_hash=True)
class City:
coordinates: Point
name: int
# Note: with such a simple data structure, it would also make sense to store
# the cities as lists of coordinates, where their position index in the
# list define their name

@dataclass
class Path:
distance: int
city_name: int

def create_city(
count: int = 50, minimum: Point = Point(0, 0), maximum: Point = Point(700, 700)
) -> set[City]:
cities = set()
for i in range(count):
rand_x = random.randint(minimum.x, maximum.x)
rand_y = random.randint(minimum.y, maximum.y)
city = City(Point(rand_x, rand_y), name=i)
return cities

def compute_distances_to_centre(cities: Collection[City]) -> list[Path]:
if not cities:
return []  # Fixes a bug where a ZeroDivisionError was raised when "cities" was empty
sum_x, sum_y = (sum(axis) for axis in zip(*(city.coordinates for city in cities)))
avg_x = sum_x // len(cities)
avg_y = sum_y // len(cities)
distances_to_centre: list[Path] = [
Path(
distance=int(math.dist((avg_x, avg_y), city.coordinates)),
city_name=city.name,
)
for city in cities
]
return sorted(distances_to_centre, key=lambda p: p.distance)

def sort_cities(
cities: set[City], last_city_scalar: int = 5, center_scalar: int = 2
) -> list[City]:
"""Sort the provided cities to give a solution to the TSP

:param cities: The :class:City instances to sort. Warning: the set is emptied
by the function
:param last_city_scalar: ...
:param center_scalar: ...
:return: A sorted list of cities
"""
# Non-mutable mapping to quickly retrieve cities from their names on each iteration:
cities_by_name: Mapping[int, City] = {city.name: city for city in cities}
sorted_cities: list[City] = []
while cities:
distances_to_centre = compute_distances_to_centre(cities)
distances_to_last: list[Path] = []
for city in cities:
if sorted_cities:
point = sorted_cities[-1].coordinates
else:
# Bug made obvious: creating a Point from a distance and a city name
point = Point(
x=distances_to_centre[-1].distance,
y=distances_to_centre[-1].city_name,
)
distances_to_last.append(
Path(
int(math.dist(point, city.coordinates)),
city.name,
)
)
paths: list[Path] = []
for path_last in distances_to_last:
for path_center in distances_to_centre:
if path_last.city_name == path_center.city_name:
distance = (
last_city_scalar * path_last.distance
+ center_scalar * path_center.distance
)
paths.append(Path(distance, path_last.city_name))
try:
min_distance = min(p.distance for p in paths)
except ValueError:
pass
else:
for path in paths:
if path.distance == min_distance:
next_city = cities_by_name[path.city_name]
sorted_cities.append(next_city)
cities.remove(next_city)
break
return sorted_cities

def display_path(sorted_cities: Sequence[City]) -> None:
window = tk.Tk()
window.config(bg="White")
window.title("Hello Python")
window.geometry("1000x1000+10+20")
canvas = tk.Canvas(width=800, height=900, bg="white")
for city in sorted_cities:
canvas.create_oval(
fill="Black",
)
for i, city in enumerate(sorted_cities):
next_city = sorted_cities[(i + 1) % len(sorted_cities)]
total_road += math.dist(city.coordinates, next_city.coordinates)
canvas.create_line(
city.coordinates.x,
city.coordinates.y,
next_city.coordinates.x,
next_city.coordinates.y,
width=2,
fill="Blue",
)
window.mainloop()

def main() -> None:
# Fixing the seed can be used to verify that the behavior is exactly
# the same as before the refactor:
random.seed(16)
cities = create_city()
sorted_cities = sort_cities(cities)
display_path(sorted_cities)

if __name__ == "__main__":
main()