X-Git-Url: https://git.distorted.org.uk/~mdw/rocl/blobdiff_plain/6f7ff7517fc2b5d67138ddd1055020385bf6baa7..9590c915c9bfe4a4fbe6a2d3af91fa4a9cb7027b:/graph.c

diff --git a/graph.c b/graph.c
index 0f9fa84..23c1a32 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 theory stuff
  *
@@ -24,14 +24,6 @@
  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: graph.c,v $
- * Revision 1.1  2003/03/07 00:45:13  mdw
- * Graph theory functions.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include <assert.h>
@@ -252,7 +244,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 +293,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;
@@ -372,7 +364,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
 
   if (nn <= 2) {
     memcpy(r_best, r, nn * sizeof(*r));
-    if (n == 1)
+    if (nn == 1)
       c_best = a[r[0] * n + r[0]];
     else
       c_best = a[r[0] * n + r[1]];
@@ -406,7 +398,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 +435,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 +498,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 &&