summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-17 03:50:45 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-17 03:50:45 +0100
commitb28e2b83fa7541f764eb829daab47de48e9f999e (patch)
treed6c56ba867e2fb513fbfe6f2071ff8c2589440d4
parent8b8fc5fe2b496620f5a4958f267475e55f86ee63 (diff)
downloadtsp-b28e2b83fa7541f764eb829daab47de48e9f999e.tar.gz
tsp-b28e2b83fa7541f764eb829daab47de48e9f999e.tar.bz2
* Comments & cleanup
-rwxr-xr-xtsp.py156
1 files changed, 122 insertions, 34 deletions
diff --git a/tsp.py b/tsp.py
index 1374b67..82e41c4 100755
--- a/tsp.py
+++ b/tsp.py
@@ -36,24 +36,26 @@ import math
import cairo
import threading
-MAX_X = 500
-MAX_Y = 500
-OFFSET_X = 20
-OFFSET_Y = 20
+MAX_X = 500 # Max X (virtual) coordinate
+MAX_Y = 500 # Max Y (virtual) coordinate
+OFFSET_X = 20 # Left & right offsets (for drawing purpose)
+OFFSET_Y = 20 # Top & bottom offsets (for drawing purpose)
-CITY_RADIUS = 3
+CITY_RADIUS = 3 # Radius of the visual city points
SHOW_NAMES = True
-INITS = ["Random", "Greedy"]
-ALGOS = ["2opt", "Annealing"]
-COUNTS = [10, 25, 50, 100, 250]
+INITS = ["Random", "Greedy"] # Init methods choices
+ALGOS = ["2opt", "Annealing"] # Algorithms choices
+COUNTS = [10, 25, 50, 100, 250] # City counts choices
+# Default settings
DEFAULT_INIT = "Random"
DEFAULT_ALGO = "Annealing"
DEFAULT_COUNT = 50
class Color:
+ '''Helper object for color handling'''
def __init__ (self, r, g, b):
self.r = r
@@ -64,26 +66,19 @@ CITY_COLOR = Color (0.9, 0, 0) # Red
TEXT_COLOR = Color (0, 0, 0) # Black
PATH_COLOR = Color (0, 0, 0.8) # Blue
-class City:
-
- i = 0
- x = 0
- y = 0
-
- def __init__ (self, i):
- self.i = i
- self.x = OFFSET_X + random.uniform (0, MAX_X)
- self.y = OFFSET_Y + random.uniform (0, MAX_Y)
-
def distance (c1, c2):
+ '''Compute the distance between two points'''
return math.sqrt ((c2.x - c1.x) ** 2 + (c2.y - c1.y) ** 2)
def draw_map (cities, cr):
+ '''Draw a map of points on a Cairo context'''
global CITY_COLOR, TEXT_COLOR, SHOW_NAMES
def draw_point (city):
+ '''Helper function to draw a point'''
cr.arc (city.x, city.y, CITY_RADIUS, 0, 2 * math.pi)
cr.fill ()
def draw_name (city):
+ '''Helper function to draw a point label'''
cr.move_to (city.x + 6, city.y + 6)
cr.show_text ("%d" % city.i)
cr.fill ()
@@ -96,6 +91,7 @@ def draw_map (cities, cr):
map (draw_name, cities.values ())
def draw_path (cities, path, cr):
+ '''Draw a path on a Cairo context'''
global PATH_COLOR
prev = path[0]
list = path[1:] + [prev]
@@ -108,19 +104,36 @@ def draw_path (cities, path, cr):
cr.line_to (cities[i].x, cities[i].y)
cr.stroke ()
+class City:
+ '''Helper object for points map handling'''
+
+ i = 0
+ x = 0
+ y = 0
+
+ def __init__ (self, i):
+ '''Initialize object (generate random coordinates)'''
+ self.i = i
+ self.x = OFFSET_X + random.uniform (0, MAX_X)
+ self.y = OFFSET_Y + random.uniform (0, MAX_Y)
+
class Path (list):
+ '''Helper object that automagically computes the path length'''
context = None
def __init__ (self, context, list):
+ '''Initalize list & object'''
self.context = context
for i in list:
self.append (i)
self.compute_length ()
def compute_length (self):
+ '''Compute length, the computation is pretty straight-forward'''
prev = self[0]
- list = self[1:] + [prev]
+ list = self[1:] + [prev] # Add the first element of the list to
+ # the end to close the path
length = 0
for i in list:
length += self.context.dists[prev][i]
@@ -128,38 +141,52 @@ class Path (list):
self.length = length
class Context:
+ '''Helper object handling the city map and distances computations, and
+featuring some basic methods such as nearest neighbours (a.k.a. greedy)
+algorithm'''
count = 0
dists = {}
map = {}
def __init__ (self, delayed = False, count = DEFAULT_COUNT):
+ '''Initialize object'''
self.count = count
if not delayed:
self.prepare ()
def prepare (self):
+ '''Prepare context data'''
self.generate_map ()
self.compute_dists ()
def generate_map (self):
+ '''Generate a map of random points'''
+ # FIXME: maybe should we check for duplicates?
self.map = {}
for i in range (0, self.count):
self.map[i] = City (i)
def compute_dists (self):
+ '''Compute the distances array'''
self.dists = {}
- for c1 in self.map.values ():
- self.dists[c1.i] = {}
- for c2 in self.map.values ():
- self.dists[c1.i][c2.i] = distance (c1, c2)
+ # Only compute half of the array, it's symetric
+ for i in range (0, self.count):
+ self.dists[i] = {}
+ for j in range (i, self.count):
+ self.dists[i][j] = distance (self.map[i], self.map[j])
+ for i in range (0, self.count):
+ for j in range (0, i):
+ self.dists[i][j] = self.dists[j][i]
def draw_to_cr (self, cr, path = None):
+ '''Draw map & path (if any) to the given Cairo context'''
if path:
draw_path (self.map, path, cr)
draw_map (self.map, cr)
def draw_png (self, filename, path = None):
+ '''Dump map & path (if any) to a PNG file'''
surface = cairo.ImageSurface (cairo.FORMAT_ARGB32,
MAX_X + 2 * OFFSET_X,
MAX_Y + 2 * OFFSET_Y)
@@ -170,11 +197,11 @@ class Context:
surface.write_to_png (filename)
def nearest_neighbours (self, start = 0):
+ '''Nearest neighbours (a.k.a. greedy) algorithm'''
def reduce_nearest (d1, d2):
- if d1[1] < d2[1]:
- return d1
- else:
- return d2
+ '''Reduce function to find the nearest point of a list'''
+ if d1[1] < d2[1]: return d1
+ else: return d2
path = [start]
while len (path) < len (self.map):
current = path[-1]
@@ -185,6 +212,7 @@ class Context:
return Path (self, path)
def nearest_neighbours_best (self):
+ '''Nearest neighbours algorithm applied to each city of the list'''
best = None
for i in self.map.keys ():
path = self.nearest_neighbours (start = i)
@@ -193,23 +221,38 @@ class Context:
return best
def random_path (self):
+ '''Random path generator'''
path = range (0, self.count)
random.shuffle (path)
return Path (self, path)
+'''
+A few notes about the way algorithms should be implemented:
+* The class name should look like "Algo_Name" where Name is the name that will
+be displayed in the GUI
+* The "run" method is what will be run by the running thread
+* The "run" method must use the "yield" mechanism to raise the current path as
+it goes on. This lets the running thread nicely interrupt execution if needed,
+and lets it quickly halt.
+'''
+
class Algo:
+ '''Base class for algorithm, please extend me!'''
context = None
def __init__ (self, context):
+ '''Initialize object'''
self.context = context
def run (self):
'''Implement this in your algorithm subclass'''
class Algo_2opt (Algo):
+ '''Classic 2opt algorithm'''
def run (self, path = None):
+ '''Algorithm main loop'''
if not path:
path = self.context.nearest_neighbours_best ()
best = path
@@ -220,22 +263,29 @@ class Algo_2opt (Algo):
best = path
def do_2opt (self, path):
+ '''Do a simple transformation: given two points i and j, reverse the
+path between i and j (e.g. [0, 1, 2, 3, 4, 5] with i = 1 and j = 4 becomes
+[0, 1, 3, 2, 4, 5]. This is better than just exchanging two points because the
+former only breaks 2 links while the latters breaks 4.'''
i, j = random.sample (path, 2)
if i < j:
segment = path[i + 1:j]
segment.reverse ()
return Path (self.context, path[:i + 1] + segment + path[j:])
else:
+ '''If i > j, loop around the list'''
segment = path[i + 1:] + path[:j]
segment.reverse ()
return Path (self.context, path[j:i + 1] + segment)
class Algo_Annealing (Algo_2opt):
+ '''Simulated annealing algorithm'''
- t0 = 10
- updates = 0
+ t0 = 10 # Initial temperature
+ updates = 0 # Accepted updates counter
def run (self, path = None):
+ '''Algorithm main loop'''
self.updates = 0
if not path:
path = self.context.nearest_neighbours_best ()
@@ -252,20 +302,26 @@ class Algo_Annealing (Algo_2opt):
self.updates += 1
def accept_change (self, current, next):
+ '''Choose if a worse path is accepted anyway, this is the key of the
+simulated annealing algorithm: the path will be accepted if the result of
+exp (- (next length - current length) / temperature) is greater than a random
+floating point number, where temperature evolves according to a given law
+based on the current number of iterations (or so)'''
delta = next.length - current.length
p0 = random.random ()
t0 = 1
p = math.exp (- delta / self.temp ())
- #print self.temp ()
if p0 <= p:
return True
else:
return False
def temp (self):
+ '''Temperature law: t = t0 - accepted_updates * 0.001 (min'd to 0.1)'''
return max (self.t0 - self.updates * 0.001, 0.1)
class AlgoThread (threading.Thread):
+ '''Threading running a given algorithm'''
context = None
algo = None
@@ -275,6 +331,7 @@ class AlgoThread (threading.Thread):
terminate = False
def __init__ (self, context, algo, gui, canvas, use_nearest = False):
+ '''Initialize the thread'''
threading.Thread.__init__ (self)
self.context = context
self.algo = algo
@@ -283,6 +340,7 @@ class AlgoThread (threading.Thread):
self.nearest = use_nearest
def update_best (self, path):
+ '''Update GUI to reflect the finding of a better solution'''
gtk.gdk.threads_enter ()
if not path: length = None
else: length = path.length
@@ -291,10 +349,13 @@ class AlgoThread (threading.Thread):
gtk.gdk.threads_leave ()
def run (self):
+ '''Main thread loop: generate a path (randomly or not, according to
+the current settings) and run the algorithm on it until the stop () function
+is called.'''
self.update_best (path = None)
best = None
if self.nearest:
- for i in self.context.map.keys ():
+ for i in self.context.map:
if self.terminate:
return
path = self.context.nearest_neighbours (start = i)
@@ -311,21 +372,25 @@ class AlgoThread (threading.Thread):
self.update_best (path = best)
def stop (self):
+ '''Stop thread'''
self.terminate = True
class AlgoCanvas (gtk.DrawingArea):
+ '''Canvas widget for displaying maps & paths'''
context = None
surface = None
path = None
def __init__ (self, context):
+ '''Initialize widget'''
gtk.DrawingArea.__init__ (self)
self.context = context
self.connect ("expose-event", self.expose)
self.set_size_request (MAX_X + 2 * OFFSET_X, MAX_Y + 2 * OFFSET_Y)
def redraw (self, path = None, damage = False):
+ '''Redraw surface using the given path (if any)'''
self.path = path
self.surface = cairo.ImageSurface (cairo.FORMAT_ARGB32,
MAX_X + 2 * OFFSET_X,
@@ -335,9 +400,12 @@ class AlgoCanvas (gtk.DrawingArea):
cr.paint ()
self.context.draw_to_cr (cr, self.path)
if damage:
+ '''Damage widget if requested'''
self.queue_draw ()
def expose (self, widget, event):
+ '''Handle expose events: copy the saved surface to the new widget
+Cairo context, clipping the draw area if needed'''
cr = self.window.cairo_create ()
if not self.surface:
self.redraw ()
@@ -349,6 +417,7 @@ class AlgoCanvas (gtk.DrawingArea):
return False
class AlgoGui (gtk.Window):
+ '''GUI for testing TSP algorithms'''
context = None
algo = None
@@ -366,41 +435,50 @@ class AlgoGui (gtk.Window):
config_label = None
def __init__ (self):
+ '''Initialize GUI'''
global INITS, ALGOS, COUNTS
gtk.Window.__init__ (self)
- self.context = Context (delayed = True)
+ self.context = Context (delayed = True) # Prepare Context
self.algo = None
+ # GTK stuff
self.set_title ("TSP Algorithm test GUI")
self.set_position (gtk.WIN_POS_CENTER)
self.connect ("delete-event", gtk.main_quit)
box = gtk.VBox ()
self.add (box)
- self.canvas = AlgoCanvas (self.context)
+ self.canvas = AlgoCanvas (self.context) # Our canvas
box.pack_start (self.canvas, False, False)
hbox = gtk.HBox ()
+ # Init methods
self.init_box = gtk.combo_box_new_text ()
map (self.init_box.append_text, INITS)
self.init_box.set_active (INITS.index (DEFAULT_INIT))
hbox.pack_start (self.init_box, False, False)
+ # Algorithms
self.algo_box = gtk.combo_box_new_text ()
map (self.algo_box.append_text, ALGOS)
self.algo_box.set_active (ALGOS.index (DEFAULT_ALGO))
hbox.pack_start (self.algo_box, False, False)
+ # City counts
self.count_box = gtk.combo_box_new_text ()
map (lambda i: self.count_box.append_text ("%d cities" % i), COUNTS)
self.count_box.set_active (COUNTS.index (DEFAULT_COUNT))
hbox.pack_start (self.count_box, False, False)
+ # Generate button
self.gen_button = gtk.Button ("Generate")
self.gen_button.connect ("clicked", self.generate)
hbox.pack_start (self.gen_button, False, False)
+ # Start button
self.start_button = gtk.Button ("Start")
self.start_button.connect ("clicked", self.start)
self.start_button.set_sensitive (False)
hbox.pack_start (self.start_button, False, False)
+ # Stop button
self.stop_button = gtk.Button ("Stop")
self.stop_button.connect ("clicked", self.stop)
self.stop_button.set_sensitive (False)
hbox.pack_start (self.stop_button, False, False)
+ # Show labels button
names_button = gtk.CheckButton (label = "Labels")
names_button.connect ("toggled", self.toggle_show_names)
names_button.set_active (True)
@@ -409,6 +487,7 @@ class AlgoGui (gtk.Window):
alignment.add (hbox)
box.pack_start (alignment, False, False)
box.show_all ()
+ # Informative labels
self.best_label = gtk.Label ()
self.update_best (length = None)
box.pack_start (self.best_label, False, False)
@@ -417,27 +496,33 @@ class AlgoGui (gtk.Window):
box.pack_start (self.config_label, False, False)
def toggle_show_names (self, button):
+ '''Toggle SHOW_NAMES setting & damage canvas'''
global SHOW_NAMES
SHOW_NAMES = button.get_active ()
self.canvas.redraw (path = self.canvas.path, damage = True)
def get_count (self):
+ '''Get currently selected city count'''
count = self.count_box.get_active_text ().split (" ")[0]
return int (count)
def get_algo (self):
+ '''Get currently selected algorithm'''
return self.algo_box.get_active_text ()
def get_init (self):
+ '''Get currently selected init method'''
return self.init_box.get_active_text ()
def generate (self, *args):
+ '''Generate a new map'''
self.context.count = self.get_count ()
self.context.prepare ()
self.start_button.set_sensitive (True)
self.canvas.redraw (damage = True)
def start (self, *args):
+ '''Run algorithm'''
global INITS
self.stop ()
self.update_config ()
@@ -451,6 +536,7 @@ class AlgoGui (gtk.Window):
self.stop_button.set_sensitive (True)
def stop (self, *args):
+ '''Halt algorithm'''
if self.thread:
self.thread.stop ()
self.thread.join (0.1)
@@ -463,6 +549,7 @@ class AlgoGui (gtk.Window):
self.stop_button.set_sensitive (False)
def update_best (self, length):
+ '''Update best solution length label'''
if not length:
self.best_label.set_markup ("<b>Best length yet</b>: N/A")
return
@@ -470,6 +557,7 @@ class AlgoGui (gtk.Window):
self.best_label.set_markup ("<b>Best length yet</b>: %s" % length)
def update_config (self, config = True):
+ '''Update current configuration label'''
if not config:
self.config_label.set_markup ("<b>Configuration</b>: N/A")
return