* Comments & cleanup

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