* Initial import

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 ()