Fix unsigned crapness in travelling-salesman solver.

[rocl] / graph.c

diff --git a/graph.c b/graph.c
index 0f9fa8435e399c666a2010644a8584bdfc5f26b8..2ec27f86046564efdb69b546c1003fcdfd591bb1 100644 (file)
--- 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 &&