From b758c3433840e6a51f285455ccdee07dcebf52b6 Mon Sep 17 00:00:00 2001
Message-Id: <b758c3433840e6a51f285455ccdee07dcebf52b6.1715367655.git.mdw@distorted.org.uk>
From: Mark Wooding <mdw@chiark.greenend.org.uk>
Date: Sat, 8 Mar 2003 00:40:32 +0000
Subject: [PATCH] Fix unsigned crapness in travelling-salesman solver.
Organization: Straylight/Edgeware

From: mdw <mdw>

---
 graph.c | 38 ++++++++++++++++++++++++++++++++------
 1 file changed, 32 insertions(+), 6 deletions(-)

diff --git a/graph.c b/graph.c
index 0f9fa84..2ec27f8 100644
--- a/graph.c
+++ b/graph.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: graph.c,v 1.1 2003/03/07 00:45:13 mdw Exp $
+ * $Id: graph.c,v 1.2 2003/03/08 00:40:32 mdw Exp $
  *
  * Graph theory stuff
  *
@@ -27,6 +27,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: graph.c,v $
+ * Revision 1.2  2003/03/08 00:40:32  mdw
+ * Fix unsigned crapness in travelling-salesman solver.
+ *
  * Revision 1.1  2003/03/07 00:45:13  mdw
  * Graph theory functions.
  *
@@ -252,7 +255,7 @@ static size_t rrange(size_t max)
  * -inner COUNT		Perform COUNT loops each cooling cycle.  Default is
  *			10000.
  *
- * -init TEMP		Set the initial temperature to TEMP.  Default is not
+ * -temp TEMP		Set the initial temperature to TEMP.  Default is not
  *			very helpful.  Initial setting should be well above
  *			the maximum cost increase from a cycle.
  *
@@ -301,7 +304,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
 	err(ti, "cooling factor must be > 1");
 	goto done;
       }
-    } else if (strcmp(p, "-init") == 0) {
+    } else if (strcmp(p, "-temp") == 0) {
       i++; if (i >= objc) goto args;
       if (Tcl_GetDoubleFromObj(ti, objv[i], &temp) != TCL_OK)
 	goto done;
@@ -406,7 +409,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
     i--;
   }
 
-/*   printf("*** initial cost = %lu\n", c_best); */
+/*   printf("*** initial cost = %lu; n = %u; nn = %u\n", c, n, nn); */
   c_curr = c_best = c;
   memcpy(r_best, r, nn * sizeof(*r));
 
@@ -443,8 +446,8 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
       if (i == j)
 	continue; /* No change */
       if (j < i) { t = i; i = j; j = t; }
-      ilo = (i - 1) % nn; ihi = (i + 1) % nn;
-      jlo = (j - 1) % nn; jhi = (j + 1) % nn;
+      ilo = (i + nn - 1) % nn; ihi = (i + 1) % nn;
+      jlo = (j + nn - 1) % nn; jhi = (j + 1) % nn;
 
       c = c_curr;
       if (j == nn - 1) {
@@ -506,6 +509,29 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
 	}
       }
 
+#ifdef PARANOID_CHECKING /* Turn this on to check the shortcut */
+      {
+	unsigned long cc;
+	size_t ii, jj;
+	if (cycle) { jj = 0; ii = nn - 1; }
+	else { jj = nn - 1; ii = jj - 1; }
+	cc = 0;
+	t = r[i]; r[i] = r[j]; r[j] = t;
+	for (;;) {
+	  cc += a[r[ii] * n + r[jj]];
+	  if (!ii)
+	    break;
+	  jj = ii;
+	  ii--;
+	}
+	t = r[i]; r[i] = r[j]; r[j] = t;
+	if (c != cc) {
+	  printf("i = %u; j = %u; c = %lu; cc = %lu\n", i, j, c, cc);
+	  abort();
+	}
+      }
+#endif
+
       /* --- Decide what to do --- */
 
       if (c > c_curr &&
-- 
[mdw]