summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rwxr-xr-xtsp.py421
1 files changed, 421 insertions, 0 deletions
diff --git a/tsp.py b/tsp.py
new file mode 100755
index 0000000..5ccef41
--- /dev/null
+++ b/tsp.py
@@ -0,0 +1,421 @@
+#!/usr/bin/env python
+# coding=utf-8
+
+'''
+ Various Travelling Salesman Problem algorithms
+ Author : Guillaume "iXce" Seguin
+ Email : guillaume@segu.in
+
+ Copyright (C) 2007 Guillaume Seguin
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License
+ as published by the Free Software Foundation; either version 2
+ of the License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+'''
+
+import pygtk
+pygtk.require ("2.0")
+import gtk
+
+gtk.gdk.threads_init ()
+
+import random
+import math
+import cairo
+import threading
+
+MAX_X = 500
+MAX_Y = 500
+OFFSET_X = 20
+OFFSET_Y = 20
+
+CITY_RADIUS = 3
+
+DEFAULT_COUNT = 100
+
+SHOW_NAMES = True
+
+ALGOS = ["2opt"]
+COUNTS = [8, 10, 25, 50, 100, 250]
+
+class Color:
+
+ def __init__ (self, r, g, b):
+ self.r = r
+ self.g = g
+ self.b = b
+
+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):
+ return math.sqrt ((c2.x - c1.x) ** 2 + (c2.y - c1.y) ** 2)
+
+def draw_map (cities, cr):
+ global CITY_COLOR, TEXT_COLOR, SHOW_NAMES
+ def draw_point (city):
+ cr.arc (city.x, city.y, CITY_RADIUS, 0, 2 * math.pi)
+ cr.fill ()
+ def draw_name (city):
+ cr.move_to (city.x + 6, city.y + 6)
+ cr.show_text ("%d" % city.i)
+ cr.fill ()
+ cr.set_operator (cairo.OPERATOR_OVER)
+ cr.set_source_rgb (CITY_COLOR.r, CITY_COLOR.g, CITY_COLOR.b)
+ map (draw_point, cities.values ())
+ if not SHOW_NAMES:
+ return
+ cr.set_source_rgb (TEXT_COLOR.r, TEXT_COLOR.g, TEXT_COLOR.b)
+ map (draw_name, cities.values ())
+
+def draw_path (cities, path, cr):
+ global PATH_COLOR
+ prev = path[0]
+ list = path[1:] + [prev]
+ length = 0
+ cr.set_operator (cairo.OPERATOR_OVER)
+ cr.set_source_rgb (PATH_COLOR.r, PATH_COLOR.g, PATH_COLOR.b)
+ cr.set_line_width (1)
+ cr.move_to (cities[prev].x, cities[prev].y)
+ for i in list:
+ cr.line_to (cities[i].x, cities[i].y)
+ cr.stroke ()
+
+class Path (list):
+
+ context = None
+
+ def __init__ (self, context, list):
+ self.context = context
+ for i in list:
+ self.append (i)
+ self.compute_length ()
+
+ def compute_length (self):
+ prev = self[0]
+ list = self[1:] + [prev]
+ length = 0
+ for i in list:
+ length += self.context.dists[prev][i]
+ prev = i
+ self.length = length
+
+class Context:
+
+ count = 0
+ dists = {}
+ map = {}
+
+ def __init__ (self, delayed = False, count = DEFAULT_COUNT):
+ self.count = count
+ if not delayed:
+ self.prepare ()
+
+ def prepare (self):
+ self.generate_map ()
+ self.compute_dists ()
+
+ def generate_map (self):
+ self.map = {}
+ for i in range (0, self.count):
+ self.map[i] = City (i)
+
+ def compute_dists (self):
+ 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)
+
+ def draw_to_cr (self, cr, path = None):
+ if path:
+ draw_path (self.map, path, cr)
+ draw_map (self.map, cr)
+
+ def draw_png (self, filename, path = None):
+ surface = cairo.ImageSurface (cairo.FORMAT_ARGB32,
+ MAX_X + 2 * OFFSET_X,
+ MAX_Y + 2 * OFFSET_Y)
+ cr = cairo.Context (surface)
+ cr.set_operator (cairo.OPERATOR_CLEAR)
+ cr.paint ()
+ self.draw_to_cr (cr, path)
+ surface.write_to_png (filename)
+
+ def nearest_neighbours (self, start = 0):
+ def reduce_nearest (d1, d2):
+ if d1[1] < d2[1]:
+ return d1
+ else:
+ return d2
+ path = [start]
+ while len (path) < len (self.map):
+ current = path[-1]
+ dists = self.dists[current].items ()
+ dists = filter (lambda (i, dist): i not in path, dists)
+ next = reduce (reduce_nearest, dists)
+ path.append (next[0])
+ return Path (self, path)
+
+ def nearest_neighbours_best (self):
+ best = None
+ for i in self.map.keys ():
+ path = self.nearest_neighbours (start = i)
+ if not best or path.length < best.length:
+ best = path
+ return best
+
+class Algo:
+
+ context = None
+
+ def __init__ (self, context):
+ self.context = context
+
+ def run (self):
+ '''Implement this in your algorithm subclass'''
+
+class Algo_2opt (Algo):
+
+ def run (self, path = None):
+ if not path:
+ path = self.context.nearest_neighbours_best ()
+ best = path
+ while True:
+ yield path
+ path = self.do_2opt (best)
+ if path.length < best.length:
+ best = path
+
+ def do_2opt (self, path):
+ i, j = sorted (random.sample (path, 2))
+ segment = path[i + 1:j]
+ segment.reverse ()
+ return Path (self.context, path[0:i + 1] + segment + path[j:])
+
+class AlgoThread (threading.Thread):
+
+ context = None
+ algo = None
+ gui = None
+ canvas = None
+ terminate = False
+
+ def __init__ (self, context, algo, gui, canvas):
+ threading.Thread.__init__ (self)
+ self.context = context
+ self.algo = algo
+ self.gui = gui
+ self.canvas = canvas
+
+ def update_best (self, path):
+ gtk.gdk.threads_enter ()
+ if not path: length = None
+ else: length = path.length
+ self.gui.update_best (length)
+ self.canvas.redraw (path = path, damage = True)
+ gtk.gdk.threads_leave ()
+
+ def run (self):
+ self.update_best (path = None)
+ best = None
+ for i in self.context.map.keys ():
+ if self.terminate:
+ return
+ path = self.context.nearest_neighbours (start = i)
+ if not best or path.length < best.length:
+ best = path
+ self.update_best (path = best)
+ runner = self.algo.run (best)
+ while not self.terminate:
+ path = runner.next ()
+ if self.terminate:
+ return
+ if not best or path.length < best.length:
+ best = path
+ self.update_best (path = best)
+
+ def stop (self):
+ self.terminate = True
+
+class AlgoCanvas (gtk.DrawingArea):
+
+ context = None
+ surface = None
+ path = None
+
+ def __init__ (self, context):
+ 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):
+ self.path = path
+ self.surface = cairo.ImageSurface (cairo.FORMAT_ARGB32,
+ MAX_X + 2 * OFFSET_X,
+ MAX_Y + 2 * OFFSET_Y)
+ cr = cairo.Context (self.surface)
+ cr.set_operator (cairo.OPERATOR_CLEAR)
+ cr.paint ()
+ self.context.draw_to_cr (cr, self.path)
+ if damage:
+ self.queue_draw ()
+
+ def expose (self, widget, event):
+ cr = self.window.cairo_create ()
+ if not self.surface:
+ self.redraw ()
+ cr.set_source_surface (self.surface)
+ cr.rectangle (event.area.x, event.area.y,
+ event.area.width, event.area.height)
+ cr.clip ()
+ cr.paint ()
+ return False
+
+class AlgoGui (gtk.Window):
+
+ context = None
+ algo = None
+ thread = None
+
+ canvas = None
+ algo_box = None
+ count_box = None
+ gen_button = None
+ start_button = None
+ stop_button = None
+
+ best_label = None
+ config_label = None
+
+ def __init__ (self):
+ global ALGOS, COUNTS
+ gtk.Window.__init__ (self)
+ self.context = Context (delayed = True)
+ self.algo = None
+ 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)
+ box.pack_start (self.canvas, False, False)
+ hbox = gtk.HBox ()
+ self.algo_box = gtk.combo_box_new_text ()
+ map (self.algo_box.append_text, ALGOS)
+ self.algo_box.set_active (ALGOS.index ("2opt"))
+ hbox.pack_start (self.algo_box, False, False)
+ 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 (25))
+ hbox.pack_start (self.count_box, False, False)
+ self.gen_button = gtk.Button ("Generate")
+ self.gen_button.connect ("clicked", self.generate)
+ hbox.pack_start (self.gen_button, False, False)
+ 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)
+ 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)
+ names_button = gtk.CheckButton (label = "Show names")
+ names_button.connect ("toggled", self.toggle_show_names)
+ names_button.set_active (True)
+ hbox.pack_start (names_button, False, False)
+ alignment = gtk.Alignment (0.5, 0.5, 0, 0)
+ alignment.add (hbox)
+ box.pack_start (alignment, False, False)
+ box.show_all ()
+ self.best_label = gtk.Label ()
+ self.update_best (length = None)
+ box.pack_start (self.best_label, False, False)
+ self.config_label = gtk.Label ()
+ self.update_config (config = False)
+ box.pack_start (self.config_label, False, False)
+
+ def toggle_show_names (self, button):
+ global SHOW_NAMES
+ SHOW_NAMES = button.get_active ()
+ self.canvas.redraw (path = self.canvas.path, damage = True)
+
+ def get_count (self):
+ count = self.count_box.get_active_text ().split (" ")[0]
+ return int (count)
+
+ def get_algo (self):
+ return self.algo_box.get_active_text ()
+
+ def generate (self, *args):
+ self.context.count = self.get_count ()
+ self.context.prepare ()
+ self.start_button.set_sensitive (True)
+ self.canvas.redraw (damage = True)
+
+ def start (self, *args):
+ self.stop ()
+ self.update_config ()
+ self.algo = eval ("Algo_%s" % self.get_algo ()) (self.context)
+ self.thread = AlgoThread (self.context, self.algo, self, self.canvas)
+ self.thread.start ()
+ self.gen_button.set_sensitive (False)
+ self.start_button.set_sensitive (False)
+ self.stop_button.set_sensitive (True)
+
+ def stop (self, *args):
+ if self.thread:
+ self.thread.stop ()
+ self.thread.join ()
+ self.thread = None
+ self.gen_button.set_sensitive (True)
+ self.start_button.set_sensitive (True)
+ self.stop_button.set_sensitive (False)
+
+ def update_best (self, length):
+ if not length:
+ self.best_label.set_markup ("<b>Best length yet</b>: N/A")
+ return
+ length = round (length, 2)
+ self.best_label.set_markup ("<b>Best length yet</b>: %s" % length)
+
+ def update_config (self, config = True):
+ if not config:
+ self.config_label.set_markup ("<b>Configuration</b>: N/A")
+ return
+ config = "<b>Configuration</b>: %d cities, using %s algorithm"
+ self.config_label.set_markup (config % (self.get_count (),
+ self.get_algo ()))
+
+if __name__ == "__main__":
+ gui = AlgoGui ()
+ gui.show_all ()
+ try:
+ gtk.main ()
+ except KeyboardInterrupt:
+ pass
+ gui.stop ()