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

diff --git a/graph.c b/graph.c
index 0f9fa84..9dc3942 100644
--- a/graph.c
+++ b/graph.c
@@ -1,37 +1,27 @@
 /* -*-c-*-
  *
- * $Id: graph.c,v 1.1 2003/03/07 00:45:13 mdw Exp $
- *
  * Graph theory stuff
  *
  * (c) 2003 Mark Wooding
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * 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., 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 +242,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 +291,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 +362,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 +396,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 +433,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 +496,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 &&
@@ -521,7 +534,7 @@ static int cmd_tsp(ClientData cd, Tcl_Interp *ti,
       t = r[i]; r[i] = r[j]; r[j] = t;
       if (c_curr < c_best) {
 	c_best = c_curr;
-/* 	printf("*** new best = %lu\n", c_best); */
+/*	printf("*** new best = %lu\n", c_best); */
 	memcpy(r_best, r, nn * sizeof(*r));
       }
     }